使用 A 演算法解決 8-puzzle 問題

問題定義 ：

8 拼圖是一個由 3 x 3 網格（包含 9 個方格）組成的簡單遊戲。其中一個方塊是空的。目標是移動到不同位置的方塊並使數字顯示在目標狀態中。

給定 8-puzzle 遊戲的初始狀態和最終狀態，找到從最初狀態到達最終狀態的最具成本效益的路徑。

初始狀態 ：

_ 1 3
4 2 5
7 8 6

最終狀態 ：

1 2 3
4 5 6
7 8 _

啟發式假設 ：

讓我們考慮當前和最終狀態之間的曼哈頓距離作為此問題陳述的啟發式。

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

總成本函式 ：

所以總費用函式 f(n) 由下式給出，

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

示例問題的解決方案 ：

首先，我們找到從初始狀態到達最終狀態所需的啟發式值。成本函式 g(n)= 0，因為我們處於初始狀態

h(n) = 8

獲得上述值，因為當前狀態下的 1 與最終狀態下的 1 相距 1 個水平距離。同樣適用於 2，5，6。_ 距離 2 個水平距離，距離 2 個垂直距離。所以 h(n) 的總值是 1 + 1 + 1 + 1 + 2 + 2 = 8.總成本函式 f(n) 等於 8 + 0 = 8。

現在，找到了可以從初始狀態到達的可能狀態，並且我們可以將 _ 向右或向下移動。

所以移動這些動作後得到的狀態是：

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

再次使用上述方法為這些狀態計算總成本函式，結果分別為 6 和 7。我們選擇了最低成本的狀態，即狀態（1）。下一個可能的移動可以是左，右或下。我們不會像之前在那個狀態那樣向左移動。所以，我們可以向右或向下移動。

我們再次找到從（1）獲得的狀態。

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

（3）導致成本函式等於 6，（4）導致 4.此外，我們將考慮（2）之前獲得的成本函式等於 7.從中選擇最小值導致（4）。下一個可能的移動可以是左，右或下。我們獲得狀態：

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

對於（5），（6）和（7），我們分別得到等於 5,2 和 4 的成本。此外，我們以前的狀態（3）和（2）分別為 6 和 7。我們選擇了最小成本狀態，即（6）。接下來可能的移動是 Up，Down 和 clear Down 會導致我們進入最終狀態，導致啟發式函式值等於 0。