8拼圖：漢明和manahttan啓發式考慮「空白」？

Question

我有一個非常簡單的問題。

我正在8的益智（8號（1至8）+空白（= 0））

當計算的漢明距離（在錯誤的位置編號）和曼哈頓距離（距離水平面+垂直在開始和結束位置之間）我應該考慮「空白」空間來計算結果嗎？

例如..

|7 2 4| 
|5 _ 6| 
|8 3 1| 

與目標狀態

|_ 1 2| 
|3 4 5| 
|6 7 8| 

什麼是正確的嗎？

• 漢明距離= 8（每數不到位）或9（也0 =空白被認爲）
• 曼哈頓距離（距離（7），距離（2），距離（4），.. ）= 3（= 1 + 2）+1（= 1 + 0）+2（1 + 1）+2（2 + 0）+0（空白）+3（1 + 2）+2（2 + 0） ）+ 3（1 + 2）+ 3（2 + 1） - >不考慮空白是18，空白（+2）是20.什麼是正確的？

謝謝

Answer 1

如果你想啓發式可以受理，那麼你不應該算在空塊。

例如

|1 _ 2| 
|3 4 5| 
|6 7 8| 

真正的答案是1，但曼哈頓的距離是2，如果你計算空白的瓷磚。 這不能是可接受的啓發式。