algorithm - 探索一种算法以找到包含某些项目的最小链

Question

抱歉，我想不出算法的名称或以下算法的问题。我将说明问题，然后说明我尝试过的方法，也许有人可以指出正确的方向。

假设您有一袋元素(未排序，允许重复)。实际上，袋子可能包含 2-20 件元素，以防这种放松有帮助。

目标是找到最小长度的链(有序链接列表，以防我们对链有不同的概念)，它以任何顺序包含包中的所有元素。

一条链由一个起始 token (不在包中)和任意数量的项目组成，然后是一个结束 token (也不在包中)。

链是通过将 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 个子问题，即开始 token 端和结束 token 端。直到子问题 1 的数据结构的第一个标记是开始标记并且子问题 2 的最后一个标记是结束标记，增长链以便我们试图尽快找到停止条件(开始或结束标记取决于在子问题上)同时也试图尽快用完袋子里的东西。这可能不太好，因为每个子问题都必须就包中还剩多少元素需要包括在内相互沟通。

有人在任何地方遇到过这个问题吗？关于如何改进(或开始正确工作)这个算法有什么想法吗？这是我正在解决的一个真正的问题，它是一个更大系统的智能部分，而不是玩具问题或家庭作业问题。

编辑

抱歉，我今天没玩电脑。我将尝试发布一个示例解决方案，它不是太琐碎，但也不是太复杂以至于看不到。

给定:

1. 包 = {A, B, C, D}(为了举例，我把它做成一个集合，但每个项目可以出现不止一次)
2. /= 开始 token
3. \= 结束 token

4. 三元组(三元组):为了命名简单，我将它们标记为 a-g。小写字母在问题中没有实际作用。

   (/,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,\)。
这是包含包中所有元素的最短链，如果您同时计算开始和结束 token ，则长度为 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,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 种状态，这应该是可以管理的。