状态空间
1. 状态空间搜索
状态空间搜索是人工智能和算法中解决复杂问题的一种通用框架。 意思是：
把问题的所有可能情况铺开，像走迷宫一样找答案。 例如：
八数码（拼图）怎么还原最快 农夫带羊、狼、菜怎么安全过河 两个不同容量的水杯怎么倒出指定水量 都可以转化为状态空间搜索。
2. 适用条件
状态空间搜索适用于：
问题有明确的“初始局面”和“目标局面” 有清晰的“规则”（每一步能做哪几种选择） 例如：
迷宫只能上下左右走 象棋里的马只能走日字 只要能把局面抽象成节点，把动作抽象成连线，就能用搜索解决。
3. 核心思想
每次从当前局面出发，尝试所有合法的动作：
生成下一步的全新局面 然后继续向下探索。 就像平行宇宙分裂：
起点是一个初始宇宙 每做一个选择，分裂出多个新宇宙 不断衍生，直到在某个宇宙中找到目标。
4. 举例理解
经典问题：农夫过河（带狼、羊、菜）。 初始状态：
全都在左岸。 动作：
农夫带羊过河、带菜过河、自己过河等。 状态转移：
农夫带羊过去 -> 变成新状态：左岸剩狼菜，右岸有农夫和羊。 如果遇到死胡同：
比如农夫带菜走，留下狼和羊 -> 羊被吃，状态淘汰（剪枝）。 不断衍生，直到：
所有人都安全到达右岸（目标状态）。
5. 基础逻辑（核心四要素）
想写代码，必须先理清四个东西：
状态（State）：当前局面长啥样（可以用数组、字符串或整数表示）。 动作（Action）：当前能进行什么操作。 转移（Transition）：做了操作后，状态怎么变化。 目标（Goal）：你想达到什么结果。
6. 最大挑战（状态爆炸）
随着步数增加，状态数量会呈指数级恐怖增长。 例如：
井字棋：几万种状态，随便搜。 三阶魔方：4.3 × 10^19 种状态，盲搜会卡死。 围棋：10^170 种状态，宇宙毁灭也搜不完。 应对方法：
剪枝（提前砍掉明显错误的路线） 启发式算法（A*，预估距离不走弯路）
7. 常见搜索门派（分类）
盲目搜索（暴力）：
BFS（广度优先）：像水波纹一层层蔓延。找最少步数必用，但费内存。 DFS（深度优先）：不撞南墙不回头。求所有方案或走迷宫常用，省内存。 启发式搜索（智能）：
A* 算法：自带雷达，优先探索离终点近的状态。 对抗搜索（博弈）：
Minimax（极小化极大）：下棋 AI 专用，总是假设对手会走出最克制你的棋。
8. 为什么要用哈希表 / vis数组
因为搜索极容易：
走回头路（死循环） 例如：
农夫带羊过去，又带羊回来。 拼图左移一下，又右移回来。 不记录走过的状态：
会无限死循环导致内存耗尽。 所以必须用 Hash、Set 或 vis 数组记录“已经见过的状态”。
9. 常见题型
最少步数问题 拼图还原、迷宫寻路。 连通块问题 扫雷游戏、计算地图上的水洼数量。 棋盘博弈 井字棋、五子棋 AI 核心逻辑。 全排列 / 组合问题 密码破解、旅行商问题（暴力解法）。
10. 常见错误
忘记标记已访问状态 没写 vis 记录，直接陷入死循环爆栈。 状态表示太臃肿 把庞大的二维数组甚至结构体疯狂塞进队列，导致内存超限（MLE）。 应考虑状态压缩（如化为字符串或二进制位运算）。 DFS 没写回溯 尝试完一种情况退回来时，没有把棋盘或状态“恢复原样”，导致后续搜索全错。
11. 如何判断使用状态空间搜索
看到这些关键词：
所有可能方案 最少操作次数（无权重差别时） 棋盘上的移动 倒水 / 倒沙子等逻辑谜题 通常优先考虑 BFS / DFS。
12. 一句话理解
状态空间搜索 = 把所有可能的局面画成一棵无穷大的树，然后像猴子一样在树上爬，直到摘到那颗叫做“目标”的果子。
13. 总结
状态空间搜索是算法和 AI 的基石。 记住三点：
找准状态的表示方法 绝对不能忘记去重（防死循环） 状态太多就果断剪枝或用 A* 大厂笔试、算法竞赛中的大题常客。