PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 有關A*跟IDA*

看板Prob_Solve (計算數學 Problem Solving)作者 (阿本)時間12年前 (2012/12/11 20:18), 編輯推噓1(1推 0噓 10→)
留言11則, 2人參與, 最新討論串1/1
新手發問，不好意思 A*是在搜尋時把每個狀態做估計值 每次展開結點時都展開目前估計值最優的 但缺點是耗費記憶體太大 所以解決方法是用迭代加深搜尋，也就是IDA* 以下是我的問題： 為什麼我看網路上IDA*的程式碼時候 在儲存待展開節點可以直接用Stack存 應該說是不需要用優先佇列 另外 好像連目前這個節點是否已出現過都不用判斷 不好意思，請問這是怎麼回事 我有甚麼盲點嗎 先謝謝大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.200.146
推
12/11 20:23, , 1F
判斷重複=>要儲存節點=>還是跟A*一樣太花空間
12/11 20:23, 1F
→
12/11 20:23, , 2F
IDA*會搜到重複的節點 但是相對於需要搜索的空間大小實在
12/11 20:23, 2F
→
12/11 20:24, , 3F
太微不足道 就不管他
12/11 20:24, 3F
→
12/11 20:27, , 4F
IDA*的確 *不* 使用優先佇列
12/11 20:27, 4F
→
12/11 20:31, , 5F
請回想優先佇列在 A* 中的用途: f(n)值小的節點會先被擴展
12/11 20:31, 5F
→
12/11 20:32, , 6F
那IDA*在跑的時候, f 的上限是 *漸次加深* 的
12/11 20:32, 6F
→
12/11 20:32, , 7F
也就是可能第一次是 1, 再來是 2, 再來是 3, ...
12/11 20:32, 7F
→
12/11 20:32, , 8F
同樣, 這可以保證若 f 較大的已經被搜索到了, 那 f 較小的
12/11 20:32, 8F
→
12/11 20:33, , 9F
也一定會被搜索過, 從而同樣保證了正確性
12/11 20:33, 9F
→
12/11 20:34, , 10F
而迭代加深的寫法, 正是可以省掉優先佇列的空間消耗
12/11 20:34, 10F
→
12/11 23:29, , 11F
原來如此，謝謝!!
12/11 23:29, 11F
‣ 更多 s89162504 的文章
文章代碼(AID): #1GnoIjaE (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 s89162504 的文章
文章代碼(AID): #1GnoIjaE (Prob_Solve)