A *算法解決8瓦滑動拼圖的時間

Question

想知道是否有人可以幫我解決一些我目前正在爲uni工作的代碼。這是一個我正在編碼的滑動拼圖遊戲，我已經實現了一個具有曼哈頓距離啓發式的A *算法。目前，解決這個難題的時間可能會從幾個毫秒到幾十秒不等，對於某些配置。我想知道的是，如果這個時間範圍是我應該期待的？

我從來沒有真正做過任何AI之前，我不得不在飛行中學習，所以任何幫助將不勝感激。

Answer 1

我想知道的是，如果這個範圍的時間是我應該期待的？

從您提供的信息中找出來有點難。如果你可以描述你是如何實現A *的，或者你分析了你的應用程序，並且需要特定的緩慢區域的幫助，這將有所幫助。

有一點需要注意的是可能會加快您的平均解決時間：任何n-tile拼圖的一半起始位置都不會導致解決方案，因此您可以立即快速排除某些配置。例如，你解決不了的8瓷磚拼圖看起來像這樣：

1 2 3 
4 5 6 
8 7 . 

要知道爲什麼，請注意，因爲空白空間具有清盤迴到起點，總體數量「向上」 /「向下」移動必須相等，「左」/「右」移動的總數也一樣。這意味着整體移動次數必須均勻。

但是這裏的7/8換位是一個從開始的謎題離開，而不改變空白位置！所以這個難題不能解決。 （但是，如果我們做了兩次換位，那麼它又可以解決了。）

Answer 2

就像你應該知道的，你不能指望任何一般的時間。它依賴於代碼本身，特別是在你的實現在樹中走向何方，以及如果你的代碼可以使用處理器特性的優點。

對於調試，我將保存或打印出來（但這需要時間！）在你的樹的哪個級別。

另外請記住，權重是非常重要的。例如： -

123 
4 6 <- your final state 
789 

  213        1 3 
To change 4 6 is much more expensive than 426 
      789        789 

我希望幫助。

Answer 3

顯然，這不僅取決於您的硬件，還取決於您的實施。然而，這並不是衡量表現的好方法：你想要做的是確定啓發式的有效分支因子，而不是其他一些非啓發式方法的實際分支因子。我不想說太多，因爲這是一個家庭作業問題，但是如果記憶服務的話，Russel和Norvig會在滑動拼圖本身的背景下進行轉化......第三章，也許呢？ （我的R + N不在手邊。）