????源代碼在最后。

????接下來會(huì)用Python來實(shí)現(xiàn)A*算法求解八數(shù)碼問題。

????八數(shù)碼就是在3*3的棋盤中有8個(gè)數(shù)碼（數(shù)字塊）和一個(gè)空格，只有與空格相鄰的數(shù)碼能移動(dòng)到空格位置。

????目的就是從初始狀態(tài)通過移動(dòng)數(shù)碼到達(dá)指定狀態(tài)。那么首先就設(shè)置一個(gè)初始狀態(tài)吧，以免還要輸入。目標(biāo)狀態(tài)就是上面那張圖的狀態(tài)。

代碼

????代價(jià) = 從初始狀態(tài)到當(dāng)前狀態(tài)的代價(jià) + 從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的估計(jì)代價(jià)

????那么，從初始狀態(tài)到當(dāng)前狀態(tài)的代價(jià)就用移動(dòng)的步數(shù)表示，從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的估計(jì)代價(jià)就用所有數(shù)碼與它們的最終位置的曼哈頓距離表示。比如說數(shù)碼2當(dāng)前位于（2，2），而它的目的位置是（0，1），所以曼哈頓距離就是abs(0-2)+abs(1-2)=3。

????好了 ，接下來建立代碼的初始狀態(tài)和目標(biāo)狀態(tài)：

????goal_dic用于把目標(biāo)狀態(tài)的數(shù)碼對(duì)應(yīng)到位置，以便計(jì)算曼哈頓距離。下圖就是曼哈頓距離的計(jì)算：

????????這兩個(gè)函數(shù)是用來輸出狀態(tài)和復(fù)制狀態(tài)的：

????獲取空格位置及四個(gè)方向上的移動(dòng)：

????獲取指定狀態(tài)下可以調(diào)用哪些移動(dòng)函數(shù)，Start是為了統(tǒng)一節(jié)點(diǎn)信息的，因?yàn)槊總€(gè)節(jié)點(diǎn)都有一個(gè)操作屬性，表示從其父節(jié)點(diǎn)到達(dá)此節(jié)點(diǎn)要用何種操作。當(dāng)然，最重要的是輸出操作名。

????搜索的結(jié)果就是建立一棵搜索樹，如果成功到達(dá)目標(biāo)狀態(tài)，則返回目標(biāo)節(jié)點(diǎn)，然后遍歷輸出就可以知道如何操作可以到達(dá)目標(biāo)節(jié)點(diǎn)了。

????已經(jīng)擴(kuò)展的節(jié)點(diǎn)保存在一個(gè)隊(duì)列中，最好是使用優(yōu)先隊(duì)列。我是要做作業(yè)才剛學(xué)的Python，所以就用列表表示隊(duì)列了，然后用一個(gè)函數(shù)找代價(jià)最小的元素。那個(gè)toInt是用來將狀態(tài)轉(zhuǎn)換為整數(shù)值然后作為已經(jīng)訪問過了的表的鍵的，原因嘛，就是Python不允許用列表作為哈希表的鍵（我手動(dòng)哈希還不行嗎^_^）。：

????接下來是主角登場(chǎng)，A星算法的主循環(huán)：

????還有類似主函數(shù)的調(diào)用。reverse用于反轉(zhuǎn)路徑，因?yàn)樗阉鞣祷氐氖悄繕?biāo)節(jié)點(diǎn)，鏈?zhǔn)欠吹模?/p>

結(jié)果

源碼

# 初始狀態(tài)

init_state = [

[1, 8, 7],

[3, 0, 5],

[4, 6, 2]

]

# 目標(biāo)狀態(tài)

goal_state = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 0]

]

# 目標(biāo)狀態(tài) 值-位置表

goal_dic = {

1:(0,0), 2:(0,1), 3:(0,2),

4:(1,0), 5:(1,1), 6:(1,2),

7:(2,0), 8:(2,1), 0:(2,2)

}

# 輸出狀態(tài)

def PrintState(state):

for i in state: print(i)

# 復(fù)制狀態(tài)

def CopyState(state):

s = []

for i in state: s.append(i[:])

return s

# 獲取空格的位置

def GetSpace(state):

for y in range(len(state)):

for x in range(len(state[y])):

if state[y][x] == 0: return y, x

# 獲取空格上移后的狀態(tài)，不改變?cè)瓲顟B(tài)

def MoveUp(state):

s = CopyState(state)

y, x = GetSpace(s)

s[y][x], s[y - 1][x] = s[y - 1][x], s[y][x]

