探索一种算法以找到包含特定项的最小链。

Question

抱歉，我无法为下面的算法想出一个算法或问题的名称。我将陈述问题，然后说明我所尝试的内容，也许有人可以指引我正确的方向。

假设你拥有一个物品袋（无序，允许重复）。在实践中，袋中可能包含2-20个物品，以此来放松问题。

目标是找到包含袋中所有任意顺序物品的最小长度链（有序链接列表，如果我们对链的概念有不同）。

链由起始标记（不在袋中），任意数量的物品和结束标记（也不在袋中）组成。

链通过拼接n元组（顺序重要）形成，进一步放宽，让我们说n值对于所有元组都是相同的。在实践中，我正在处理n = 3. 如果它们具有重叠元素，则可以“混合”链，而不是连接它们。例如，考虑（a,b,c）和（c,d,e）。 可以将它们连接为（a,b,c,d,e）。同样，（a,b,c）和（b,c,d）可连接为（a,b,c,d）。某些元组可能在第一个位置具有起始标记，某些标记可能在最后一个位置具有结束标记，这当然允许存在问题的解决方案。

因此，在一般情况下，似乎不可能得到问题的精确解。需要某种优化算法才能获得“好”的问题解决方案。我可以接受“好”的解决方案。

我开始使用一种贪婪方法，其中在第一遍中，您找到包含物品中最多元素的元组，并任意打破平局。创建一个保存到目前为止构建的链的数据结构，并将所选元组放入此数据结构中。将问题分成2个子问题：起始标记侧和结束标记侧。在子问题1的数据结构的第一个标记为起始标记且子问题2的最后一个标记为结束标记之前，增加链，以便尽快找到停止条件（根据子问题而定的起始或结束标记），同时尽快耗尽袋中的内容。这可能不是很好，因为每个子问题都必须相互通信，以了解需要包括在袋中的剩余物品数量。

有人在任何地方看到过这个问题吗？有什么想法来改进（或使这个算法正确工作）？这是一个真正的问题，我正在处理它，它是一个更大系统的智能部分，不是玩具问题或家庭作业问题。

编辑：

抱歉，我今天离开电脑了。我将尝试发布一个示例解决方案，它既不是太琐碎，也不是太复杂。

给定：

1. Bag = {A, B, C, D} (I make it a set for the sake of example, but each item can appear more than once)
2. / = Start Token
3. \ = End Token

4. 3-Tuples (Triples): I label them a-g for simplicity in naming. The lowercase letters have no actual function in the problem.

   (/,A, E) a
   (/,C, D) b
   (/,G, H) c
   (D,B, A) d
   (C,G, H) e
   (B,A, \) f
   (G,H, \) g
   

解决方案：如果我们将 b、d 和 f 链接在一起，我们得到 (/,C,D,B,A,\)。这是包含所有元素的最短链，如果你计算开始和结束标记，它的长度为6。通常情况下，如果最短路径确实存在，则其长度为 |BAG|+2。希望我的问题陈述现在更加清晰明了。

- demongolem

---

抱歉，我无法理解问题。您能添加一个简单的测试用例和最优解吗？ - amit

在我看来，“允许重复”是无意义的。对于一对双胞胎，1）如果它们具有相同的进出路径，则其中一个是多余的。2）如果它们具有不同的路径，则节点不能相同。此外：如果它们是重复的，则应合并/组合节点（及其路径）。 - wildplasser

如果我有一个能解决你的问题的盒子，我可以用它来解决 http://en.wikipedia.org/wiki/Hamiltonian_path 吗？ - mcdowella

在多次重新阅读原问题后，确实看起来OP想要一种哈密顿路径。但是：允许多次访问节点，因此它变成了一种中国邮递员问题。 - wildplasser

Answer 1

由于您最多只有20个项目，我认为您可以在合理的时间内计算出精确的解决方案（例如，在一分钟内）。

一种方法是使用动态规划，其中状态由以下内容给出：

A) a 20 bit number m (which will represent which items have been visited so far)
B) a number b in the range 1..20 
C) a number c in the range 1..20

这个状态对应的链看起来像Start,?,?,?,...,?,b,c。也就是说，b和c是最近的两个元素。

数字m是一个位域，表示在链中访问了哪些其他元素。换句话说，如果袋子中包含第i个元素，则m的第i位为1。

找到最短链的算法如下：

1. 令S = 所有具有起始标记的元组的集合。（所有这些状态的链长度都为2）
2. 对于从3开始的每个链长y，请遍历S中的所有状态，并尝试使用适当的元组将状态扩展到长度y。如果可以，请将扩展后的状态添加到集合S中。
3. 只有在位域m的所有位都被设置时，才允许添加带有结束标记的元组。

如果您成功添加了一个包含结束状态的元组，则已经找到了包含所有元素的最短链。

对于袋子中的N个物品，大约有2^N.N.N种状态，应该是可以处理的。

- Peter de Rivaz

---

我一直在心里想，既然我的包里有最多的物品，动态规划可能是一个不错的方法。我需要再仔细思考一下，并回复你。我相信我的原始问题是我从错误的角度来看待问题。 - demongolem

会给你点赞。我成功地用算法的一般思路解决了上面的例子。可能还有一些边缘情况需要处理，例如如果我们永远无法到达结束标记会发生什么，但这些都是小问题。我认为它将适用于所有情况，我必须继续在提供给我的三元组集合上进行测试，以确保它能正常运行。 - demongolem

我认为另一种看待这种方法的方式是，它从起点到终点进行广度优先搜索，成本是访问的节点总数。因此，您可能需要考虑使用http://en.wikipedia.org/wiki/Bidirectional_search或A*算法。 - mcdowella

其实我想了想，我认为双向搜索只是将节点分成两半并访问这两个部分的所有节点，而具有明显启发式的A*搜索只是广度优先搜索的更昂贵版本，所以划掉那个 - 抱歉。 - mcdowella