5

抱歉，我无法为以下算法提出算法或问题的名称。我会陈述问题，然后我已经尝试过，也许有人可以指出我正确的方向。

想象一下，您有一袋物品（无序，允许重复）。在实践中，袋子可能包含 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-Tuples（三元组）：为了命名简单，我将它们标记为 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，如果它确实存在。我希望我的问题陈述现在更有意义。

4

1 回答 1

2

由于您最多只有 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 个状态，它们应该是可以管理的。

于 2012-10-21T17:54:06.787 回答