跳到主要内容

启发式搜索

介绍

启发式搜索(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)。
  2. 循环:
    • 从开放列表中选择 f(n) 最小的节点 n
    • 如果 n 是目标节点,则搜索成功,返回路径。
    • 否则,将 n 移出开放列表,加入关闭列表(Closed List)。
    • 扩展 n 的所有邻居节点,计算它们的 f(n) 值,并加入开放列表。
  3. 如果开放列表为空且未找到目标节点,则搜索失败。

代码示例

以下是一个简单的 A* 算法实现,用于在网格地图中寻找最短路径。

python
import heapq

def heuristic(a, b):
# 使用曼哈顿距离作为启发式函数
return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(graph, start, goal):
open_list = []
heapq.heappush(open_list, (0, start))
came_from = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}

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

if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
return path[::-1]

for neighbor in graph.neighbors(current):
tentative_g_score = g_score[current] + graph.cost(current, neighbor)

if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
heapq.heappush(open_list, (f_score[neighbor], neighbor))

return None

输入与输出

假设我们有一个 3x3 的网格地图,起点为 (0, 0),终点为 (2, 2)。地图中某些格子是障碍物,无法通过。

python
class Graph:
def __init__(self, grid):
self.grid = grid

def neighbors(self, node):
x, y = node
neighbors = []
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < len(self.grid) and 0 <= ny < len(self.grid[0]) and self.grid[nx][ny] == 0:
neighbors.append((nx, ny))
return neighbors

def cost(self, a, b):
return 1

grid = [
[0, 1, 0],
[0, 1, 0],
[0, 0, 0]
]

graph = Graph(grid)
start = (0, 0)
goal = (2, 2)

path = a_star_search(graph, start, goal)
print("Path:", path)

输出:

Path: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]

实际应用

启发式搜索在许多实际场景中都有广泛应用,例如:

  1. 路径规划:在自动驾驶或机器人导航中,A* 算法常用于寻找最短路径。
  2. 游戏 AI:在策略游戏中,启发式搜索用于寻找最优策略或路径。
  3. 拼图游戏:如八数码问题,启发式搜索可以帮助找到最少的移动步骤。

总结

启发式搜索通过引入启发式函数,能够有效地减少搜索空间,提高搜索效率。A* 算法是启发式搜索中最常用的算法之一,广泛应用于路径规划、游戏 AI 等领域。理解启发式搜索的基本原理和实现方法,对于解决复杂问题具有重要意义。

附加资源与练习

  • 练习:尝试实现一个解决八数码问题的 A* 算法。
  • 资源:阅读《人工智能:一种现代方法》中关于启发式搜索的章节,深入了解启发式搜索的理论基础。
警告

启发式搜索的性能高度依赖于启发式函数的设计。如果启发式函数设计不当,可能会导致搜索效率低下甚至无法找到最优解。