探索一种算法来查找包含某些项目的最小链

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} (为了示例,我把它设为一组,但每个项目可以出现多次)
2. / = Start Token
3. \ = End Token

4. 3元组(三元组):为了简化命名,我将它们标记为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

此状态对应于看起来像 Start 的链，?,?,?,...,?,b,cie b 和 c 是最近的 2 个元素。

数字 m 是一个位字段，表示链中哪些其他元素已被访问。换句话说，当且仅当链包含包中的第 i 个元素时，m 的位 i 才为 1。

找到最短链的算法是：

1. 令 S = 由具有起始标记的所有元组组成的状态集。（所有这些状态的链长度都相同，均为 2）
2. 对于从 3 开始的每个链长度 y，遍历 S 中的所有状态，并尝试使用适当的元组将状态扩展为长度 y。如果可能的话，将扩展状态添加到集合 S。
3. 如果位字段 m 最终以所有位集结束，则仅允许添加带有结束标记的元组。

如果您曾经设法添加包含最终状态的元组，那么您就找到了包含所有元素的最短链。

对于包里的 N 件物品，大约有 2^NNN 种状态，这应该是可以管理的。