return s

# 獲取空格下移后的狀態(tài)，不改變?cè)瓲顟B(tài)

def MoveDown(state):

s = CopyState(state)

y, x = GetSpace(s)

s[y][x], s[y + 1][x] = s[y + 1][x], s[y][x]

return s

# 獲取空格左移后的狀態(tài)，不改變?cè)瓲顟B(tài)

def MoveLeft(state):

s = CopyState(state)

y, x = GetSpace(s)

s[y][x], s[y][x - 1] = s[y][x - 1], s[y][x]

return s

# 獲取空格右移后的狀態(tài)，不改變?cè)瓲顟B(tài)

def MoveRight(state):

s = CopyState(state)

y, x = GetSpace(s)

s[y][x], s[y][x + 1] = s[y][x + 1], s[y][x]

return s

# 獲取兩個(gè)狀態(tài)之間的啟發(fā)距離

def GetDistance(src, dest):

dic, d = goal_dic, 0

for i in range(len(src)):

for j in range(len(src[i])):

pos = dic[src[i][j]]

y, x= pos[0], pos[1]

d += abs(y - i) + abs(x - j)

return d

# 獲取指定狀態(tài)下的操作

def GetActions(state):

acts = []

y, x = GetSpace(state)

if x > 0:acts.append(MoveLeft)

if y > 0:acts.append(MoveUp)

if x < len(state[0]) - 1:acts.append(MoveRight)

if y < len(state[0]) - 1: acts.append(MoveDown)

return acts

# 用于統(tǒng)一操作序列的函數(shù)

def Start(state):

return

# 邊緣隊(duì)列中的節(jié)點(diǎn)類

class Node:

state = None ? # 狀態(tài)

value = -1 ? ? # 啟發(fā)值

step = 0 ? ? ? # 初始狀態(tài)到當(dāng)前狀態(tài)的距離（步數(shù)）

action = Start ?# 到達(dá)此節(jié)點(diǎn)所進(jìn)行的操作

parent = None, ?# 父節(jié)點(diǎn)

# 用狀態(tài)和步數(shù)構(gòu)造節(jié)點(diǎn)對(duì)象

def __init__(self, state, step, action, parent):

self.state = state

self.step = step

self.action = action

self.parent = parent

# 計(jì)算估計(jì)距離

self.value = GetDistance(state, goal_state) + step

# 獲取擁有最小啟發(fā)值的元素索引

def GetMinIndex(queue):

index = 0

for i in range(len(queue)):

node = queue[i]

if node.value < queue[index].value:

index = i

return index

# 將狀態(tài)轉(zhuǎn)換為整數(shù)

def toInt(state):

value = 0

for i in state:

for j in i:

value = value * 10 + j

return value

# A*算法尋找初始狀態(tài)到目標(biāo)狀態(tài)的路徑

def AStar(init, goal):

# 邊緣隊(duì)列初始已有源狀態(tài)節(jié)點(diǎn)

queue = [Node(init, 0, Start, None)]

visit = {} ?# 訪問過的狀態(tài)表

count = 0 ? # 循環(huán)次數(shù)

# 隊(duì)列沒有元素則查找失敗

while queue:

# 獲取擁有最小估計(jì)距離的節(jié)點(diǎn)索引

index = GetMinIndex(queue)

node = queue[index]

visit[toInt(node.state)] = True

count += 1

if node.state == goal:

return node, count

del queue[index]

# 擴(kuò)展當(dāng)前節(jié)點(diǎn)

for act in GetActions(node.state):

# 獲取此操作下到達(dá)的狀態(tài)節(jié)點(diǎn)并將其加入邊緣隊(duì)列中

near = Node(act(node.state), node.step + 1, act, node)

if toInt(near.state) not in visit:

queue.append(near)

return None, count

# 將鏈表倒序，返回鏈頭和鏈尾

def reverse(node):

if node.parent == None:

return node, node

head, rear = reverse(node.parent)

rear.parent, node.parent = node, None

return head, node

node, count = AStar(init_state, goal_state)

if node == None:

print("無法從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)！")

else:

print("搜索成功，循環(huán)次數(shù)：", count)

node, rear = reverse(node)

count = 0

while node:

# 啟發(fā)值包括從起點(diǎn)到此節(jié)點(diǎn)的距離

print("第", count + 1, "步：", node.action.__name__,

"啟發(fā)值為：", count, "+", node.value - count)

PrintState(node.state)

node = node.parent

count += 1