编辑“︁启发式搜索”︁

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

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

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

== 数学基础 ==  
启发式函数需满足以下条件：  
* '''可采纳性'''（Admissibility）：<math>h(n)</math> 不得高估实际成本，即 <math>h(n) \leq h^*(n)</math>（<math>h^*(n)</math> 为真实成本）。  
* '''一致性'''（Consistency）：对于任意相邻节点 <math>n</math> 和 <math>m</math>，满足 <math>h(n) \leq c(n, m) + h(m)</math>（<math>c(n, m)</math> 为边成本）。  

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

<syntaxhighlight lang="python">  
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)]  
</syntaxhighlight>  

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

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

== 可视化示例 ==  
<mermaid>  
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  
</mermaid>  
图中数字为 <math>g(n)</math>（路径成本）和 <math>h(n)</math>（启发式估计），A* 会选择总成本 <math>f(n)</math> 最低的路径。  

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:搜索算法]]