用Python写一个A*搜索算法含注释说明

大家好！我是幻化意识流。

今天我们用Python写一个A*搜索算法的代码，我做了注释说明，欢迎大家一起学习：

import heapq

# 定义搜索节点类，包括当前状态、从初始状态到该状态的代价g、从该状态到目标状态的估计代价h、父节点、以及在搜索中是否被访问过的状态

class Node:

def __init__(self, state, g_cost, h_cost, parent=None):

self.state = state

self.g_cost = g_cost

self.h_cost = h_cost

self.parent = parent

self.visited = False

# 定义比较操作，用于堆排序时比较两个节点的f值

def __lt__(self, other):

return (self.g_cost + self.h_cost) < (other.g_cost + other.h_cost)

# 定义A*搜索函数，接收初始状态和目标状态作为输入

def astar_search(start_state, goal_state):

# 定义初始节点，初始g值为0，h值为从初始状态到目标状态的估计代价

start_node = Node(start_state, 0, heuristic(start_state, goal_state))

# 定义一个堆，用于存储待扩展的节点

open_heap = []

heapq.heappush(open_heap, start_node)

# 定义一个字典，用于存储已经访问过的节点

visited = {}

while open_heap:

# 取出f值最小的节点

current_node = heapq.heappop(open_heap)

# 如果该节点已经被访问过，则跳过

if visited.get(current_node.state):

continue

# 将该节点标记为已经访问过

current_node.visited = True

visited[current_node.state] = current_node

# 如果当前节点为目标状态，则返回搜索路径

if current_node.state == goal_state:

return get_path(current_node)

# 扩展当前节点

for next_state, cost in get_neighbors(current_node.state):

# 如果下一个状态已经被访问过，则跳过

if visited.get(next_state):

continue

# 计算从初始状态到下一个状态的代价g

g_cost = current_node.g_cost + cost

# 如果下一个状态还没有被访问过，则创建一个新节点

if not any(node.state == next_state for node in open_heap):

next_node = Node(next_state, g_cost, heuristic(next_state, goal_state), current_node)

heapq.heappush(open_heap, next_node)

else:

# 如果下一个状态已经在堆中，则找到对应的节点

next_node = next(node for node in open_heap if node.state == next_state)

# 如果新的g值更优，则更新该节点

if g_cost < next_node.g_cost:

next_node.g_cost = g_cost

next_node.parent = current_node

# 如果搜索完毕，但是没有找到目标状态，则返回空列表

return []

# 定义估价函数，这里使用曼哈顿距离作为估计代价

def heuristic(state, goal_state):

return sum(abs(a - b) for a, b in zip(state, goal_state))

定义获取邻居节点函数，这里使用一个简单的例子来说明

假设状态是一个二维坐标(x,y)，邻居节点包括上下左右四个方向上的节点

def get_neighbors(state):

x, y = state

neighbors = []

if x > 0:

neighbors.append(((x-1, y), 1))

if x < 2:

neighbors.append(((x+1, y), 1))

if y > 0:

neighbors.append(((x, y-1), 1))

if y < 2:

neighbors.append(((x, y+1), 1))

return neighbors

定义获取搜索路径函数，从目标状态开始，依次沿着父节点返回到初始状态

def get_path(node):

path = []

while node:

path.append(node.state)

node = node.parent

return path[::-1]

测试代码，假设初始状态为(0,0)，目标状态为(2,2)

start_state = (0, 0)

goal_state = (2, 2)

path = astar_search(start_state, goal_state)

print(path)

注释说明：

- 在定义搜索节点类Node时，包括了状态state、代价g_cost、估计代价h_cost、父节点parent以及是否被访问过的状态visited。

- 在定义比较操作`__lt__`时，采用的是节点的f值作为比较依据，即f = g + h。

- 在实现A*搜索函数astar_search时，采用了堆数据结构来存储待扩展的节点，这样可以快速找到f值最小的节点。

- 在搜索过程中，使用字典visited来存储已经访问过的节点，这样可以避免重复访问。

- 在扩展节点时，首先判断下一个状态是否已经被访问过，如果已经被访问过，则跳过；否则，计算从初始状态到下一个状态的代价g，如果下一个状态还没有在堆中，则创建一个新节点并加入堆中，否则，找到对应的节点并更新g值和父节点。

- 在估价函数heuristic中，采用的是曼哈顿距离，即两点在x和y方向上的距离之和。

- 在获取邻居节点函数get_neighbors中，假设状态是二维坐标(x,y)，邻居节点包括上下左右四个方向上的节点，其中每个邻居节点的代价均为1。

- 在获取搜索路径函数get_path中，从目标状态开始，依次沿着父节点返回到初始状态，最终得到的是从初始状态到目标状态的一条最短路径。

- 在测试代码中，假设初始状态为(0,0)，目标状态为(2,2)，调用A*搜索函数astar_search得到最短路径，并输出路径上的所有状态。

以上就是一个简单的A*搜索代码，当然在实际应用中可能需要根据具体问题进行相应的调整。

如果喜欢我的文章，麻烦您动动您的神手帮我点个赞哦！本人在此深深的感谢！