Python 算法高级篇：启发式搜索与 A *算法

小蓝枣

发布于 2023-10-27 16:47:42

3780

发布于 2023-10-27 16:47:42

Python 算法高级篇：启发式搜索与 A *算法

引言

启发式搜索是一种常用于解决路径规划和优化问题的算法，而 A *算法是其中的一种经典方法。本篇博客将深入探讨启发式搜索的原理，介绍 A *算法的工作方式，以及如何在 Python 中实现它。每一行代码都将有详细的注释，以帮助你理解算法的实现。

😃😄 ❤️ ❤️ ❤️

1. 什么是启发式搜索？

启发式搜索是一种问题解决方法，旨在在大规模搜索空间中寻找最优解或接近最优解的解。它使用一个启发式函数（也称为估价函数）来评估每个搜索节点，以确定哪些节点最有可能包含最优解。启发式函数提供了一种估计从当前节点到目标节点的代价或距离的方式，通常称为启发式值。

1.1 启发式函数的特性

一个良好的启发式函数应该满足以下特性：

一致性（ Consistency ）：启发式函数的估计值不应该高估实际代价。也就是说，如果启发式函数估计从节点 A 到节点 B 的代价为 h ( A )，而从节点 B 到节点 C 的代价为 d ( B , C )，那么 h ( A )不应该大于 d ( B , C ) + h ( C )。
启发式值为 0 ：启发式函数应该在目标节点上返回 0 。这表示已经达到了最优解。

1.2 启发式搜索算法

在启发式搜索中，有两个核心概念：

开放列表（ Open List ）：包含待扩展的节点。节点根据启发式函数的值排列，最有希望的节点在前面。
闭合列表（ Closed List ）：包含已经扩展的节点。这些节点不会再次考虑。

启发式搜索通常包括以下步骤：

1 . 将初始节点放入开放列表。
2 . 重复执行以下步骤，直到达到目标节点或开放列表为空：
- a . 从开放列表中选择具有最小启发式值的节点。
- b . 如果选择的节点是目标节点，则算法结束。
- c . 否则，将该节点从开放列表移到闭合列表，并扩展它的邻居节点。
3 . 如果开放列表为空且未找到目标节点，则问题无解。

2. A *算法的原理

A *算法是一种启发式搜索算法，常用于路径规划和图搜索问题。它使用两个估价函数来指导搜索过程：

g ( n )：从起始节点到节点 n 的实际代价。
h ( n )：从节点 n 到目标节点的估计代价，由启发式函数提供。

A *算法的评估函数为 f ( n ) = g ( n ) + h ( n )。它尝试从开放列表中选择 f 值最小的节点进行扩展，期望能够找到最优解。

2.1 A *算法的伪代码

以下是 A *算法的伪代码：

function A*(start, goal)
    open_list = {start}  # 初始化开放列表，包含起始节点
    closed_list = {}     # 初始化闭合列表

    while open_list is not empty
        current = node in open_list with the lowest f
        if current is goal
            return reconstruct_path(goal)
        
        move current from open_list to closed_list

        for each neighbor of current
            if neighbor is in closed_list
                continue
            if neighbor is not in open_list
                add neighbor to open_list
            tentative_g = g(current) + distance(current, neighbor)
            if tentative_g >= g(neighbor)
                continue

            # This path is the best so far. Record it!
            g(neighbor) = tentative_g
            h(neighbor) = heuristic(neighbor, goal)
            f(neighbor) = g(neighbor) + h(neighbor)
            parent(neighbor) = current

    # Open list is empty but goal was never reached
    return "No path found"

2.2 A *算法的优点

A *算法具有以下优点：

完备性：如果解存在， A *算法将找到最优解。
最优性：当启发式函数满足一致性条件时， A *算法保证找到最优解。
可配置性：可以根据不同问题和启发式函数来配置 A *算法。

3. Python 中的 A *算法实现

让我们来看一个在 Python 中实现 A *算法的示例，用于解决迷宫问题。

import heapq

def astar(grid, start, end):
    open_list = []
    heapq.heappush(open_list, (0, start))
    came_from = {}
    g_score = {cell: float('inf') for row in grid for cell in row}
    g_score[start] = 0
    f_score = {cell: float('inf') for row in grid for cell in row}
    f_score[start] = heuristic(start, end)

    while open_list:
        current_f, current = heapq.heappop(open_list)

        if current == end:
            return reconstruct_path(came_from, current)

        for neighbor in get_neighbors(current, grid):
            tentative_g = g_score[current] + 1
            if tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, end)
                heapq.heappush(open_list, (f_score[neighbor], neighbor))

    return None  # No path found

# Helper functions for the A* algorithm
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def get_neighbors(cell, grid):
    neighbors = []
    row, col = cell
    if row > 0 and not grid[row - 1][col]:
        neighbors.append((row - 1, col))
    if row < len(grid) - 1 and not grid[row + 1][col]:
        neighbors.append((row + 1, col))
    if col > 0 and not grid[row][col - 1]:
        neighbors.append((row, col - 1))
    if col < len(grid[0]) - 1 and not grid[row][col + 1]:
        neighbors.append((row, col + 1))
    return neighbors

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

# 示例：解决迷宫问题
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
end = (4, 4)
path = astar(grid, start, end)
print("Path:", path)

这个示例演示了如何使用 A *算法解决迷宫问题，寻找从起点到终点的最短路径。