DSA MASTERY · CURRICULUM
Ch.15
回溯与搜索
使用状态空间、选择、撤销与剪枝组织系统搜索。
draft · 草稿学习目标
- 把问题建模为解向量与约束，画出子集树或排列树
- 用选择-探索-撤销的回溯模板实现全排列、子集与 N 皇后
- 用可行性、限界与对称剪枝收缩搜索树，并辨析回溯与分支限界的取舍
从状态空间到剪枝策略
- 15.1 解向量、状态空间树与回溯模板
- 15.2 子集树与排列树：全排列、子集和、N 皇后
- 15.3 可行性、限界与对称去重剪枝
- 15.4 分支限界：队列式与优先队列式搜索
已有内容入口
第 15 章 回溯与搜索：把解空间变成一棵可以搜索的树章节导读15.1 回溯框架：解向量、状态空间树与回溯模板理论文章15.2 子集树与排列树：全排列、子集和与 N 皇后理论文章15.3 可行性、限界与对称去重剪枝理论文章15.4 分支限界：队列式与优先队列式搜索理论文章Lab 15-E-01：全排列问题相关 LabLab 15-E-02：组合的输出相关 LabLab 15-E-03：子集相关 LabLab 15-E-04：选数相关 LabLab 15-E-05：电话号码的字母组合相关 LabLab 15-E-06：迷宫相关 LabLab 15-E-07：奇怪的电梯相关 LabLab 15-E-08：马的遍历相关 LabLab 15-E-09：括号生成相关 LabLab 15-E-10：组合总和相关 LabLab 15-E-11：子集 II相关 LabLab 15-E-12：全排列 II相关 LabLab 15-E-13：组合总和 II相关 LabLab 15-E-14：单词搜索相关 LabLab 15-E-15：分割回文串相关 LabLab 15-E-16：N 皇后相关 LabLab 15-E-17：解数独相关 LabLab 15-E-18：八数码难题相关 LabLab 15-E-19：小木棍相关 LabLab 15-E-20：靶形数独相关 LabLab 15-E-21：骑士精神相关 Lab