A *算法的例子 - 它是正確的

enter image description here

如果我使用A *算法，我得到這個sollution：

     S (0+1=1) 
        /  \ 
       /   \ 
      a(3+3=6)    b(2+3=5) 
     / | \    /  \ 
    / |  \   /  \ 
    c(4+0=4) b(6+3=9) d(6+0=6) d(5+0=5) c(7+0=7)

問：哪些解決方案我們發現，使用算法A *和啓發式估計（參見圖）

溶劑：

選擇B（= 5）：

    S (0+1=1) 
       /  \ 
      /   \ 
     a(3+3=6)    b(2+3=5)

選擇d（= 5）：

    S (0+1=1) 
       /  \ 
      /   \ 
     a(3+3=6)    b(2+3=5) 
          /  \ 
          /  \ 
          d(5+0=5) c(7+0=7)

停止搜索 - 因爲「成本5」小於一個（3+ 3 = 6） - >我們不搜索其他解決方案？解決辦法是： S-B-d，成本= 5

，對嗎？

來源

2011-12-29 OldFox

什麼是*問題*？「去D最便宜的方式」？ – Amadan 2011-12-29 09:34:17

問題：我們將使用算法A *和啓發式估計（請參閱圖表）找到哪種解決方案。目標是D或C – OldFox 2011-12-29 09:43:00

是的，似乎是正確的。吮吸C，但這是你得到一個壞的啓發式功能。 – Amadan 2011-12-29 09:46:37

理論上看你寫的是正確的。然而，在運行A *的圖上有一個非常重要的屬性應該是有效的，以便您知道該算法會產生最優解：您使用的啓發式函數應該是樂觀的，即永遠不會高估與目標的真實距離。如果我正確地得到它，你有幾個目標節點C和D，問題是A的啓發式值不樂觀，實際上它高估了（從A到目標節點C的路徑只有1，小於h （A）= 3）。這就是爲什麼你實際上沒有得到最佳解決方案。

來源

2011-12-29 09:48:36

好的，所以s-b-d，cost = 5是這種情況下的解決方案。非常感謝您的解釋。 – OldFox 2011-12-29 10:33:52

A *算法的例子 - 它是正確的

回答

相關問題