启发式搜索

启发式搜索（Heuristic Search）是一种利用问题领域的额外信息（即启发式函数）来引导搜索方向的算法，旨在提高搜索效率并减少不必要的计算。与盲目搜索（如广度优先搜索、深度优先搜索）不同，启发式搜索通过评估当前状态到目标的“潜力”来优化路径选择，常用于解决复杂问题（如路径规划、游戏AI、优化问题等）。

核心概念

启发式搜索的核心是启发式函数（Heuristic Function），记作 $h(n)$，用于估计从当前节点 $n$ 到目标节点的最低成本。该函数的设计直接影响算法的效率和准确性。

常见启发式搜索算法

• A*算法：结合路径成本 $g(n)$ 和启发式函数 $h(n)$，选择 $f(n)=g(n)+h(n)$ 最小的节点扩展。
• 贪婪最佳优先搜索（Greedy Best-First Search）：仅依赖启发式函数 $h(n)$，优先扩展“看似最优”的节点。
• 迭代加深A*（IDA*）：通过动态调整 $f(n)$ 的阈值来优化内存使用。

数学基础

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

• 可采纳性（Admissibility）：$h(n)$ 不得高估实际成本，即 $h(n)\le h^{*}(n)$（$h^{*}(n)$ 为真实成本）。
• 一致性（Consistency）：对于任意相邻节点 $n$ 和 $m$，满足 $h(n)\le c(n,m)+h(m)$（$c(n,m)$ 为边成本）。

代码示例

以下为 Python 实现的 A* 算法示例，解决网格路径规划问题：

  
import heapq  

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

def a_star(grid, start, goal):  
    neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0)]  
    open_set = []  
    heapq.heappush(open_set, (0, start))  
    came_from = {}  
    g_score = {start: 0}  
    f_score = {start: heuristic(start, goal)}  

    while open_set:  
        _, current = heapq.heappop(open_set)  
        if current == goal:  
            path = []  
            while current in came_from:  
                path.append(current)  
                current = came_from[current]  
            return path[::-1]  

        for dx, dy in neighbors:  
            neighbor = (current[0] + dx, current[1] + dy)  
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == 0:  
                tentative_g_score = g_score[current] + 1  
                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] = g_score[neighbor] + heuristic(neighbor, goal)  
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))  
    return None  

# 示例输入：0表示可通行，1表示障碍物  
grid = [  
    [0, 0, 0, 0],  
    [1, 1, 0, 1],  
    [0, 0, 0, 0]  
]  
start = (0, 0)  
goal = (2, 3)  
print(a_star(grid, start, goal))  # 输出：[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3)]

实际应用

1. 游戏AI：如《星际争霸》中的单位寻路。 2. 机器人导航：无人机避开障碍物到达目标点。 3. 自然语言处理：机器翻译中搜索最优译文序列。

性能优化与权衡

• 启发式函数设计：更好的启发式能显著减少搜索空间（如欧几里得距离比曼哈顿距离更精确）。
• 内存限制：IDA* 适用于内存紧张的场景，但可能重复计算。

可视化示例

graph TD A[Start] -->|g=1| B A -->|g=1.4| C B -->|g=2| D C -->|g=2| D D -->|h=0| Goal style A fill:#f9f style Goal fill:#f66

图中数字为

$g(n)$

（路径成本）和

$h(n)$

（启发式估计），A* 会选择总成本

$f(n)$

最低的路径。

总结

启发式搜索通过智能地选择扩展节点，显著提升了搜索效率。理解启发式函数的设计原则和算法特性（如 A* 的最优性）是掌握该技术的关键。实际应用中需根据问题特点权衡速度与精度。