探索一个算法来找到包含某些项目的最小链条

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使它例如起见一组，但每个项可以出现一次以上）
2. / = Start Token
3. \ = End Token

4. 3-元组（Triples）：为了简化命名，我将它们标记为ag。小写字母在问题中没有实际功能。

   (/,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，如果它实际存在。我希望我的问题陈述现在更有意义。

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 

这种状态可能符合链看起来像开始，，，，...，，B ，C。 即b和c是2个最近的元素。

数字m是一个位域，表示链中已访问过哪些其他元素。换句话说，当且仅当链包括袋中的第i个元素时，m的位i是1。

的算法来寻找，然后在最短的链条是：

1. 令S =套件包括有开始令牌的所有元组的状态。 （所有这些状态将具有相同的链长度2）
2. 对于从3向上的每个链长y，遍历S中的所有状态并尝试通过使用适当的元组来扩展状态以具有长度y。如果可能，请添加扩展状态以设置S.
3. 如果位域m将以所有位设置结束，则只允许添加带有结束标记的元组。

如果您曾设法添加包含结束状态的元组，则您已找到包含所有元素的最短链。

对于包中的N件物品，大约有2^N.N.N个状态应该是可以管理的。