算法簡(jiǎn)介

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

代碼說(shuō)明

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

代碼

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