實現(xiàn)兩種啟發(fā)函數(shù)

采取兩種策略實現(xiàn)啟發(fā)函數(shù)：

• 策略1：不在目標(biāo)位置的數(shù)字個數(shù)
• 策略2：曼哈頓距離（將數(shù)字直接移動到對應(yīng)位置的步數(shù)總數(shù)）

# 策略1: 不在目標(biāo)位置的數(shù)字個數(shù)，即 state 與 goal_state 不相同的數(shù)字個數(shù)
def h1(state, goal_state):'''state, goal_state - 3x3 list'''distance = 0for i in range(3):for j in range(3):if state[i][j] != goal_state[i][j] and state[i][j] != 0:distance += 1return distance# 功能性函數(shù)，用于查找給定數(shù)字 num 在 goal_state 中的坐標(biāo)
def find_num(num, goal_state):for i in range(3):for j in range(3):if goal_state[i][j] == num:return i, jreturn -1, -1# 策略2: 曼哈頓距離之和
def h2(state, goal_state):'''state, goal_state - 3x3 list'''distance = 0for i in range(3):for j in range(3):if state[i][j] == 0:continueif state[i][j] == goal_state[i][j]:continuegoal_i, goal_j = find_num(state[i][j], goal_state)distance += abs(i - goal_i) + abs(j - goal_j)return distance# 測試
start_state = [[2, 8, 3],[1, 6, 4],[7, 0, 5]
]goal_state = [[1, 2, 3],[8, 0, 4],[7, 6, 5]
]# 不在目標(biāo)位置的數(shù)字：1、2、8、6，共 4 個
# 1 需移動 1 步到達(dá)正確位置
# 2 需移動 1 步到達(dá)正確位置
# 8 需移動 2 步到達(dá)正確位置
# 6 需移動 1 步到達(dá)正確位置
# 曼哈頓距離共 5 步print(h1(start_state, goal_state))  # 4
print(h2(start_state, goal_state))  # 5

---

實現(xiàn)A*算法

為了便于替換啟發(fā)函數(shù)，將其作為參數(shù)傳入函數(shù)：

# 定義A*算法函數(shù)
def astar(start_state, goal_state, h):'''params:start_state - 3x3 list 初始狀態(tài)goal_state  - 3x3 list 目標(biāo)狀態(tài)h           - function 啟發(fā)函數(shù)returns:expanded_nodes - 擴展節(jié)點數(shù)run_time       - 算法運行時間path           - 算法運行路徑ps. 當(dāng)路徑不存在時，會返回 run_time = 0, path = None'''start_time = time.time()  # 算法開始open_list = [(h(start_state, goal_state), start_state)]  # 存儲待擴展的節(jié)點的優(yōu)先隊列closed_set = set()  # 存儲已經(jīng)擴展過的節(jié)點的集合came_from = {}      # 記錄節(jié)點之間的關(guān)系，即每個節(jié)點的父節(jié)點是哪個節(jié)點expanded_nodes = 0  # 記錄擴展節(jié)點的數(shù)量while open_list:  # 帶擴展節(jié)點隊列不為空_, current_state = heapq.heappop(open_list)  # 彈出優(yōu)先級最高的節(jié)點expanded_nodes += 1if current_state == goal_state:  # 找到目標(biāo)狀態(tài)# 回溯路徑path = [current_state]while tuple(map(tuple, current_state)) in came_from:current_state = came_from[tuple(map(tuple, current_state))]path.append(current_state)end_time = time.time()  # 記錄算法結(jié)束時間return expanded_nodes, end_time-start_time, path[::-1]closed_set.add(tuple(map(tuple, current_state)))  # 將當(dāng)前節(jié)點狀態(tài)加入已擴展節(jié)點集合zero_i, zero_j = find_num(0, current_state)  # 找到當(dāng)前的空格坐標(biāo)moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 四周的格子for di, dj in moves:new_i, new_j = zero_i + di, zero_j + dj  # 移動的數(shù)字if 0 <= new_i < 3 and 0 <= new_j < 3:  # 確保新位置在范圍內(nèi)new_state = [row[:] for row in current_state]  # 拷貝 current_statenew_state[zero_i][zero_j], new_state[new_i][new_j] = current_state[new_i][new_j], current_state[zero_i][zero_j]  # 移動空白格if tuple(map(tuple, new_state)) in closed_set:continue  # 如果新狀態(tài)已經(jīng)擴展過，則跳過new_cost = len(came_from) + 1 + h(new_state, goal_state)  # 計算新狀態(tài)的代價heapq.heappush(open_list, (new_cost, new_state))  # 將新狀態(tài)加入優(yōu)先隊列came_from[tuple(map(tuple, new_state))] = tuple(map(tuple, current_state))  # 更新新狀態(tài)的父節(jié)點信息# 無可行解return expanded_nodes, 0, None

