A *啓發式法求解N-puzzle的比較

Question

我想用三種不同的啓發式函數來解決使用A *算法的N-puzzle問題。我想知道如何比較每種啓發式的時間複雜性。我使用的啓發式是：曼哈頓距離，曼哈頓距離+線性衝突，N-max交換。特別是對於8個難題和15個難題。

Answer 1

一般來說，NP難以找到最短的解決方案，所以無論使用哪種啓發式方法，都不太可能找到它們之間複雜度的差異，因爲您不會證明任何界限的緊密性。

如果您將自己限制在8個難題或15個難題，那麼具有任何容許啓發式的A *算法將在O（1）時間內運行，因爲存在有限（儘管數量很多）的棋盤位置。

Answer 2

正如@Harold在他的評論中所說的，比較啓發函數時間複雜度的方法是通過實驗測試得出的。在你的情況下，爲8-puzzle和15-puzzle生成一組n隨機問題，並使用不同的啓發函數解決它們。事情需要注意的是：

1. 的比較將始終取決於幾個因素，如硬件expecs，編程語言，實現算法時，你的技能，...

2. 一般來說，一個更明智的啓發式方法總是會比不那麼知情的方法擴展更少的節點，並且可能會更快。

最後，以三個啓發式比較每個問題集，我會建議，平均運行時間的圖形（重複例如5次，每次的問題），其中：

1. 的問題在x軸上按難度排序。
2. 運行時間在每個啓發函數的y軸上（如果不能輕易看到替代方案之間的差異，則可能以對數形式表示）。

和具有探索狀態數量的類似圖形。