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

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

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

# 策略1: 不在目標(biāo)位置的數(shù)字個(gè)數(shù)，即 state 與 goal_state 不相同的數(shù)字個(gè)數(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 個(gè)
# 1 需移動(dòng) 1 步到達(dá)正確位置
# 2 需移動(dòng) 1 步到達(dá)正確位置
# 8 需移動(dòng) 2 步到達(dá)正確位置
# 6 需移動(dòng) 1 步到達(dá)正確位置
# 曼哈頓距離共 5 步print(h1(start_state, goal_state))  # 4
print(h2(start_state, goal_state))  # 5

---

實(shí)現(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 - 擴(kuò)展節(jié)點(diǎn)數(shù)run_time       - 算法運(yùn)行時(shí)間path           - 算法運(yùn)行路徑ps. 當(dāng)路徑不存在時(shí)，會(huì)返回 run_time = 0, path = None'''start_time = time.time()  # 算法開始open_list = [(h(start_state, goal_state), start_state)]  # 存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)的優(yōu)先隊(duì)列closed_set = set()  # 存儲(chǔ)已經(jīng)擴(kuò)展過的節(jié)點(diǎn)的集合came_from = {}      # 記錄節(jié)點(diǎn)之間的關(guān)系，即每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是哪個(gè)節(jié)點(diǎn)expanded_nodes = 0  # 記錄擴(kuò)展節(jié)點(diǎn)的數(shù)量while open_list:  # 帶擴(kuò)展節(jié)點(diǎn)隊(duì)列不為空_, current_state = heapq.heappop(open_list)  # 彈出優(yōu)先級最高的節(jié)點(diǎn)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é)束時(shí)間return expanded_nodes, end_time-start_time, path[::-1]closed_set.add(tuple(map(tuple, current_state)))  # 將當(dāng)前節(jié)點(diǎn)狀態(tài)加入已擴(kuò)展節(jié)點(diǎn)集合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  # 移動(dòng)的數(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]  # 移動(dòng)空白格if tuple(map(tuple, new_state)) in closed_set:continue  # 如果新狀態(tài)已經(jīng)擴(kuò)展過，則跳過new_cost = len(came_from) + 1 + h(new_state, goal_state)  # 計(jì)算新狀態(tài)的代價(jià)heapq.heappush(open_list, (new_cost, new_state))  # 將新狀態(tài)加入優(yōu)先隊(duì)列came_from[tuple(map(tuple, new_state))] = tuple(map(tuple, current_state))  # 更新新狀態(tài)的父節(jié)點(diǎn)信息# 無可行解return expanded_nodes, 0, None

---

測試

首先，定義一個(gè)函數(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* 算法共擴(kuò)展 {} 個(gè)節(jié)點(diǎn)，耗時(shí) {}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* 算法共擴(kuò)展 {} 個(gè)節(jié)點(diǎn)，耗時(shí) {}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* 算法共擴(kuò)展 28 個(gè)節(jié)點(diǎn)，耗時(shí) 0.00037217140197753906s，路徑如下：
調(diào)用 h2 啟發(fā)函數(shù)的 A* 算法共擴(kuò)展 17 個(gè)節(jié)點(diǎn)，耗時(shí) 0.0002200603485107422s，路徑如下：

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

# 設(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* 算法共擴(kuò)展 {} 個(gè)節(jié)點(diǎn)，耗時(shí) {}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* 算法共擴(kuò)展 {} 個(gè)節(jié)點(diǎn)，耗時(shí) {}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* 算法無法得到可行解。

國科大的朋友們提交之前改一改哈！因?yàn)樽髡咭彩沁@么交的～