A *算法重新頂點

考慮爲A* search algorithm以下僞代碼：A *算法重新頂點

A*(G, s, h) 
    for each vertex u in V 
    d[u] := f[u] := infinity 
    color[u] := WHITE 
    p[u] := u 
    end for 
    color[s] := GRAY 
    d[s] := 0 
    f[s] := h(s) 
    INSERT(Q, s) 
    while (Q != Ø) 
    u := EXTRACT-MIN(Q) 
    for each vertex v in Adj[u] 
     if (w(u,v) + d[u] < d[v]) 
     d[v] := w(u,v) + d[u] 
    f[v] := d[v] + h(v) 
    p[v] := u 
    if (color[v] = WHITE) 
     color[v] := GRAY 
     INSERT(Q, v) 
    else if (color[v] = BLACK) 
     color[v] := GRAY 
     INSERT(Q, v) 
    end if 
     else 
     ... 
    end for 
    color[u] := BLACK 
    end while

現在 - 我理解正確的話，如果我們要找到從源頂點（s）一些目標頂點（路徑讓我們將其命名爲d）那麼我們可以簡單地添加一個檢查的u := EXTRACT-MIN(Q)聲明這樣之後：

u := EXTRACT-MIN(Q) 
    if (u = d) RETURN PATH

這顯然是正確的情況下，我們並不需要重新頂點（else if (color[v] = BLACK），但是正確萬一我們不得不重新打開（例如，如果啓發函數不是單調的）？

來源

2011-12-26 Yippie-Ki-Yay

這是正確的。如果你找到目標節點，那麼你將永遠不必重新打開任何東西;你可以返回路徑。通過A *算法的屬性（包括可接受的啓發式），您首次將目標節點從優先級隊列中彈出，您將擁有最短的路徑。

來源

2011-12-26 19:15:51

實際上，這是您第一次選擇目標節點進行擴展，而不是第一次遇到它。如果在首次生成目標節點時將算法短路，則無法保證找到最短路徑。 – 2011-12-26 19:19:05

@TedHopp：改寫。 – 2011-12-26 19:20:12

A *算法重新頂點

回答

相關問題