在給定一些約束的情況下，我可以使用什麼算法來驗證可以連接的節點列表？

我正在構建一個遊戲，玩家可以隨機獲得一組節點，並嘗試通過按照特定順序放置節點來構建最長的列表。每個節點都有零個或多個連接，這些連接必須與列表中下一個節點的至少一個連接相匹配。例如，一個節點可能是這樣的：在給定一些約束的情況下，我可以使用什麼算法來驗證可以連接的節點列表？

    +--+ 
left connections A B right connections 
        B C 
        +--+

以上節點（例如節點）可以與任何這些節點的連接：

+--+ 
C | This node can connect to the right side of the example node (matches C) 
D | 
+--+ 

+--+ 
B K This node can connect to the left side of the example node (matches A) 
L A This node can connect to the right side of the example node (matches B) 
+--+

因此，考慮到這三個節點，球員可能在列表中匹配它們如下：

+--+  +--+  +--+ 
B K  A B  C | 
L A -A- B C -C- D | 
+--+  +--+  +--+

我需要驗證玩家的選擇。玩家不必首先按照正確的順序選擇節點，但是他們的最終選擇必須能夠連接成一個連續的線性列表。因此，給定一個無序節點數組（玩家選擇），我需要將節點形成一個像上面這樣的有效列表，或者向玩家顯示一個錯誤。

我可以蠻力驗證，但我希望找到一個更優雅的解決方案。

來源

2016-04-02 Stephen

這些套件有多大？如果不是這樣，比蠻力更精細的東西可能不值得麻煩。對於大集合，動態編程可能是合適的。 –

@ScottHunter玩家的選擇可能是5或6個節點。 – Stephen

從沒有周期的情況下，從左到右追蹤路徑是不夠的？即你只能在一個方向上（右）在一個鏈接'-A-'上移動，你只能向上/向下/向右移動。如果您擔心用戶會構建多條死路的路徑，那麼您真的需要首先遍歷一棵樹，其中至少有一片葉子到達目的地「一側」。如果你想要最短路徑，我想dykstra的算法可能在這裏工作（但我對它有點模糊）。 –

後散了，有的預計算的問題，可能是這樣的：

Given a graph determine whether it has a path traversing all nodes

這正是the Hamiltonian problem。您可以閱讀有關該主題的研究或分析圖的某些結構（對於某些特殊的圖具有簡單的解決方案），但通常情況下，我知道的最佳解決方案是指數型。

但是，直截了當的暴力解決方案是通過所有排列（n!），並檢查它是否形成正確的路徑（*n）。這種方法導致O(n*n!)漸近。實際上，這意味着n應該最大爲12亞秒級檢查和n=15需要幾個小時檢查最壞的情況。輕微優化 - 逐漸形成路徑並檢查每個新頂點 - 最糟糕的情況下會導致O(n!)時間，因此在最差的情況下可以在幾秒鐘內檢查n=13，甚至更快的平均速度因爲很多錯誤的道路將在早期階段被削減。

你可以走得更遠，並利用動態編程。讓我們定義isProperPath[S][i]（其中S是節點子集的位掩碼，i是該子集的某個節點）作爲對應於存儲由與最後一個節點i對應的子集的節點構成的路徑的值的值。那麼很容易根據當時的S用更少的元件子集的所有值來計算isProperPath[S][i]：

isProperPath[S][i] = false; 
for (j in S) { 
    if (isProperPath[S\i][j] && hasConnection(j, i)) 
     isProperPath[S][i] = true; 
}

通過遍歷所有對S和i在S升大小，我們將計算所有值的順序。答案是肯定的當且僅當isProperPath[A][i] = true其中A是整個給定的集合和i-任何節點。

時間複雜度爲O(2^n*n^2)，空間複雜度爲O(2^n*n)，因爲有2^n*n個值，並且需要O(n)根據以前的值計算值。該算法使得有可能利用大約400M比特或50Mb在亞秒時間內檢查大小高達24的組。

來源

2016-04-19 11:11:25 sbeliakov

在給定一些約束的情況下，我可以使用什麼算法來驗證可以連接的節點列表？

回答

相關問題