人工智能入门扩展内容
状态空间搜索
把问题表示成状态和动作，在可能路径中寻找通往目标的方案。
前置知识
通俗直觉
像在迷宫中找出口：每个位置是状态，每次移动是动作，搜索算法决定先探索哪条路。
核心原理
广度优先搜索按层扩展节点，在边代价相同的图上可以找到步数最少的解。
数学公式
b 是分支因子，d 是最浅解深度，说明搜索空间会指数增长。
工作流程
- 1
建立初始状态队列
- 2
取出最早加入的状态
- 3
扩展未访问邻居
- 4
遇到目标后回溯路径
代码示例
状态空间搜索 示例
Python
example.py用途：队列保存当前节点及其完整路径。先进入队列的浅层节点会先被探索，因此得到最短步数路径。
from collections import deque
def bfs(graph, start, goal):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == goal:
return path
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append((nxt, path + [nxt]))代码解析
队列保存当前节点及其完整路径。先进入队列的浅层节点会先被探索，因此得到最短步数路径。
- — deque 保证先进先出
- — visited 防止在环中重复搜索
应用场景
- 路径规划
- 游戏求解
- 任务调度
常见误区
忘记处理重复状态
把最少步数误认为最低代价
推荐学习资料
视频课程A 级
CS50’s Introduction to Artificial Intelligence with Python
通过搜索、知识表示、概率、优化、机器学习与语言项目学习 AI 基础。
Brian Yu / David J. Malan · Harvard CS50
资料笔记
书籍A 级
Artificial Intelligence: A Modern Approach
以统一框架组织搜索、知识、推理、规划、学习、智能体和机器人等主题。
Stuart Russell / Peter Norvig · AIMA
资料笔记
视频课程B 级
UC Berkeley CS188 Introduction to AI
覆盖智能体、搜索、博弈、概率推理、MDP、强化学习和机器学习。
UC Berkeley EECS · UC Berkeley