如何找到通过一组集的最短路径

Question

我有一个算法问题，我有许多无序的元素集，我需要找到通过所有这些集合的最短路径（集合的有序组合）。可能有数千组。

例如，让以下4个无序集：
a = abcdefg
B = CD
C = ABCH
d = defi

最短路径大小为 11 。

一种可能的解决方案是：
P = CADB = habcgdeficd
| P | = 11

注意，集合可以与路径中的相邻集共享元素！
也可能存在属于不同集合的重复元素（如上所述：'c'和'd'在 p 中重复，通过添加 b CAD ）。

请使用算法建议找到如上所述的最短路径。
谢谢！

Answer 1

这个问题可以简化为最短的常见超音问题的变体

Answer 2

您有图形：

• 节点是集合;
• 如果 A和 B具有相交，但不是子集
• EDGE A-B存在；
• 如果EDGE A-B存在，则距离A-B是A联合B的大小。

您正在寻找涵盖所有节点的最短路径。这是旅行推销员问题的变体，而无需重新开始。

一些阅读：旅行推销员问题（TSP）的问题名称是什么，而无需考虑返回起点？

编辑：我尝试总结评论和我的答案中讨论的内容。

1. 问题不清楚的是：如果一套是另一个的超集，您该怎么办？我以为您想将这两套分开，这就是为什么我写道："如果A和B有一个相交，但不是另一个彼此的子集。对于TSP，如果边缘不存在，则只需在集合A和B之间使用无限的距离即可。适用于子集/超集。

2. 路径被排序（按路径的定义），但集合是无序的。这就是为什么这不是最短常见超声问题的（微不足道）变化的原因。订购了一个字符串，一组no。

3. TSP的想法与上面定义的距离都无法很好地工作，因为：

   • 距离的定义不好：当相交生长时，距离应严格降低。解决方案将是max(len(S)) - len(A ^ B)。
   • 更重要的是：不允许您在集合的"双方"上使用相同的字母。例如。" ABC"不能距离" BCD"和距" EB"的距离1的距离，因为如果您选择路径" A-BC-D"，则是边缘" ABC" - " EB"t已经存在了。也许贪婪的选择会解决问题，但我不确定。