2020-2021:teams:no_morning_training:a_算法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:no_morning_training:a_算法 [2020/05/24 17:56] nomansland |
2020-2021:teams:no_morning_training:a_算法 [2020/05/29 21:28] (当前版本) nomansland |
||
|---|---|---|---|
| 行 28: | 行 28: | ||
| -直线距离。 | -直线距离。 | ||
| -曼哈顿方法，即在瓦块图中，水平距离加垂直距离。 | -曼哈顿方法，即在瓦块图中，水平距离加垂直距离。 | ||
| + | ====IDA*算法==== | ||
| + | A*算法存在一定的缺陷。\\ | ||
| + | 我们需要维护一个灰色和黑色节点列表，并且需要不时进行排序操作，需要占用大量的空间和时间。\\ | ||
| + | 为了结局这个问题，我们引入了ID（迭代加深）的思想，也就是在[[2020-2021:teams:no_morning_training:深度优先搜索及其优化|深搜]]里提到的限制深度。\\ | ||
| + | 我们设定一个H函数的阈值maxH，其最初为初始点的H值。然后进行深度优先搜索，过程中忽略所有H值大于maxH的节点；若没有解，则加大阈值maxH，重复。\\ | ||
| + | IDA*算法的优点是不用排序，不用保存节点。\\ | ||
| + | 也可把IDA*理解为在IDDFS基础上加了A*算法里F函数的剪枝。 | ||
2020-2021/teams/no_morning_training/a_算法.1590314193.txt.gz · 最后更改: 2020/05/24 17:56 由 nomansland
