使用 Python 进行 AI – 启发式搜索

使用 Python 进行人工智能 – 启发式搜索

启发式搜索 (Heuristic search) 是人工智能中用于高效解决复杂问题的基本技术。本章探讨其概念和应用。

理解 AI 中的启发式搜索

启发式方法 (heuristic) 是一种有根据的猜测，或者说是一种“经验法则 (rule of thumb)”，旨在引导搜索算法比穷举法更快地找到可能的解决方案。许多 AI 问题涉及巨大的搜索空间 (search spaces)，使得探索所有可能性变得不切实际。启发式方法通过优先考虑有希望的路径来帮助修剪这个搜索空间。

启发式方法的有效性取决于其估计与目标“接近度”的能力。一个好的启发式方法能显著减少搜索时间，尽管它不总是保证找到绝对最佳解决方案（除非启发式方法具有特定属性，例如 A* 搜索中的可采纳性 (admissibility)）。

无信息搜索 vs. 有信息搜索

搜索策略 (Search strategies) 根据是否使用特定问题知识（启发式方法）大致分类：

无信息搜索 (盲目搜索)

无信息搜索 (Uninformed search) 算法的操作仅基于问题定义（状态、操作符、目标测试），不使用任何领域特定知识。它们系统地探索搜索空间。示例包括：

广度优先搜索 (Breadth-First Search, BFS)：逐层探索。
深度优先搜索 (Depth-First Search, DFS)：在回溯之前尽可能深地探索一个分支。

这些方法是穷举的，对于大型状态空间来说效率可能非常低。

有信息搜索 (启发式搜索)

有信息搜索 (Informed search) 算法使用一个启发式函数 h(n)，该函数估计从状态 ‘n’ 到最近目标的代价。这可以引导搜索朝着更有希望的状态前进。示例包括：

贪婪最佳优先搜索 (Greedy Best-First Search)：根据启发式函数展开看起来最接近目标的节点。
A* 搜索 (A* Search)：结合了到达节点的代价 g(n) 和到目标的估计代价 h(n)。它使用 f(n) = g(n) + h(n)。如果启发式函数 h(n) 是可采纳的（永不高估到目标的真实代价）且一致的（对于通过动作 a 生成的任何节点 n 及其后继节点 n’，h(n) <= cost(n,a,n’) + h(n’)），那么 A* 是最优且完备的。
束搜索 (Beam Search)：最佳优先搜索的一种变体，每一步只保留固定数量（‘beam width’，束宽）的最佳路径。

常见的启发式方法示例包括路径寻找问题中的曼哈顿距离 (Manhattan distance) 或欧几里得距离 (Euclidean distance)。

约束满足问题 (CSPs)

约束满足问题 (Constraint Satisfaction Problems, CSPs) 是一类问题，其目标是找到满足给定约束集（规则或限制）的状态或变量值集合。CSPs 由以下要素定义：

一组变量 (X = {X1, …, Xn})
每个变量的域集 (D = {D1, …, Dn})，定义了可能的取值。
一组约束 (C = {C1, …, Ck})，指定了允许的变量值组合。

CSP 的解是对变量进行完全赋值，使得所有约束都得到满足。回溯搜索 (Backtracking search) 是解决 CSP 的常用算法。

约束满足示例：代数关系

让我们考虑一个简单的代数关系作为一个 CSP：a * 2 = b，其中 ‘a’ 和 ‘b’ 是特定范围内的整数，比如 0 到 9。

这里：

变量：a, b
域：Da = {0, 1, ..., 9}, Db = {0, 1, ..., 9}
约束：a * 2 == b

我们可以通过系统地检查域中的值来解决这个问题：

def solve_algebraic_csp():
    solutions = []
    domain = range(10)
    for a_val in domain:
        for b_val in domain:
            # 检查约束
            if a_val * 2 == b_val:
                solutions.append({'a': a_val, 'b': b_val})
    return solutions

# 获取解决方案
solutions = solve_algebraic_csp()
print(solutions)

上面的 Python 代码定义了一个函数，它遍历 ‘a’ 和 ‘b’ 的可能值，并将有效的对添加到 solutions 列表中。输出将是：

[{'a': 0, 'b': 0}, {'a': 1, 'b': 2}, {'a': 2, 'b': 4}, {'a': 3, 'b': 6}, {'a': 4, 'b': 8}]

对于更复杂的 CSPs，通常使用通用求解器或实现带有前向检查 (forward checking) 或弧相容性 (arc consistency) 等算法的库（例如，Google OR-Tools）。

应用：幻方验证器

幻方 (magic square) 是一个由不同数字组成的网格，其中每行、每列和两个主对角线上的数字之和都相等（这个和称为“幻常数 (magic constant)”）。验证给定方阵是否为幻方是一个约束检查问题。

以下 Python 函数检查给定矩阵是否为幻方：

def is_magic_square(matrix):
    n = len(matrix)
    if n == 0 or any(len(row) != n for row in matrix):
        print("Matrix must be square and non-empty.")
        return False

    sum_list = []

    # 行和
    for r in range(n):
        sum_list.append(sum(matrix[r]))

    # 列和
    for c in range(n):
        current_col_sum = 0
        for r in range(n):
            current_col_sum += matrix[r][c]
        sum_list.append(current_col_sum)

    # 主对角线和 (左上到右下)
    main_diag_sum = 0
    for i in range(n):
        main_diag_sum += matrix[i][i]
    sum_list.append(main_diag_sum)

    # 副对角线和 (右上到左下)
    anti_diag_sum = 0
    for i in range(n):
        anti_diag_sum += matrix[i][n - 1 - i]
    sum_list.append(anti_diag_sum)

    # 检查所有和是否相等
    if len(set(sum_list)) > 1:
        return False
    return True

让我们用一些示例进行测试：

non_magic = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(f"[{non_magic}] 是幻方吗？ {is_magic_square(non_magic)}")

# 一个已知的 3x3 幻方 (幻常数 = 15)
magic_3x3 = [[8, 1, 6], [3, 5, 7], [4, 9, 2]]
print(f"[{magic_3x3}] 是幻方吗？ {is_magic_square(magic_3x3)}")

# 另一个不是幻方的示例
not_magic_either = [[3, 9, 2], [3, 5, 7], [9, 1, 6]]
print(f"[{not_magic_either}] 是幻方吗？ {is_magic_square(not_magic_either)}")

输出：

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] 是幻方吗？ False
[[8, 1, 6], [3, 5, 7], [4, 9, 2]] 是幻方吗？ True
[[3, 9, 2], [3, 5, 7], [9, 1, 6]] 是幻方吗？ False