---

測試

首先，定義一個函數(shù) print_path() 用于查看路徑：

def print_path(path):step = 0for state in path:print("Step. ", step)for row in state:print(row)step += 1

設(shè)置初始狀態(tài)和目標(biāo)狀態(tài)進(jìn)行測試：

# 設(shè)置初始狀態(tài)和目標(biāo)狀態(tài)
start_state = [[2, 8, 3],[1, 6, 4],[7, 0, 5]
]goal_state = [[1, 2, 3],[8, 0, 4],[7, 6, 5]
]h1_nodes, h1_times, h1_path = astar(start_state, goal_state, h1)  # 通過 h1 啟發(fā)函數(shù)調(diào)用 astar 算法
h2_nodes, h2_times, h2_path = astar(start_state, goal_state, h2)  # 通過 h2 啟發(fā)函數(shù)調(diào)用 astar 算法if h1_path:print("調(diào)用 h1 啟發(fā)函數(shù)的 A* 算法共擴展 {} 個節(jié)點，耗時 {}s，路徑如下：".format(h1_nodes, h1_times))# print_path(h1_path)
else:print("調(diào)用 h1 啟發(fā)函數(shù)的 A* 算法無法得到可行解。")# print("=" * 50)
if h2_path:print("調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法共擴展 {} 個節(jié)點，耗時 {}s，路徑如下：".format(h2_nodes, h2_times))# print_path(h2_path)
else:print("調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法無法得到可行解。")

輸出結(jié)果：（path 輸出過長，這里省略）

調(diào)用 h1 啟發(fā)函數(shù)的 A* 算法共擴展 28 個節(jié)點，耗時 0.00037217140197753906s，路徑如下：
調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法共擴展 17 個節(jié)點，耗時 0.0002200603485107422s，路徑如下：

測試魯棒性——當(dāng)可行解不存在時：

# 設(shè)置初始狀態(tài)和目標(biāo)狀態(tài)
start_state = [[7, 8, 3],[1, 5, 2],[6, 0, 4]
]goal_state = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]h1_nodes, h1_times, h1_path = astar(start_state, goal_state, h1)  # 通過 h1 啟發(fā)函數(shù)調(diào)用 astar 算法
h2_nodes, h2_times, h2_path = astar(start_state, goal_state, h2)  # 通過 h2 啟發(fā)函數(shù)調(diào)用 astar 算法if h1_path:print("調(diào)用 h1 啟發(fā)函數(shù)的 A* 算法共擴展 {} 個節(jié)點，耗時 {}s，路徑如下：".format(h1_nodes, h1_times))# print_path(h1_path)
else:print("調(diào)用 h1 啟發(fā)函數(shù)的 A* 算法無法得到可行解。")# print("=" * 50)
if h2_path:print("調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法共擴展 {} 個節(jié)點，耗時 {}s，路徑如下：".format(h2_nodes, h2_times))# print_path(h2_path)
else:print("調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法無法得到可行解。")

輸出結(jié)果：（path 輸出過長，這里省略）

調(diào)用 h1 啟發(fā)函數(shù)的 A* 算法無法得到可行解。
調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法無法得到可行解。

國科大的朋友們提交之前改一改哈！因為作者也是這么交的～