启发式搜索

介绍

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

启发式搜索常用于以下场景：

路径规划（如A*算法）
人工智能中的问题求解（如博弈树搜索）
组合优化问题（如旅行商问题）

核心概念

启发式函数

启发式函数 $h (n)$ 用于估计从当前节点 $n$ 到目标节点的最低成本。该函数必须满足以下条件：

可采纳性（Admissibility）： $h (n)$ 不能高估实际成本，即 $h (n) \leq h^{*} (n)$ ，其中 $h^{*} (n)$ 是真实成本。
一致性（Consistency）：对于任意相邻节点 $n$ 和 $n^{'}$ ， $h (n) \leq c (n, n^{'}) + h (n^{'})$ ，其中 $c (n, n^{'})$ 是从 $n$ 到 $n^{'}$ 的实际成本。

常见启发式搜索算法

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

代码示例

以下是一个使用A*算法解决8数码问题（8-Puzzle）的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

输入与输出示例：

初始状态：[[1, 2, 3], [4, 0, 6], [7, 5, 8]]
目标状态：[[1, 2, 3], [4, 5, 6], [7, 8, 0]]
输出：返回从初始状态到目标状态的最短移动序列。

实际应用案例

路径规划

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

游戏AI

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

数学基础

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

最优性条件：

如果 $h (n)$ 可采纳，则A*算法返回最优解。
如果 $h (n)$ 一致，则A*算法高效且无需重复处理节点。

进阶主题

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

总结

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