编辑“︁启发式搜索”︁

{{DISPLAYTITLE:启发式搜索}}

== 介绍 ==
'''启发式搜索'''（Heuristic Search）是一种在[[回溯与分支限界]]算法中广泛使用的优化技术，它通过引入'''启发式函数'''（Heuristic Function）来指导搜索方向，从而减少不必要的计算，提高搜索效率。与盲目搜索（如[[深度优先搜索]]或[[广度优先搜索]]）不同，启发式搜索利用问题领域的额外信息（即启发式信息）来估计当前状态到目标状态的“距离”，从而优先探索更有可能接近目标的路径。

启发式搜索常用于以下场景：
* [[路径规划]]（如A*算法）
* [[人工智能]]中的问题求解（如博弈树搜索）
* [[组合优化]]问题（如旅行商问题）

== 核心概念 ==
=== 启发式函数 ===
启发式函数 <math>h(n)</math> 用于估计从当前节点 <math>n</math> 到目标节点的'''最低成本'''。该函数必须满足以下条件：
* '''可采纳性'''（Admissibility）：<math>h(n)</math> 不能高估实际成本，即 <math>h(n) \leq h^*(n)</math>，其中 <math>h^*(n)</math> 是真实成本。
* '''一致性'''（Consistency）：对于任意相邻节点 <math>n</math> 和 <math>n'</math>，<math>h(n) \leq c(n, n') + h(n')</math>，其中 <math>c(n, n')</math> 是从 <math>n</math> 到 <math>n'</math> 的实际成本。

=== 常见启发式搜索算法 ===
* '''[[贪婪最佳优先搜索]]'''（Greedy Best-First Search）：仅依赖启发式函数 <math>h(n)</math> 选择下一个节点。
* '''[[A*算法]]'''：结合实际成本 <math>g(n)</math> 和启发式函数 <math>h(n)</math>，使用 <math>f(n) = g(n) + h(n)</math> 作为优先级。
* '''[[IDA*算法]]'''：迭代加深的A*算法，节省内存。

== 代码示例 ==
以下是一个使用A*算法解决8数码问题（8-Puzzle）的Python示例：

<syntaxhighlight lang="python">
import heapq

def heuristic(state, target):
    """曼哈顿距离启发式函数"""
    distance = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] != 0:
                x, y = divmod(target[state[i][j]], 3)
                distance += abs(x - i) + abs(y - j)
    return distance

def a_star(start, target):
    open_set = []
    heapq.heappush(open_set, (0 + heuristic(start, target), 0, start))
    came_from = {}
    g_score = {tuple(map(tuple, start)): 0}

    while open_set:
        _, current_g, current = heapq.heappop(open_set)
        if current == target:
            return reconstruct_path(came_from, current)

        for neighbor in get_neighbors(current):
            tentative_g = current_g + 1
            if tentative_g < g_score.get(tuple(map(tuple, neighbor)), float('inf')):
                came_from[tuple(map(tuple, neighbor))] = tuple(map(tuple, current))
                g_score[tuple(map(tuple, neighbor))] = tentative_g
                f_score = tentative_g + heuristic(neighbor, target)
                heapq.heappush(open_set, (f_score, tentative_g, neighbor))
    return None
</syntaxhighlight>

'''输入与输出示例'''：
* 初始状态：<code>[[1, 2, 3], [4, 0, 6], [7, 5, 8]]</code>
* 目标状态：<code>[[1, 2, 3], [4, 5, 6], [7, 8, 0]]</code>
* 输出：返回从初始状态到目标状态的最短移动序列。

== 实际应用案例 ==
=== 路径规划 ===
在导航软件（如Google Maps）中，A*算法用于计算最短路径。启发式函数通常选择两点之间的直线距离（欧几里得距离），因其满足可采纳性。

<mermaid>
graph LR
    A[起点] -->|实际道路距离| B[节点1]
    B -->|h(n)=直线距离| C[目标点]
</mermaid>

=== 游戏AI ===
在策略游戏中，启发式搜索用于优化单位移动或资源分配。例如，《星际争霸》中的AI使用启发式函数评估地图区域的战略价值。

== 数学基础 ==
启发式搜索的性能依赖于启发式函数的质量。定义'''分支因子''' <math>b</math> 和'''有效深度''' <math>d</math>，则A*算法的时间复杂度为 <math>O(b^d)</math>，但实际中因启发式函数的剪枝效果远优于盲目搜索。

最优性条件：
* 如果 <math>h(n)</math> 可采纳，则A*算法返回最优解。
* 如果 <math>h(n)</math> 一致，则A*算法高效且无需重复处理节点。

== 进阶主题 ==
* '''加权A*算法'''：引入权重 <math>w</math> 平衡 <math>g(n)</math> 和 <math>h(n)</math>，即 <math>f(n) = g(n) + w \cdot h(n)</math>。
* '''实时启发式搜索'''：适用于动态环境，如机器人实时避障。

== 总结 ==
启发式搜索通过智能地选择搜索方向显著提升算法效率，但其效果高度依赖启发式函数的设计。开发者需根据具体问题设计合理的启发式函数，以平衡最优性和计算成本。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:回溯与分支限界]]