跳到主要内容

启发式搜索

介绍​

启发式搜索（Heuristic Search）是一种在搜索过程中利用启发式信息来指导搜索方向的算法。与盲目搜索（如深度优先搜索或广度优先搜索）不同，启发式搜索通过评估当前状态与目标状态之间的“距离”或“代价”，优先选择最有希望达到目标的路径。这种方法可以显著减少搜索空间，提高搜索效率。

启发式搜索常用于解决复杂问题，如路径规划、拼图游戏、人工智能中的决策问题等。

启发式函数​

启发式搜索的核心是启发式函数（Heuristic Function），通常表示为 h(n)。这个函数用于估计从当前状态 n 到目标状态的代价。启发式函数的设计对搜索效率至关重要，一个好的启发式函数能够有效地引导搜索方向。

备注

启发式函数必须满足以下条件：

  1. 可接受性（Admissibility）：启发式函数的值不能高估实际代价。
  2. 一致性（Consistency）：对于任意状态 n 和其后续状态 n'，启发式函数应满足 h(n) <= cost(n, n') + h(n')。

A* 算法​

A* 算法是最常用的启发式搜索算法之一。它结合了代价函数 g(n)（从起点到当前状态的代价）和启发式函数 h(n)，通过评估函数 f(n) = g(n) + h(n) 来选择最优路径。

A* 算法步骤​

  1. 初始化：将起点加入开放列表（Open List），并设置 g(n) 和 h(n) 的值。
  2. 循环直到找到目标或开放列表为空：
    • 从开放列表中选择 f(n) 最小的节点。
    • 将该节点从开放列表移到关闭列表（Closed List）。
    • 对该节点的所有邻居节点：
      • 如果邻居节点是目标，返回路径。
      • 如果邻居节点不在开放列表中，计算 g(n) 和 h(n)，并将其加入开放列表。
      • 如果邻居节点已在开放列表中，检查是否需要更新 g(n) 和 f(n)。

代码示例​

以下是一个简单的 A* 算法实现，用于在网格中找到从起点到终点的最短路径。

python
def a_star(start, goal, grid):
    open_list = [start]
    closed_list = set()
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    
    while open_list:
        current = min(open_list, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, current)
        
        open_list.remove(current)
        closed_list.add(current)
        
        for neighbor in get_neighbors(current, grid):
            if neighbor in closed_list:
                continue
            tentative_g_score = g_score[current] + 1  # Assuming each step costs 1
            
            if neighbor not in open_list:
                open_list.append(neighbor)
            elif tentative_g_score >= g_score[neighbor]:
                continue
                
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
    
    return None

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def get_neighbors(node, grid):
    # Return valid neighbors in the grid
    pass

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

输入与输出​

假设我们有一个 3x3 的网格，起点为 (0, 0)，终点为 (2, 2)，网格中无障碍物。

python
grid = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]

start = (0, 0)
goal = (2, 2)

path = a_star(start, goal, grid)
print(path)  # 输出: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]

实际应用​

路径规划​

启发式搜索广泛应用于路径规划问题，如机器人导航、游戏中的角色移动等。通过使用启发式函数，算法可以快速找到从起点到终点的最短路径。

拼图游戏​

在解决拼图游戏（如 8 拼图）时，启发式搜索可以帮助找到最少的移动步骤。常用的启发式函数包括曼哈顿距离和错位方块数。

总结​

启发式搜索通过利用启发式信息，能够有效地减少搜索空间，提高搜索效率。A* 算法是启发式搜索的经典实现，广泛应用于路径规划、拼图游戏等领域。

提示

练习：尝试实现一个 A* 算法来解决 8 拼图问题，并使用不同的启发式函数（如曼哈顿距离、错位方块数）来比较搜索效率。

附加资源​