探索一個算法來找到包含某些項目的最小鏈條

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個狀態應該是可以管理的。