算法簡介

A*（A-star）算法是一種用于圖形搜索和路徑規(guī)劃的啟發(fā)式搜索算法，它結(jié)合了最佳優(yōu)先搜索（Best-First Search）和Dijkstra算法的思想，能夠有效地尋找從起點到目標點的最短路徑。A*算法廣泛應(yīng)用于導航、游戲AI、機器人路徑規(guī)劃等領(lǐng)域。

代碼說明

Node類：表示搜索過程中的一個節(jié)點，包含位置、從起點到當前節(jié)點的代價 (g)、從當前節(jié)點到目標節(jié)點的啟發(fā)式代價 (h)，以及父節(jié)點用于回溯路徑。
A算法：astar函數(shù)實現(xiàn)了A算法的核心邏輯。通過開放列表優(yōu)先隊列不斷從代價最小的節(jié)點擴展，直到找到目標節(jié)點。
啟發(fā)式函數(shù)：heuristic使用曼哈頓距離作為啟發(fā)式代價，適用于網(wǎng)格布局。
鄰居節(jié)點：get_neighbors返回當前節(jié)點的四個鄰居（上下左右）。

代碼

import heapqclass Node:def __init__(self, position, g=0, h=0):self.position = position  # 坐標 (x, y)self.g = g  # 從起點到當前節(jié)點的代價self.h = h  # 從當前節(jié)點到目標節(jié)點的預(yù)估代價（啟發(fā)式估計）self.f = g + h  # 總代價self.parent = None  # 記錄父節(jié)點def __lt__(self, other):return self.f < other.f  # 優(yōu)先隊列按 f 值排序def astar(start, goal, grid):# 創(chuàng)建開放列表（優(yōu)先隊列）和閉合列表open_list = []closed_list = set()# 將起點添加到開放列表start_node = Node(start, 0, heuristic(start, goal))heapq.heappush(open_list, start_node)while open_list:# 從開放列表中取出代價最小的節(jié)點current_node = heapq.heappop(open_list)# 如果目標已經(jīng)找到，返回路徑if current_node.position == goal:path = []while current_node:path.append(current_node.position)current_node = current_node.parentreturn path[::-1]  # 返回反轉(zhuǎn)后的路徑# 將當前節(jié)點添加到閉合列表closed_list.add(current_node.position)# 獲取相鄰節(jié)點neighbors = get_neighbors(current_node.position)for neighbor in neighbors:if neighbor in closed_list:continue  # 如果相鄰節(jié)點已經(jīng)被處理過，跳過g_cost = current_node.g + 1  # 假設(shè)每步的代價為1h_cost = heuristic(neighbor, goal)neighbor_node = Node(neighbor, g_cost, h_cost)neighbor_node.parent = current_node# 如果相鄰節(jié)點不在開放列表中，加入開放列表heapq.heappush(open_list, neighbor_node)return None  # 如果沒有路徑，返回 Nonedef heuristic(node, goal):# 計算啟發(fā)式代價（這里使用曼哈頓距離）return abs(node[0] - goal[0]) + abs(node[1] - goal[1])def get_neighbors(position):# 獲取當前節(jié)點的相鄰節(jié)點（上下左右）x, y = positionreturn [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]if __name__ == "__main__":start = (0, 0)  # 起點goal = (4, 4)  # 目標點grid = [[0 for _ in range(5)] for _ in range(5)]  # 假設(shè)網(wǎng)格，0表示可行走區(qū)域path = astar(start, goal, grid)print("找到的路徑：", path)