2020-2021:teams:no_morning_training:weekly:宽度优先搜索及其优化
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:weekly:宽度优先搜索及其优化 [2020/05/22 22:12] nomansland |
2020-2021:teams:no_morning_training:weekly:宽度优先搜索及其优化 [2020/05/29 21:14] (当前版本) nomansland |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| ====优化==== | ====优化==== | ||
| 和深搜一样，裸宽搜基本没什么用。\\ | 和深搜一样，裸宽搜基本没什么用。\\ | ||
| + | ===循环队列=== | ||
| + | 应该算常规操作吧...\\ | ||
| + | 不过还是想列出来。毕竟挺有用的。\\ | ||
| + | ===状态压缩=== | ||
| + | 准确的说不是宽搜特有的优化策略。深搜也用得到。\\ | ||
| + | 因为搜索是对状态进行的操作，所以如何表示一个状态是很重要的一个问题。\\ | ||
| + | 对于许多题目而言，状态的存储可能会占据很大的空间，并且对于后期进行状态间的判断也带来相当大的麻烦。基于此，需要对状态进行压缩表示。\\ | ||
| + | 例如一个大数可以进行取模操作。\\ | ||
| ===剪枝=== | ===剪枝=== | ||
| 不管是深搜还是宽搜，合理地剪枝总是一种简化的好方法。\\ | 不管是深搜还是宽搜，合理地剪枝总是一种简化的好方法。\\ | ||
| - | 当然也包含A*算法\\ | + | 当然也包含[[2020-2021:teams:no_morning_training:a_算法|A*算法]]\\ |
| ===双向宽搜=== | ===双向宽搜=== | ||
| 考虑到随着层数的增加，单层的节点数越来越多，所需的队列空间也越来越大。\\ | 考虑到随着层数的增加，单层的节点数越来越多，所需的队列空间也越来越大。\\ | ||
| 为了解决这个问题，我们可以从起始状态和目标状态一起进行宽搜。\\ | 为了解决这个问题，我们可以从起始状态和目标状态一起进行宽搜。\\ | ||
| 当状态相遇时搜索结束。\\ | 当状态相遇时搜索结束。\\ | ||
2020-2021/teams/no_morning_training/weekly/宽度优先搜索及其优化.1590156775.txt.gz · 最后更改: 2020/05/22 22:12 由 nomansland
