為什麽八數碼問題用a*算法求解合適

其實A*算法也是壹種最好優先的算法只不過要加上壹些約束條件罷了。由於在壹些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是幹這種事情的！我們先下個定義，如果壹個估價函數可以找出最短的路徑，我們稱之為可采納性。A*算法是壹個可采納的最好優先算法。A*算法的估價函數可表示為：f'(n)=g'(n)+h'(n)這裏，f'(n)是估價函數，g'(n)是起點到節點n的最短路徑值，h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這壹點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可采納的。我們說應用這種估價函數的最好優先算法就是A*算法。舉壹個例子，其實廣度優先算法就是A*算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先算法是壹種可采納的。實際也是。當然它是壹種最臭的A*算法。再說壹個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計壹個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個算法越好。這就是為什麽廣度優先算法的那麽臭的原因了，誰叫它的h(n)=0，壹點啟發信息都沒有。但在遊戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但算法的準確性就差了，這裏就有壹個平衡的問題。