C＃RushHour迭代加深，優化

我必須使用迭代加深搜索來解決rushhour問題，我爲每個移動生成新節點，一切正常，除了計算所有內容需要太多時間以及原因之外是我生成重複的節點。任何想法如何檢查重複？C＃RushHour迭代加深，優化

首先我從根開始，然後有一種方法可以檢查每輛車是否可以移動它，如果是，則從當前節點創建新節點，但將有效移動的一輛車替換爲新車有新的座標。

問題是，算法越深入，重複移動的次數越多。

我試圖不更換汽車，但使用了與根節點中使用的相同的集合，但汽車僅在一個方向上移動。

我認爲我需要以某種方式配合汽車收藏，但不知道如何。

The code

任何想法如何停止生產重複？我是新來的C＃（閱讀幾個教程，然後已經使用了2天），所以你可以告訴我我做錯了什麼，或者我不應該做什麼？

來源

2013-03-24 Jan

如果你想堅持迭代加深，那麼最簡單的解決方案可能是建立一個哈希表。然後，所有你需要每一個新的節點做的是一樣的東西

NewNode = GenerateNextNode 
if not InHashTable(NewNode) then 
    AddToHashTable(NewNode) 
    Process(NewNode)

或者，在RushHour可能的位置（節點）的數量相當小（假設你使用的是標準的電路板尺寸），並有可能相當容易地生成所有可能的（並且不可能的）電路板。然後，而不是迭代加深，您可以從「解決方案」狀態開始並向後工作（勾選所有可能的「父」狀態），直到達到開始狀態。通過在可能的狀態表上工作，您永遠不會生成重複項，並且一旦訪問了每個狀態標記，就永遠不會重新訪問狀態。

來源

2013-03-24 22:47:49 Penguino

謝謝，我已經試過，但它沒有工作 – Jan 2013-03-24 22:57:06

你能告訴我們你試過了什麼，爲什麼它不起作用？（請注意，我提出的替代解決方案對我來說確實有效）。 – Penguino 2013-03-24 23:11:05

您也可以同時從開始狀態搜索轉發，並從結束狀態向後搜索（可以考慮廣度優先搜索，但實際併發也可以）。一旦兩個搜索在中間相遇，您就可以得到解決方案，從而將必要的搜索樹深度減半。 – Daniel 2013-03-24 23:18:02

C＃RushHour迭代加深，優化

回答

相關問題