作者：唐古拉风情2502931431 | 来源：互联网 | 2023-02-12 10:06
我现在有很多个（几百个）链表，长度多数在3-10之间，是由一个很庞大的树上提取的路径，有以下限制：链表的第一个元素是树根，下一个元素是底下一层的一个节点，但是最后一个元素不一定是叶结点，即
我现在有很多个（几百个）链表，长度多数在3-10之间，是由一个很庞大的树上提取的路径，有以下限制：
链表的第一个元素是树根，下一个元素是底下一层的一个节点，但是最后一个元素
不一定是叶结点，即路径从树根开始，但是不一定完整。
如：
A->B1->C2->D3
A->B1->C2->D1->E7->F8->G2
A->B2->C9......
A是根节点，B,C,D,E分别是第2、3、4层的节点
现在要完成的算法是：
在所有的这些链表中，找到两个最匹配的，即，从根节点开始，相同路径最长的，然后对着两个链表进行评估（评估函数已实现），之后进行两种可能的操作：
1、评估成功：将两个链表合并，即合并成一个链表，其路径为原两表的共同路径，这个操作将影响到以后的评估函数，之后找下一组最佳匹配的链表。
2、评估失败：将两个链表不动，找下一组最佳匹配的链表。
算法的结束条件是：
找不到评估函数成功的匹配。
多谢了，时间复杂度不要太高。
8 个解决方案
还是不太明白，举个实例说明一下。特别是“这个操作将影响到以后的评估函数”
Sorry，我没有讲详细
Node的结构式这样的：(SomeClass data, int eval)
EVAL函数是对整个链表的每个Node使用公式计算的值，对整个链表有意义。
当最长匹配的两个链表找出来以后，对链表lx,链表ly和他们的合并链表merged进行评估，如果EVAL(merged)>EVAL(lx) && EVAL(merged)>EVAL(ly)，则将lx,ly从集合中取出来，然后将merged链表放进去，merged的长度相当于原来lx,ly的公共部分，但是Node.eval和原来并不一样的。这是集合生了变化，重复选择最佳匹配的两个链表。
注意的是这些链表集合并不是静态的，每次找到的最佳匹配并不一定执行合并，可能不合并就把那lx,ly放回去。
多谢大家乐。
这个问题真难呵...我提些建议吧：
1 从公式入手，看看问题有没有特殊性，如果能从数学角度解决是最好的了。
2 采用人工智能的方法，这个问题带有明显的“遗传”特征，可以考虑用遗传算法。
3 解决这个问题需要很强的理论基础，你可以考虑找在校的优秀研究生帮忙。
那么你就是问怎么挑出最长匹配的和合并以后怎么继续这两个问题么？
如果是这样就简单。法宝----排序！随便用什么办法排序只需要O(n*logn*k)的时间。排序以后你用遍历的算法在O(n*k)就可以找出最优匹配（只需要遍历一遍），然后用二分查找把你合并的那个链表塞进去要O(nlogn*k)的时间（k是链表的最长长度），这是用数组的，用更好的搜索结构可能还可以加快。这样，你的整个算法需要的时间肯定是O(n^2*logn*k)。按你说的那个数（n=300,k=10），肯定能在1秒以内算出来。
楼上说的很有对，但他的问题是先挑出最长匹配后再判断是否是最佳匹配，最长匹配不一定是最佳匹配。而且难的是：如果是最佳匹配则合并成新的链表，但新链表的长度和各节点的权都会改变，因此会影响到其他的匹配，故每次找到的最佳匹配并不一定执行合并。所以对此可能要搜了。不过楼上的方法有可能改进到比较好的近似吧？能用遗传算法的话会使问题得到好的解决。
1。他不是说他已经有了EVAL了么？
2。不合并不就等于不动么？建一个堆数组，一开始就把每两个之间匹配的长度存进去。
heap a[10]; /* 长度最大是10，多放一个让下标从1开始 */
stack b;
遍历的时候，每一个碰到的就分放到数组的对应项里
a[匹配长度].insert(现在的那个链表编号);
好，判断的时候，从最长的a开始，计算他的eval，如果不行，push到b里面，再换下一个，直到可以为止，这个最多是O(n*time(EVAL()))的时间吧。
可以了以后，再用binsearch给他排到适当的位置，把后面的往后挪。这个是O(n)的时间。
这时把b里面的pop出来，insert到堆里面，再把a里面有那两个用掉的链表的项去掉，并把堆里那些下标变了的改掉（因为是顺序加一所以不会影响排列关系），这个是O(nlogn)的时间。
现在只需要研究那个新生成的和它相邻的链表之间的匹配长度关系，把这两个匹配长度添加到a就可以了，是O(logn)的时间。
所以总共需要MAX(O(nlogn),O(n*time(EVAL()))的时间。(上面因为都是用给这个链表分配的一个下标来操作，所以不涉及到k）
heap a[10]; /* 长度最大是10，多放一个让下标从1开始 */
厄，这个是不小心打错了，不要当真。
heap a[10]; /* 长度最大是10 */
是这样就对了。
还有，刚才说的是一步的时间，总共有多少步？我看很难说会超过O(n)把（虽然我也没法证），所以估计MAX(O(n^2logn),O(n^2*time(EVAL)))是比较合理的。
京公网安备 11010802041100号