启发式搜索
介绍
启发式搜索(Heuristic Search)是一种在搜索过程中利用启发式信息来指导搜索方向的算法。与盲目搜索(如广度优先搜索或深度优先搜索)不同,启发式搜索通过评估当前状态与目标状态之间的“距离”或“代价”,从而优先选择更有可能接近目标的路径。这种方法可以显著减少搜索空间,提高搜索效率。
启发式搜索常用于解决复杂问题,如路径规划、拼图游戏、人工智能中的决策问题等。
启发式函数
启发式搜索的核心是启发式函数(Heuristic Function),通常记作 h(n)
。这个函数用于估计从当前节点 n
到目标节点的代价。启发式函数的设计对算法的性能至关重要,一个好的启发式函数应该满足以下条件:
- 可接受性(Admissibility):启发式函数的值不能高估实际代价。
- 一致性(Consistency):对于任意节点
n
和其子节点n'
,启发式函数应满足h(n) <= cost(n, n') + h(n')
。
提示
启发式函数的设计需要结合具体问题的特性。一个好的启发式函数可以显著提高搜索效率。
A* 算法
A* 算法是启发式搜索中最经典的算法之一。它结合了代价函数 g(n)
(从起点到当前节点的实际代价)和启发式函数 h(n)
,通过计算 f(n) = g(n) + h(n)
来选择最优路径。
A* 算法步骤
- 初始化:将起点加入开放列表(Open List)。
- 循环:
- 从开放列表中选择
f(n)
最小的节点n
。 - 如果
n
是目标节点,则搜索成功,返回路径。 - 否则,将
n
移出开放列表,加入关闭列表(Closed List)。 - 扩展
n
的所有邻居节点,计算它们的f(n)
值,并加入开放列表。
- 从开放列表中选择
- 如果开放列表为空且未找到目标节点,则搜索失败。
代码示例
以下是一个简单的 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)]
实际应用
启发式搜索在许多实际场景中都有广泛应用,例如:
- 路径规划:在自动驾驶或机器人导航中,A* 算法常用于寻找最短路径。
- 游戏 AI:在策略游戏中,启发式搜索用于寻找最优策略或路径。
- 拼图游戏:如八数码问题,启发式搜索可以帮助找到最少的移动步骤。
总结
启发式搜索通过引入启发式函数,能够有效地减少搜索空间,提高搜索效率。A* 算法是启发式搜索中最常用的算法之一,广泛应用于路径规划、游戏 AI 等领域。理解启发式搜索的基本原理和实现方法,对于解决复杂问题具有重要意义。
附加资源与练习
- 练习:尝试实现一个解决八数码问题的 A* 算法。
- 资源:阅读《人工智能:一种现代方法》中关于启发式搜索的章节,深入了解启发式搜索的理论基础。
警告
启发式搜索的性能高度依赖于启发式函数的设计。如果启发式函数设计不当,可能会导致搜索效率低下甚至无法找到最优解。