給定一個包含5個節點集的圖,其中2個是目標節點。具有多個目標的A *算法
通過運行該算法,它找到了成本爲7的goal-1節點並終止。
雖然,還有另一個目標,目標-2,成本爲6.
是,找到目標-1作爲第一個解決方案是否正確?或者最佳解決方案是讓A *以6的成本找到目標-2?
給定一個包含5個節點集的圖,其中2個是目標節點。具有多個目標的A *算法
通過運行該算法,它找到了成本爲7的goal-1節點並終止。
雖然,還有另一個目標,目標-2,成本爲6.
是,找到目標-1作爲第一個解決方案是否正確?或者最佳解決方案是讓A *以6的成本找到目標-2?
是的,找到目標1作爲第一個解決方案是否正確?
是正確的,但不是最佳
或者最佳的解決方案是A *,找到目標-2與成本的6 ?
事實上
A *依靠啓發式執行搜索。根據您是在執行「單一目標」還是「多個目標」搜索,您應該提供不同的啓發式。如果你有一個目標admissible heuristic,這並不意味着它可以用於多個目標。
您的初始啓發式是h(x) = somedistance(x,g)
。
通用版本是h'(x) = min{ somedistance(x,gi), gi in GoalSet }
。
它應該找到目標2.啓發式不應該從一個目標搜索到多個目標搜索 – UmNyobe
這是你的功課嗎? –
@UmNyobe:但是A *只是使用一個函數f來計算節點N(g函數)和啓發式函數之間的路徑成本總和就是從當前目標到目標節點的距離。就是說,用數學術語:f(n)= g(n)+ h(n)。 – Chris