疊代加深Ａ*搜尋法(IDA*)

資料來源:http://cindy.cis.nctu.edu.tw/AI96/team02/ida.html 疊代加深是節省記憶體需求的有效方法，利用Ａ*演算法加上 疊代加深的方式，得到的記憶體限制搜尋法，稱之為疊代加 深Ａ*搜尋法(IDA*)。在此演算法中同於疊代加深搜尋法，每 一回的疊代均為一次深度優先搜尋；不同的是，疊代加深搜尋 法中每一回疊代所限制的是搜尋深度，而疊代加深Ａ*搜尋法則 是以f-cost作為限制。換句話說，疊代加深Ａ*搜尋法的每一回的 疊代，即是以f-cost為限制的深度優先搜尋，當所有小於f-cost限 制的節點都已展開，此回合的疊代便算結束，而下回合疊代的 f-cost即是以此回合疊代中超過f-cost限制的最小f-cost。 A* 演算法

Step1 : Put the start node S on a list called OPEN . Set               g(S)<---0      and f(S)<--h(S)    Step2 : If OPEN is empty, exit with failure; otherwise continue.    Step3 : Remove from OPEN that node n whose f-value is smallest 
            and put it on a list called CLOSED.    Step4 : If n is a goal node, exit with the solution path obtained by tracing
           back through the pointers; otherwise continue.    Step5 : Expand node n, generating all of its successors. ( If there are no
            successors, go to Step2. For each successor ni, compute gi<---g(n) c(n,ni).
            c(n,ni) 是由 n 點到 n的第 i 個 successor 的成本    Step6 : If a successor ni is not already on either OPEN or CLOSED, set
             g(ni)<---gi and f(ni)<---gi h(ni).
             Put ni on OPEN and direct a pointer from it back to n.
Step7 : If a successor ni is already on OPEN or CLOSED ,and if g(ni)>gi,
            then update it by setting
             g(ni)<---gi   and f(ni)<---gi h(ni)
            Put ni on OPEN if it was on CLOSED and redirect to n the pointer from ni.
Step8 : Go to Step2 .    

疊代加深Ａ*搜尋法如同Ａ*搜尋法，是完備的(complete)亦是最佳的 (optimal)。由於其為深度優先搜尋，此方法所需要的記憶體空間僅與 所展開最長路徑成正比，約為bd( b為分支因數，d為解題深度)。其時 間複雜度與啟發函數所能得到的數值數目有很大的關係，若一個問題 其搜尋樹每一個節點的啟發函數值均不相同，則每一回疊代只能展開 一個節點，如此展開ｎ個節點便需要ｎ回疊代才能完成。 例如在推銷 員問題中，每一個狀態的啟發函數數值均不相同，此類問題便是疊代 加深Ａ*搜尋法的弱點。 疊代加深Ａ*搜尋演算法

function IDA*(probelm) returns a solution sequence
  inputs: problem, a problem
  static: f-limit, the current f-Cost limit
          root, a node      root<--Make-Node(Initial-State[problem])
  f-limit<--f-Cost(root)
  loop do
    solution,f-limit<--DFS-Contour(root,f-limit)
    if solution is non-null then retuen soluiton
    if f-limit=INF then return failure; end    function DFS-Contour(node,f-limit) return a solution sequence and a new f-Cost limit
  inputs: node, a node
          f-limit, the current f-Cost limit
  static: next-f, the f-Cost limit for the next contour, initially INF      if f_Cost[node]>f-limit then return null, f-Cost[node]
  if Goal-Test[problem](State[node]) then return node,f-limit
  for each node s in Successors(node) do
      solution,new-f<--DFS-Contour(s,f-limit)
      if solutin is non-null then return solution,f-limit
      next-f<--Min(next-f,new-f); end      return null,next-f

疊代加深Ａ*搜尋法執行範例 : 此處所示為疊代加深Ａ*搜尋法的執行範例， 下圖為範例問題的搜尋空間(search space)，每一個節點所標示的 數值代表g h=f，目標節點分別為D，H，圖中以雙圈表示。 演算過程: 網路志工聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]--- 發表人 - axsoft 於 2002/08/23 14:18:26