第3章：搜索（Solving Problems by Searching）
一、导读
1.1 本章学习目标
第3章介绍了AI中最基本、最广泛使用的问题求解方法——搜索。搜索是将问题求解形式化为在状态空间中寻找从初始状态到目标状态的路径的过程。从简单的迷宫求解到复杂的国际象棋博弈，搜索算法构成了AI系统的核心引擎。
本章的核心学习目标包括：
- 掌握问题形式化的方法：学会将现实世界问题转化为状态空间搜索问题，包括定义状态、初始状态、行动、转移模型、目标测试和路径代价。
- 理解无信息搜索算法：掌握广度优先搜索（BFS）、深度优先搜索（DFS）、迭代加深搜索（IDS）和一致代价搜索（UCS）的原理、实现和性能分析。
- 掌握有信息（启发式）搜索：理解贪心最佳优先搜索和 A* 搜索的原理，掌握启发函数的设计方法，理解可容许性和一致性。
- 理解局部搜索算法：掌握爬山法、模拟退火和遗传算法的原理，理解它们在优化问题中的应用。
- 掌握搜索算法的性能分析方法：能够分析搜索算法的完备性、最优性、时间复杂度和空间复杂度。
- 了解搜索在实际问题中的应用：路径规划、调度、游戏、定理证明等。
1.2 为什么第三章如此重要
搜索是AI的"通用引擎"。本书后续章节中的许多算法——约束满足（第4章）、对抗搜索（第5章）、自动规划（第7章）——本质上都是搜索算法的变体。掌握了搜索，你就掌握了AI问题求解的核心方法论。
更重要的是，搜索算法体现了AI的一个核心思想：将智能行为归结为在状态空间中的系统探索。这种思想不仅适用于传统的问题求解，也适用于现代机器学习中的超参数优化、神经架构搜索等领域。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
为什么盲目搜索在大规模问题中不可行？ 国际象棋的搜索空间有多大？我们如何克服组合爆炸？
启发式函数为什么能大幅提升搜索效率？ A* 算法为什么是最优的？它的"最优性"建立在什么条件上？
时间和空间的权衡：DFS 省空间但可能找不到最优解，BFS 保证最优但空间爆炸。有没有两全其美的方法？
局部搜索与全局搜索的区别：什么时候应该使用局部搜索？爬山法为什么会陷入局部最优？
搜索算法的局限性：搜索方法在处理不确定性、动态环境时有什么不足？
二、核心概念详解
2.1 问题形式化
2.1.1 状态空间搜索的六要素
将一个问题形式化为搜索问题，需要定义以下六个要素：
状态空间（State Space）：所有可能状态的集合
初始状态（Initial State）：问题的起始状态
行动（Actions）：在给定状态下可执行的行动
转移模型（Transition Model）：描述行动结果的函数 Result(s, a) = s'
目标测试（Goal Test）：判断某状态是否为目标状态的函数
路径代价（Path Cost）：路径的总代价，通常是各步代价之和
python
class Problem:
def __init__(self, initial, goal=None):
self.initial = initial
self.goal = goal
def actions(self, state):
raise NotImplementedError
def result(self, state, action):
raise NotImplementedError
def is_goal(self, state):
return state == self.goal
def action_cost(self, state, action, next_state):
return 1
def path_cost(self, path):
return sum(self.action_cost(path[i], path[i+1][1], path[i+1][0])
for i in range(len(path) - 1))
# 八数码问题
class EightPuzzle(Problem):
def __init__(self, initial, goal=(1,2,3,4,5,6,7,8,0)):
super().__init__(tuple(initial), goal)
def actions(self, state):
blank = state.index(0)
row, col = blank // 3, blank % 3
actions = []
if row > 0: actions.append('up')
if row < 2: actions.append('down')
if col > 0: actions.append('left')
if col < 2: actions.append('right')
return actions
def result(self, state, action):
state = list(state)
blank = state.index(0)
row, col = blank // 3, blank % 3
swaps = {'up': (row-1)*3+col, 'down': (row+1)*3+col,
'left': row*3+col-1, 'right': row*3+col+1}
swap = swaps[action]
state[blank], state[swap] = state[swap], state[blank]
return tuple(state)2.1.2 从现实问题到搜索问题
将现实世界问题转化为搜索问题需要适当的抽象。一个具体的状态（如"在武汉长江大桥上"）被抽象为一个搜索状态（如"在武汉"），一个具体的行动（如"以60km/h速度行驶3分钟然后左转"）被抽象为一个搜索行动（如"从武汉到宜昌"）。
好的抽象应该：
- 足够简单：状态空间不能太大以至于无法搜索
- 足够精确：抽象后的解在实际中是可行的
- 足够丰富：能表达足够多的行为选择
2.2 无信息搜索（盲目搜索）
2.2.1 树搜索与图搜索
搜索算法的核心区别在于是否维护已访问状态的记录。树搜索不记录，可能重复访问同一状态；图搜索维护一个"closed list"来避免重复。
python
class Node:
def __init__(self, state, parent=None, action=None, path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
def expand(self, problem):
return [self.child_node(problem, action)
for action in problem.actions(self.state)]
def child_node(self, problem, action):
next_state = problem.result(self.state, action)
return Node(next_state, self, action,
self.path_cost + problem.action_cost(self.state, action, next_state))
def path(self):
node = self
path_back = []
while node:
path_back.append(node)
node = node.parent
return list(reversed(path_back))
def tree_search(problem, strategy):
frontier = [Node(problem.initial)]
while frontier:
node = strategy(frontier)
if problem.is_goal(node.state):
return node.path()
frontier.extend(node.expand(problem))
return None
def graph_search(problem, strategy):
frontier = [Node(problem.initial)]
explored = set()
while frontier:
node = strategy(frontier)
if problem.is_goal(node.state):
return node.path()
explored.add(node.state)
for child in node.expand(problem):
if child.state not in explored and child.state not in [n.state for n in frontier]:
frontier.append(child)
return None2.2.2 广度优先搜索（BFS）
BFS 总是先扩展最浅的节点。它保证在步代价一致时找到最优解，但空间复杂度是指数级的。
python
from collections import deque
def breadth_first_search(problem):
node = Node(problem.initial)
if problem.is_goal(node.state):
return node.path()
frontier = deque([node])
reached = {problem.initial}
while frontier:
node = frontier.popleft()
for child in node.expand(problem):
s = child.state
if problem.is_goal(s):
return child.path()
if s not in reached:
reached.add(s)
frontier.append(child)
return None
# 性能分析
# 时间复杂度: O(b^d)，其中 b 是分支因子，d 是目标深度
# 空间复杂度: O(b^d)
# 完备性: 是（在有限状态空间中）
# 最优性: 是（当所有步代价相等时）2.2.3 深度优先搜索（DFS）
DFS 总是先扩展最深的节点。它空间效率高，但不保证最优性，且在无限状态空间中可能不完备。
python
def depth_first_search(problem):
frontier = [Node(problem.initial)]
reached = set()
while frontier:
node = frontier.pop()
if problem.is_goal(node.state):
return node.path()
reached.add(node.state)
for child in reversed(node.expand(problem)):
if child.state not in reached:
frontier.append(child)
return None
# 性能分析
# 时间复杂度: O(b^m)，其中 m 是最大深度
# 空间复杂度: O(b*m)
# 完备性: 否（在无限状态空间中）
# 最优性: 否2.2.4 一致代价搜索（UCS）
UCS 总是先扩展路径代价最小的节点。它是步代价不一致时的最优搜索算法。
python
import heapq
def uniform_cost_search(problem):
node = Node(problem.initial)
if problem.is_goal(node.state):
return node.path()
frontier = [(0, id(node), node)]
reached = {problem.initial: node.path_cost}
while frontier:
_, _, node = heapq.heappop(frontier)
if problem.is_goal(node.state):
return node.path()
for child in node.expand(problem):
s = child.state
if s not in reached or child.path_cost < reached[s]:
reached[s] = child.path_cost
heapq.heappush(frontier, (child.path_cost, id(child), child))
return None2.2.5 迭代加深搜索（IDS）
IDS 结合了 BFS 的空间效率和 DFS 的时间效率。它对深度限制从 0 开始逐步增加。
python
def iterative_deepening_search(problem):
for depth in range(100000):
result = depth_limited_search(problem, depth)
if result != 'cutoff':
return result
return None
def depth_limited_search(problem, limit):
def recursive_dls(node, limit):
if problem.is_goal(node.state):
return node.path()
if limit == 0:
return 'cutoff'
cutoff = False
for child in node.expand(problem):
result = recursive_dls(child, limit - 1)
if result == 'cutoff':
cutoff = True
elif result is not None:
return result
return 'cutoff' if cutoff else None
return recursive_dls(Node(problem.initial), limit)2.3 有信息搜索（启发式搜索）
2.3.1 启发式函数
启发式函数 h(n) 估计从状态 n 到目标状态的最低代价。它是搜索算法的"指南针"，引导搜索方向。
python
# 八数码问题的启发式函数
def misplaced_tiles(state, goal=(1,2,3,4,5,6,7,8,0)):
return sum(1 for i in range(9) if state[i] != goal[i] and state[i] != 0)
def manhattan_distance(state, goal=(1,2,3,4,5,6,7,8,0)):
distance = 0
for i in range(9):
if state[i] == 0:
continue
target_pos = goal.index(state[i])
distance += abs(i // 3 - target_pos // 3) + abs(i % 3 - target_pos % 3)
return distance
# 比较两种启发式
state = (3, 1, 2, 4, 0, 5, 6, 7, 8)
print(f"错位 tiles: {misplaced_tiles(state)}")
print(f"曼哈顿距离: {manhattan_distance(state)}")2.3.2 A* 搜索
A* 搜索使用评估函数 f(n) = g(n) + h(n)，其中 g(n) 是从初始状态到 n 的实际代价，h(n) 是从 n 到目标的估计代价。
关键定理：如果 h(n) 是可容许的（admissible，即从不高估实际代价），A 树搜索是最优的。如果 `h(n)` 还满足**一致性**（consistent），A 图搜索也是最优的。
python
def astar_search(problem, h):
node = Node(problem.initial)
if problem.is_goal(node.state):
return node.path()
f = lambda n: n.path_cost + h(n.state)
frontier = [(f(node), id(node), node)]
reached = {problem.initial: node.path_cost}
while frontier:
_, _, node = heapq.heappop(frontier)
if problem.is_goal(node.state):
return node.path()
for child in node.expand(problem):
s = child.state
if s not in reached or child.path_cost < reached[s]:
reached[s] = child.path_cost
heapq.heappush(frontier, (f(child), id(child), child))
return None
# 使用 A* 求解八数码
puzzle = EightPuzzle([3, 1, 2, 4, 0, 5, 6, 7, 8])
solution = astar_search(puzzle, manhattan_distance)
if solution:
print(f"找到解！步数: {len(solution) - 1}")
for node in solution:
state = node.state
print(f"{state[0]} {state[1]} {state[2]}")
print(f"{state[3]} {state[4]} {state[5]}")
print(f"{state[6]} {state[7]} {state[8]}")
print()2.3.3 启发式函数的设计
好的启发式函数需要满足：
可容许性（Admissibility）：h(n) ≤ h*(n)，其中 h*(n) 是实际最低代价
一致性（Consistency）：h(n) ≤ c(n,a,n') + h(n')
信息量：h(n) 越接近 h*(n) 越好
python
# 通过松弛问题来设计启发式
# 八数码的松弛：忽略某些约束
def relaxed_manhattan(state, goal=(1,2,3,4,5,6,7,8,0)):
return manhattan_distance(state, goal)
# 模式数据库启发式：预计算子问题的精确解
class PatternDatabase:
def __init__(self, pattern):
self.pattern = pattern
self.table = {}
self._build()
def _build(self):
from collections import deque
goal = tuple(0 if t not in self.pattern else t for t in range(9))
self.table[goal] = 0
queue = deque([goal])
while queue:
state = queue.popleft()
cost = self.table[state]
blank = state.index(0)
row, col = blank // 3, blank % 3
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = row+dr, col+dc
if 0 <= nr < 3 and 0 <= nc < 3:
swap = nr*3+nc
new_state = list(state)
new_state[blank], new_state[swap] = new_state[swap], new_state[blank]
new_state = tuple(new_state)
if new_state not in self.table:
self.table[new_state] = cost + 1
queue.append(new_state)
def __call__(self, state):
abstract = tuple(t if t in self.pattern or t == 0 else 0 for t in state)
return self.table.get(abstract, float('inf'))
# 组合启发式：取多个可容许启发式的最大值
def max_heuristic(state, heuristics):
return max(h(state) for h in heuristics)2.4 局部搜索算法
2.4.1 爬山法（Hill Climbing）
爬山法是一种贪心局部搜索算法，它总是向邻域中最好的邻居移动。
python
def hill_climbing(problem, max_iterations=1000):
current = problem.initial
for _ in range(max_iterations):
neighbors = problem.neighbors(current)
if not neighbors:
break
best_neighbor = max(neighbors, key=problem.value)
if problem.value(best_neighbor) <= problem.value(current):
return current
current = best_neighbor
return current
# N 皇后问题
class NQueensProblem:
def __init__(self, n):
self.n = n
self.initial = list(range(n))
import random
random.shuffle(self.initial)
def value(self, state):
attacks = 0
for i in range(len(state)):
for j in range(i+1, len(state)):
if state[i] == state[j]:
attacks += 1
if abs(state[i] - state[j]) == abs(i - j):
attacks += 1
return -attacks
def neighbors(self, state):
neighbors = []
for i in range(len(state)):
for j in range(len(state)):
if i != j:
new_state = list(state)
new_state[i], new_state[j] = new_state[j], new_state[i]
neighbors.append(tuple(new_state))
return neighbors
problem = NQueensProblem(8)
solution = hill_climbing(problem)
print(f"爬山法解: {solution}, 冲突数: {-problem.value(solution)}")2.4.2 模拟退火（Simulated Annealing）
模拟退火通过引入"温度"参数，允许以一定概率接受更差的解，从而避免陷入局部最优。
python
import math
import random
def simulated_annealing(problem, schedule=None, max_iterations=10000):
if schedule is None:
schedule = lambda t: 100 * (0.995 ** t)
current = problem.initial
for t in range(max_iterations):
T = schedule(t)
if T == 0:
return current
neighbors = problem.neighbors(current)
if not neighbors:
return current
next_state = random.choice(neighbors)
delta_e = problem.value(next_state) - problem.value(current)
if delta_e > 0 or random.random() < math.exp(delta_e / T):
current = next_state
return current
# 使用模拟退火求解 N 皇后
problem = NQueensProblem(8)
solution = simulated_annealing(problem)
print(f"模拟退火解: {solution}, 冲突数: {-problem.value(solution)}")2.4.3 遗传算法（Genetic Algorithm）
遗传算法模拟自然进化过程，通过选择、交叉和变异来搜索解空间。
python
import random
def genetic_algorithm(problem, population_size=100, max_generations=500,
mutation_rate=0.1):
population = [problem.random_state() for _ in range(population_size)]
for generation in range(max_generations):
fitness_values = [problem.fitness(ind) for ind in population]
if max(fitness_values) == problem.max_fitness():
return population[fitness_values.index(max(fitness_values))]
new_population = []
for _ in range(population_size):
parent1 = tournament_select(population, fitness_values)
parent2 = tournament_select(population, fitness_values)
child = problem.crossover(parent1, parent2)
if random.random() < mutation_rate:
child = problem.mutate(child)
new_population.append(child)
population = new_population
return max(population, key=problem.fitness)
def tournament_select(population, fitness_values, k=3):
indices = random.sample(range(len(population)), k)
best = max(indices, key=lambda i: fitness_values[i])
return population[best]
# N 皇后的遗传算法
class NQueensGA:
def __init__(self, n):
self.n = n
def random_state(self):
state = list(range(self.n))
random.shuffle(state)
return state
def fitness(self, state):
max_attacks = self.n * (self.n - 1) // 2
attacks = 0
for i in range(len(state)):
for j in range(i+1, len(state)):
if state[i] == state[j] or abs(state[i]-state[j]) == abs(i-j):
attacks += 1
return max_attacks - attacks
def max_fitness(self):
return self.n * (self.n - 1) // 2
def crossover(self, p1, p2):
cut = random.randint(0, self.n - 1)
child = p1[:cut]
for gene in p2:
if gene not in child:
child.append(gene)
return child
def mutate(self, state):
i, j = random.sample(range(self.n), 2)
state[i], state[j] = state[j], state[i]
return state
ga = NQueensGA(8)
solution = genetic_algorithm(ga)
print(f"遗传算法解: {solution}, 适应度: {ga.fitness(solution)}")三、实战案例
3.1 案例一：地图路径规划
python
import heapq
class MapProblem:
def __init__(self, graph, start, goal):
self.graph = graph
self.start = start
self.goal = goal
self.initial = start
def actions(self, state):
return list(self.graph[state].keys())
def result(self, state, action):
return action
def is_goal(self, state):
return state == self.goal
def action_cost(self, state, action, next_state):
return self.graph[state][action]
# 罗马尼亚地图
romania_map = {
'Arad': {'Sibiu': 140, 'Timisoara': 118, 'Zerind': 75},
'Sibiu': {'Arad': 140, 'Fagaras': 99, 'Rimnicu': 80, 'Oradea': 151},
'Fagaras': {'Sibiu': 99, 'Bucharest': 211},
'Bucharest': {'Fagaras': 211, 'Giurgiu': 90, 'Pitesti': 101, 'Urziceni': 85},
'Pitesti': {'Bucharest': 101, 'Rimnicu': 97, 'Craiova': 138},
'Rimnicu': {'Sibiu': 80, 'Pitesti': 97, 'Craiova': 146},
'Timisoara': {'Arad': 118, 'Lugoj': 111},
'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
'Mehadia': {'Lugoj': 70, 'Drobeta': 75},
'Drobeta': {'Mehadia': 75, 'Craiova': 120},
'Craiova': {'Drobeta': 120, 'Rimnicu': 146, 'Pitesti': 138},
'Zerind': {'Arad': 75, 'Oradea': 71},
'Oradea': {'Zerind': 71, 'Sibiu': 151},
'Giurgiu': {'Bucharest': 90},
'Urziceni': {'Bucharest': 85, 'Vaslui': 142, 'Hirsova': 98},
'Vaslui': {'Urziceni': 142, 'Iasi': 92},
'Iasi': {'Vaslui': 92, 'Neamt': 87},
'Neamt': {'Iasi': 87},
'Hirsova': {'Urziceni': 98, 'Eforie': 86},
'Eforie': {'Hirsova': 86},
}
# 直线距离启发式
straight_line = {
'Arad': 366, 'Bucharest': 0, 'Craiova': 160, 'Drobeta': 242,
'Eforie': 161, 'Fagaras': 176, 'Giurgiu': 77, 'Hirsova': 151,
'Iasi': 226, 'Lugoj': 244, 'Mehadia': 241, 'Neamt': 234,
'Oradea': 380, 'Pitesti': 100, 'Rimnicu': 193, 'Sibiu': 253,
'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374,
}
problem = MapProblem(romania_map, 'Arad', 'Bucharest')
solution = astar_search(problem, lambda s: straight_line.get(s, 0))
if solution:
path = [n.state for n in solution]
cost = solution[-1].path_cost
print(f"路径: {' → '.join(path)}")
print(f"总代价: {cost}")3.2 案例二：搜索算法性能对比
python
import time
def compare_search_algorithms(problem, h=None):
results = {}
start = time.time()
bfs_result = breadth_first_search(problem)
results['BFS'] = {'time': time.time() - start,
'found': bfs_result is not None,
'nodes': len(set(str(n.state) for n in (bfs_result or [])))}
start = time.time()
dfs_result = depth_first_search(problem)
results['DFS'] = {'time': time.time() - start,
'found': dfs_result is not None,
'nodes': len(set(str(n.state) for n in (dfs_result or [])))}
start = time.time()
ids_result = iterative_deepening_search(problem)
results['IDS'] = {'time': time.time() - start,
'found': ids_result is not None,
'nodes': len(set(str(n.state) for n in (ids_result or [])))}
if h:
start = time.time()
astar_result = astar_search(problem, h)
results['A*'] = {'time': time.time() - start,
'found': astar_result is not None,
'nodes': len(set(str(n.state) for n in (astar_result or [])))}
for name, r in results.items():
print(f"{name}: 找到={r['found']}, 时间={r['time']:.4f}s")
puzzle = EightPuzzle([1, 4, 2, 3, 0, 5, 6, 7, 8])
compare_search_algorithms(puzzle, manhattan_distance)四、本章小结
本章系统介绍了搜索算法——AI中最基本的问题求解方法。我们从问题形式化开始，学习了如何将现实问题转化为状态空间搜索问题。然后详细讲解了无信息搜索（BFS、DFS、UCS、IDS）和有信息搜索（贪心搜索、A*搜索），以及局部搜索（爬山法、模拟退火、遗传算法）。
核心知识点回顾：
- 问题形式化六要素：状态空间、初始状态、行动、转移模型、目标测试、路径代价
- BFS 保证最优但空间爆炸；DFS 省空间但不保证最优
- A* 搜索在可容许启发式下是最优的
- 启发式函数设计：通过松弛问题获得下界
- 局部搜索适合优化问题，但可能陷入局部最优
- 模拟退火和遗传算法通过随机性避免局部最优
五、思考与练习
思考题
A* 的效率：为什么好的启发式函数能大幅减少 A* 搜索的节点扩展数？考虑两个可容许启发式 h1 和 h2，如果对所有 n 都有 h2(n) > h1(n)，为什么 h2 比 h1 更好？
组合爆炸：国际象棋的平均分支因子约为 35，平均游戏长度约为 80 步。计算完整的博弈树有多少个叶节点？这说明了什么问题？
局部搜索的适用性：在什么情况下，局部搜索比系统性搜索更适合？给出三个适合使用局部搜索的实际问题。
编程练习
实现双向搜索：实现双向 BFS，从初始状态和目标状态同时搜索，在中间相遇。比较它与普通 BFS 的性能差异。
设计启发式函数：为"传教士与野人"问题设计一个可容许的启发式函数，并用 A* 搜索求解。
遗传算法优化：用遗传算法求解旅行商问题（TSP），比较不同种群大小和变异率对解质量的影响。