2013-04-29 66 views
1

我正在做一個需要使用A *算法的任務,但我無法弄清楚如何。在路線規劃中應用A *算法?

這個任務是,想象一個郵差從(0,0)到無限的網格地圖上發送包裹。他在一天的開始時接受任務清單,每個任務分配一個起點(x1,y1)和一個終點(x2,y2)。由於他不能同時處理兩項任務,所以他必須安排這些任務,以便當他完成一項任務並從終點移動到下一個起點時,他可以在整個一天中保持最小的行駛距離。距離計算爲曼哈頓距離,即d(x1,y1,x2,y2) = abs(x2 - x1) + abs(y2 - y1)

樣本輸入:

Job 3 3 to 5 3  # there is a job from (3,3) to (5,3) 
Job 1 1 to 9 2  # there is a job from (1,1) to (9,2) 
Job 3 5 to 2 7  # there is a job from (3,5) to (2,7) 
Job 5 5 to 5 7  # there is a job from (5,5) to (5,7) 

輸出樣本:

n nodes explored 
cost = 31 
Move from 0 0 to 1 1 
Carry from 1 1 to 9 2 
Move from 9 2 to 3 3 
Carry from 3 3 to 5 3 
Move from 5 3 to 5 5 
Carry from 5 5 to 5 7 
Move from 5 7 to 3 5 
Carry from 3 5 to 2 7 

在我的觀點來看,雖然圖(或地圖)在這裏所提到的,它不是由於只有必要的部分所需是將這些任務排序的最小值,而距離可以很容易計算出來。有些愚蠢的東西是排列組合,選擇成本最低的一個,但從不採用這個。我也嘗試了貪婪,但它可能無法獲得全球最佳解決方案。

所以問題是,因爲A *算法。是爲路徑尋找而設計的,我們如何將這個或者其中的一個變體應用於尋找正確方式的問題?

+0

請參閱http://stackoverflow.com/questions/5344705/how-can-the-a-algorithm-be-applied-to-the-traveling-salesman-problem – 2013-04-29 15:45:00

+0

非常感謝。 – 2013-04-29 15:48:14

回答

0

採取所有這些點,並將其送入kd樹。您可以使用kd-tree來查找任何點的最近鄰居。

運行A *算法時,使用最近的鄰居展開下一個節點。轉到由最近的鄰居表示的路徑的末尾,然後再次展開。刪除操作將花費O(日誌n)的平均時間,我希望這將適用於您的實施。

對於離:

n個節點探索

成本= 31

搜索由0(0,0)=>(1,1)

移動最近鄰0到1 1

從1 1到9 2

從三月3日至5月3日

查找最近鄰查找(9,2)=>(3,3)

移動從9月2日至3月3日

卡里的最近鄰的(5,3)=>(5,5)

移動從3月5日至5月5日

卡里從5月5日至7月5日

查找的(5,7)=>(3,5)

移動從5月7日至3月五日

卡里從3月5日至2月7日

近鄰++++ +++++++++++++++++++++++++

檢查此爲kd-tree概述:http://en.wikipedia.org/wiki/Travelling_salesman_problem

並檢查此視頻是否有基於陣列的kd-tree實現:http://www.youtube.com/watch?v=2SbVSxWGtpI

P.S: - 只插入每個路徑的第一個節點到樹中。還有一件事情......蠻力會給你全球最佳狀態......但是會花費很多時間。

+0

btw ...我忘了在算法中提到...如果您使用A *搜索,則需要將啓發式函數添加到擴展節點的成本中......不確定這將如何幫助您! – metsburg 2013-05-02 05:15:01