常用的搜索策略和优化手段
Login to join training plan
在掌握回溯的基础上，还要熟练掌握以下搜索策略和搜索优化手段：
- 剪枝，记忆化，迭代加深
- BFS变形：多起点BFS，多重BFS，双端队列BFS，优先队列BFS
- 双向搜索/折半搜索（Meet in the Middle）
- 状态判重（状压、哈希等手段）
请在洛谷完成 UVA11367 Full Tank? （需先注册 onlinejudge.org 账号并绑定到洛谷）。
Section 1. 最基础的所有人必须能快速写出来的题
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P1706 全排列问题 | 23 | 11 | 6 |
| A1317 【例5.2】组合的输出 | 14 | 11 | 7 |
| B3622 枚举子集（递归实现指数型枚举） | 13 | 11 | 7 |
| A1213 八皇后问题 | 5 | 2 | 10 |
| A1318 【例5.3】自然数的拆分 | 16 | 7 | 8 |
| A1199 全排列 | 7 | 6 | 9 |
| A1473 素数环 | 13 | 6 | 8 |
Section 2. 剪枝与迭代加深
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P10483 小猫爬山 | 96 | 12 | 8 |
| P1120 小木棍 | 268 | 12 | 9 |
| P1731 [NOI1999] 生日蛋糕 | 218 | 9 | 9 |
| P22 「一本通 1.3 例 4」Addition Chains | 42 | 9 | 7 |
| P24 「一本通 1.3 练习 1」埃及分数 | 149 | 10 | 9 |
Section 3. 有趣的BFS变形
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P10485 Bloxorz I | 81 | 9 | 9 |
| P10493 Bloxorz II | 2 | 0 | 10 |
| A1474 矩阵距离 | 29 | 11 | 6 |
| P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修 | 88 | 10 | 9 |
Section 4. 双向搜索/折半搜索（Meet in the Middle）
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P10487 Nightmare II | 46 | 3 | 9 |
| P10484 送礼物 | 8 | 2 | 10 |
Section 5. 状态判重
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P1379 八数码难题 | 70 | 11 | 8 |
| P29 「一本通 1.4 例 2」魔板 | 26 | 13 | 5 |
| P10481 Sudoku | 44 | 5 | 9 |
| P10482 Sudoku 2 | 24 | 4 | 9 |
