人工智能算法之A*搜索算法

创作时间:

作者:

@小白创作中心

人工智能算法之A*搜索算法

引用

CSDN

https://m.blog.csdn.net/weixin_50153843/article/details/143379550

A搜索算法是一种广泛应用于路径寻找和优化问题的图形搜索算法。它结合了实际代价和启发式代价，能够高效地找到从起点到目标点的最优路径。本文将详细介绍A算法的基本原理、实现方法及其应用场景。

A搜索算法是一种广泛使用的图形搜索算法，适用于路径寻找和图形遍历。它结合了最佳优先搜索和Dijkstra算法的优点，通过利用启发式信息来引导搜索过程，能够高效地找到从起点到目标点的最优路径。A算法在很多应用场景中表现出色，包括游戏开发、机器人导航和地图路由等。

A*算法的基本原理

A*算法通过维护一个优先队列来管理待处理的节点。每个节点的代价由两部分组成：

实际代价 ( g(n) )：从起点到当前节点 ( n ) 的实际代价。
启发式代价 ( h(n) )：从当前节点 ( n ) 到目标节点的估算代价。

A*算法的核心思想是使用代价函数 ( f(n) ) 来评估节点 ( n )：

f(n) 表示从起点到目标节点的总估计代价。
g(n) 是实际成本。
h(n) 是从当前节点到目标节点的启发式估算。

A*算法通过不断扩展代价函数最小的节点，逐步找到目标节点。

启发式函数的选择

启发式函数 ( h(n) ) 是A*算法的关键，它决定了算法的效率和效果。一个有效的启发式函数应满足以下条件：

可接受性（Admissibility）：启发式函数永远不应高估从当前节点到目标节点的真实代价。
一致性（Consistency）：对于每个节点 ( n ) 和它的每个相邻节点 ( m )，启发式函数应满足：
其中 ( c(n, m) ) 是从 ( n ) 到 ( m ) 的实际代价。

常见的启发式函数包括：

曼哈顿距离：在网格地图中，适用于只能上下左右移动的场景：
欧几里得距离：适用于可以在任意方向移动的场景：

A*算法的步骤

初始化：创建一个开启列表（Open List）和关闭列表（Closed List）。将起点放入开启列表。
循环处理节点：

从开启列表中选择代价函数 f(n) 最小的节点 n 。
如果 n 是目标节点，则找到路径，算法结束。
将 n 移动到关闭列表。
对于每个相邻节点 m ：
如果 m 在关闭列表中，跳过。
计算 g(m) 和 f(m) 。
如果 m 不在开启列表中，添加到开启列表。

路径重建：从目标节点反向重建路径。

A*算法的Python实现

下面的代码实现了A*算法在一个简单网格上的路径寻找，假设可以上下左右移动。

import heapq

class Node:
    def __init__(self, position, parent=None):
        self.position = position  # 节点位置 (x, y)
        self.parent = parent  # 父节点
        self.g = 0  # 从起点到当前节点的实际代价
        self.h = 0  # 从当前节点到目标节点的启发式代价
        self.f = 0  # 总的估计代价 f(n) = g(n) + h(n)

    def __eq__(self, other):
        return self.position == other.position

    def __lt__(self, other):
        return self.f < other.f

def heuristic(node1, node2):
    """ 计算曼哈顿距离作为启发式函数 """
    return abs(node1.position[0] - node2.position[0]) + abs(node1.position[1] - node2.position[1])

def a_star_search(start, goal, grid):
    open_list = []
    closed_list = set()
    start_node = Node(start)
    goal_node = Node(goal)
    
    # 将起点加入开启列表
    heapq.heappush(open_list, start_node)
    while open_list:
        # 取出f值最小的节点
        current_node = heapq.heappop(open_list)
        # 如果达到目标节点
        if current_node == goal_node:
            path = []
            while current_node:
                path.append(current_node.position)
                current_node = current_node.parent
            return path[::-1]  # 返回反向路径
        closed_list.add(current_node)
        # 生成邻居节点
        neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上、右、下、左
        for new_position in neighbors:
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
            # 检查是否在网格范围内
            if (node_position[0] > (len(grid) - 1) or node_position[0] < 0 or
                    node_position[1] > (len(grid[len(grid) - 1]) - 1) or node_position[1] < 0):
                continue
            
            # 检查是否为障碍物
            if grid[node_position[0]][node_position[1]] != 0:
                continue
            
            neighbor_node = Node(node_position, current_node)
            
            if neighbor_node in closed_list:
                continue
            
            # 计算g, h, f值
            neighbor_node.g = current_node.g + 1
            neighbor_node.h = heuristic(neighbor_node, goal_node)
            neighbor_node.f = neighbor_node.g + neighbor_node.h
            
            # 检查邻居是否已经在开启列表中
            if any(neighbor_node == open_node and neighbor_node.g > open_node.g for open_node in open_list):
                continue
            
            # 将邻居添加到开启列表
            heapq.heappush(open_list, neighbor_node)
    return None  # 没有找到路径

# 示例网格（0表示可通行，1表示障碍物）
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)  # 起点
goal = (4, 4)   # 终点

# 执行A*搜索
path = a_star_search(start, goal, grid)
print(f"Path from {start} to {goal}: {path}")