作者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