迭代深化與週期實行A *圖形

我一直在努力實現迭代深化A *算法，在那裏我有一張圖表。我已經看過了維基百科的僞碼週期下面發現：迭代深化與週期實行A *圖形

node    current node 
g     the cost to reach current node 
f     estimated cost of the cheapest path (root..node..goal) 
h(node)   estimated cost of the cheapest path (node..goal) 
cost(node, succ) step cost function 
is_goal(node)  goal test 
successors(node) node expanding function, expand nodes ordered by g + h(node) 

procedure ida_star(root) 
    bound := h(root) 
    loop 
    t := search(root, 0, bound) 
    if t = FOUND then return bound 
    if t = ∞ then return NOT_FOUND 
    bound := t 
    end loop 
end procedure 

function search(node, g, bound) 
    f := g + h(node) 
    if f > bound then return f 
    if is_goal(node) then return FOUND 
    min := ∞ 
    for succ in successors(node) do 
    t := search(succ, g + cost(node, succ), bound) 
    if t = FOUND then return FOUND 
    if t < min then min := t 
    end for 
    return min 
end function

然而問題是這個僞代碼不能處理週期，因爲當進入一個循環時，循環不會終止。如何完成？

來源

2017-04-06 Denjvf

您可以爲每個訪問節點添加一個屬性「color」，然後爲每個節點檢查它是否着色，即已經訪問過。如果是這樣的話，那麼你不會繼續循環。 – Driblou

我假設你指的是後繼者的循環？ – Denjvf

我建議你創建兩個節點列表，並檢查他們的每一次迭代：

打開清單：包含尚未展開的節點。按評估函數f（n）= g（n）+ h（n）分類。最初包含根。要展開節點，您需要從列表中獲得第一個節點。除了你將繼任者添加到列表中。

閉合列表：包含已擴展的節點。當您要展開一個節點時，請檢查它是否不在封閉列表中。如果這是你丟棄它。

希望這會有所幫助。

來源

2017-04-07 08:09:12

迭代深化與週期實行A *圖形

回答

相關問題