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

How to find the shortest path that pass through a group of Sets?

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

例如，假设有以下4个无序集合：
A=abcdefg
B=cd
C=abch
D=defi

最短路径大小为11.

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

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

请提供一种算法来找到所描述的最短路径。
谢谢！

你有一个图表：

您正在寻找覆盖所有节点的最短路径。那是travelling salesman problem的一个变体，不需要回到开始。

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

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

问题中不清楚的是：如果一个集合是另一个集合的超集，你会怎么做？我假设您想将这两个集合分开，这就是我写的原因：'the edge A-B exists if A and B have an intersection but are not subset one of another'。对于 TSP，如果边不存在，只需在集合 A 和 B 之间使用无限距离。这适用于 subsets/supersets.
路径是有序的（根据路径的定义），但集合是无序的。这就是为什么这不是最短常见超弦问题的（微不足道的）变体。一个字符串是有序的，一个set no.
TSP 的想法对于上面定义的距离也不太适用，因为：
- 距离的定义不好：当交集增长时，距离应该严格减少。一个解决方案是 max(len(S)) - len(A ^ B).
- 更重要的是：不允许在集合的 "both sides" 中使用相同的字母。例如。 "abc" 不能与 "bcd" 的距离为 1，与 "eb" 的距离为 2，因为如果您选择路径 "a-bc-d"，则边缘 "abc" - "eb" 不存在了。也许贪婪的选择会成功，但我不确定。

的变体