我正在做一個需要使用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 *算法。是爲路徑尋找而設計的,我們如何將這個或者其中的一個變體應用於尋找正確方式的問題?
請參閱http://stackoverflow.com/questions/5344705/how-can-the-a-algorithm-be-applied-to-the-traveling-salesman-problem – 2013-04-29 15:45:00
非常感謝。 – 2013-04-29 15:48:14