作者s89162504 (阿本)
站内Prob_Solve
标题[问题] 有关A*跟IDA*
时间Tue Dec 11 20:18:51 2012
新手发问，不好意思
A*是在搜寻时把每个状态做估计值
每次展开结点时都展开目前估计值最优的
但缺点是耗费记忆体太大
所以解决方法是用迭代加深搜寻，也就是IDA*
以下是我的问题：
为什麽我看网路上IDA*的程式码时候
在储存待展开节点可以直接用Stack存
应该说是不需要用优先伫列
另外
好像连目前这个节点是否已出现过都不用判断
不好意思，请问这是怎麽回事
我有甚麽盲点吗
先谢谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.200.146
1F：推 suhorng:判断重复=>要储存节点=>还是跟A*一样太花空间 12/11 20:23
2F：→ suhorng:IDA*会搜到重复的节点 但是相对於需要搜索的空间大小实在 12/11 20:23
3F：→ suhorng:太微不足道 就不管他 12/11 20:24
4F：→ suhorng:IDA*的确 *不* 使用优先伫列 12/11 20:27
5F：→ suhorng:请回想优先伫列在 A* 中的用途: f(n)值小的节点会先被扩展 12/11 20:31
6F：→ suhorng:那IDA*在跑的时候, f 的上限是 *渐次加深* 的 12/11 20:32
7F：→ suhorng:也就是可能第一次是 1, 再来是 2, 再来是 3, ... 12/11 20:32
8F：→ suhorng:同样, 这可以保证若 f 较大的已经被搜索到了, 那 f 较小的 12/11 20:32
9F：→ suhorng:也一定会被搜索过, 从而同样保证了正确性 12/11 20:33
10F：→ suhorng:而迭代加深的写法, 正是可以省掉优先伫列的空间消耗 12/11 20:34
11F：→ s89162504:原来如此，谢谢!! 12/11 23:29