通用技术 求数据结构

杨漫步 · 2021年09月06日 · 最后由 杨漫步 回复于 2021年09月11日 · 933 次阅读

我有 5 个点,A B C D E,然后 每个点有起点和终点,比如 A_start A_end,那么我想找出所有的组合,保证 1:start 先于 end,2:所有的组合
有什么方便的数据结构吗,当前只是例子,点大概 100 个左右

当前用 complete 有向图,但是会有几个点有问题
1.搜寻指定的几个点 A B C...的全覆盖,需要进一步判断,因为有可能出现路径查询卡在一个点不能向下走的情形
2.当点的个数多的时候,效率过低,30 个点都近 5 分钟的时间。

共收到 32 条回复 时间 点赞

理解不了,一个点怎么有起点和终点的……

所有的组合指的是 必须是一个 start 和一个 end 么?还是说只能是 A start 和 A end

槽神 回复

也就是意味着点的个数是 2 倍的点,并且点中是有特殊关系的单向

Ikaros灬 回复

所有的

杨漫步 回复

那就是有可能是 start+ start? end+end?

Ikaros灬 回复

有可能是类似于如下:
A_start->B_start->A_end-> B_end
A_start->A_end->B_start-> B_end
B_start->A_start->A_end-> B_end
等等

杨漫步 回复

那就是向量,而不是点了吧
另外,条件 1,“start 先于 end” 还是 “start 小于 end”,如果是 “先于”,那么 “先于” 的定义是什么?

槽神 回复

就是一个时序,先做 start 然后 end

理解不了题干。“5 个点”,“每个点有起点和终点”,是五个运动的元素,每个元素有一个起点和终点?

我来理解一下:我有 5 个类实例,每个实例都有两个属性:起始点和结束点。现在要求实例间的连线,要求每个实例的起始点要先用,才能用结束点。
连线用 1++ 来表示应该可以,然后只要求实例中的起始点小于结束点就可以。

Ouroboros 回复

哈哈,没有多难理解,就是找一堆点 (n 个) 的所有可能的排序
限制是
1.这堆点个数是偶数个。
2.这堆点中每一个点都有和它关联的一个点,它们之间有先后关系。

类似楼上的回复描述

感觉有点类似括号嵌套的问题

@ 杨漫步 5 个节点的时候,有多少种组合? 我验证下自己的计算结果

可不可以弄一个三维数组呢?第一个是 start,第二个是 end,第三个是变量 flag,初始为 0,调用过 start,变为 1,调用过 end 变为 2,每次都先检验 flag 的值,为 0 调用 start,为 1 调用 end,为 2 说明调用完毕,不再调用。本人很菜,大佬们轻点喷。。

ghost 回复

因为我这块有一些额外的依赖,当前试下来 5 个点 11000+

Francissun 回复

可以这样走,但是外层怎么控制顺序呢

杨漫步 回复

噗~~,看来我算错了,算了 11w+。

不过,理论上我觉得穷举所有组合其实不太可能。 等到你有 30 个节点以后,不得跑个好几年。 你做这个事情的具体业务场景是啥?

ghost 回复

生成用例,是的,时间成本过大,因此想着在建模确定了后,那么就后续从先验知识 + 实时运行效果进行改进,逐步确定后续的运行策略。

ghost 回复

你的运行逻辑贴一下?或者分享下?
有没有好的解决先生成这么些数据的思路。
最起码能够陆陆续续的获取这么些数据的方法。不一定一次性获取到

这都是个队列啊,先进先出?

Theodore 回复

不太一样吧。。。他这里要求可以 A_start->B_start->A_end->B_end 的呀

按我之前回复的计算,5 个点 113400,4 个点 2520,3 个点 90,2 个点 6。这个数据,增长的太快了,别说 100 个了,30 个的数据就已经爆炸了。
你这个求的是排列,太多了,光是 start 立刻接 end 这种,都有 A100 的排列组合,还有 start 接 start,把所有 start 接完再处理 end 的也有 A100*A100。
不过通过上面的数据,发现一个规律,总点数每 +1,连线的总数就在前一个的基础上乘以 (总点数) * (2* 总点数-1)。
按照这个规律计算的话
6 个点的总点数是 7484400(事实上在回复的过程中我就在跑 6 个点的数据,跑完后的总数和预测相符)
30 个点的总连线是 7749523141180528462190498768559996393280264554881719828070400000000000000。
就瞅瞅吧。
好奇是什么具体场景。

杨漫步 回复
def my_function(n):
    if n==1:
        return 1
    result = my_function(n-1)*n*(2*n-1)
    return result

用递归计算了下组合数,计算结果跟你的没对上。

数据和我算出来的一致

6 个点的我好像没跑出来,内存 Error 了

杨漫步 回复

事实上我认为,这么大的数据,对正常的场景来说已经是没有意义的了。

怎么感觉像 UnionFind 并查集算法?大佬看看这个文章符合要求不
https://zhuanlan.zhihu.com/p/98406740

是的,但是可以从这里边进行挑选呢,再增加一些限制,比如每个点上的权重,路径的权重等等都会能够比较便利的获取到带有顺序的节点组合。
想着是后期基于此融入一些精准的因素,达到快速获取相关序列

好的,多谢,不是大佬,喜欢这里的氛围,及时分享交流

杨漫步 回复

加限制的话,其实也挺难的,6 个点就 800W 种排列了,100 个点加了限制局部也很容易就形成 6 个点 7 个点的情况。
而权重只会影响某个组合出现的概率,并不会影响总数。
如果是要做精准测试的代码函数流转关系的话,这个方式恐怕有点难,你想想 30 个类就已经这样的,正常的项目别说 30 个了,300 个类打底吧。

是的,你这个局部我倒是没有考虑到,不过当前我们的基本上在 30-50 间,感觉还好,目前还在建模阶段
这块有什么好的经验可以分享下的,😀

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册