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

Question

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

例如，让以下4个无序集： A = ABCDEFG B = CD C = ABCH d = DEFI

最短路径大小为11。

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

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

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

Answer 1

这个问题可以简化为Shortest common superstring problem的变种

Answer 2

你有一个图表：

• 节点是集合;
• 如果A-B和A有一个交集但不是另一个的子集，则存在边缘B;
• 如果边缘A-B存在，距离A-B是A联合B的大小。

您正在寻找涵盖所有节点的最短路径。这是travelling salesman problem的一个变种，无需回到起点。

一些阅读：What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?

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

1. 问题中不明确的是：如果一个集合是另一个集合的超集，你会怎么做？我假设你想把这两组分开，这就是为什么我写道：'如果A和B有一个交集但不是另一个的子集，则边缘A-B存在'。对于TSP，如果边缘不存在，只需在集合A和B之间使用无限距离。这适用于子集/超集。
2. 路径是有序的（根据路径的定义），但是这些集是无序的。这就是为什么这不是最短共同超弦问题的（微不足道）变化。字符串是有序的，一组是否。
3. TSP的想法不能很好地适应上面定义的距离，因为： 距离的定义不好：交叉点增长时距离应严格减小。解决方案是max(len(S)) - len(A ^ B)。 更重要的是：您不能在该组的“两侧”使用相同的字母。例如。 “abc”不能与“bcd”相距1，距离“eb”的距离为2，因为如果选择路径“a-bc-d”，则边缘“abc” - “eb”不会t再也存在了。也许贪婪的选择可以解决问题，但我不确定。