2014-01-09 79 views
0

給定一個包含5個節點集的圖,其中2個是目標節點。具有多個目標的A *算法

通過運行該算法,它找到了成本爲7的goal-1節點並終止。
雖然,還有另一個目標,目標-2,成本爲6.

是,找到目標-1作爲第一個解決方案是否正確?或者最佳解決方案是讓A *以6的成本找到目標-2?

+0

它應該找到目標2.啓發式不應該從一個目標搜索到多個目標搜索 – UmNyobe

+0

這是你的功課嗎? –

+0

@UmNyobe:但是A *只是使用一個函數f來計算節點N(g函數)和啓發式函數之間的路徑成本總和就是從當前目標到目標節點的距離。就是說,用數學術語:f(n)= g(n)+ h(n)。 – Chris

回答

2

是的,找到目標1作爲第一個解決方案是否正確?

是正確的,但不是最佳

或者最佳的解決方案是A *,找到目標-2與成本的6 ?

事實上

A *依靠啓發式執行搜索。根據您是在執行「單一目標」還是「多個目標」搜索,您應該提供不同的啓發式。如果你有一個目標admissible heuristic,這並不意味着它可以用於多個目標。

您的初始啓發式是h(x) = somedistance(x,g)

通用版本是h'(x) = min{ somedistance(x,gi), gi in GoalSet }

+0

問題如下定義我們的啓發式:從當前節點到目標節點的最小路徑數。所以,我們必須使用這個啓發式功能。考慮到上述情況,找到目標1是一個可接受的解決方案,對吧? A *找到目標1的最佳路徑成本,因爲還有另外一條路徑,其成本爲12. – Chris

+0

在問題中如何實現此功能 – UmNyobe

+0

「最少路徑數」?真的嗎? – UmNyobe