1

A* アルゴリズムを使用する必要がある課題に取り組んでいますが、その方法がわかりません。

(0,0)割り当ては、郵便配達員がグリッド マップ上の小包を無限遠から送ることを想像してください。彼は 1 日の初めにタスクのリストを作成し、各タスクには開始点(x1,y1)と終了点が割り当てられています(x2,y2)。2 つのタスクを同時に処理することはできないため、1 つのタスクを終了して終点から次の始点に移動するときに、1 日全体の移動距離が最小になるように、それらのタスクを調整する必要があります。 . 距離は であるマンハッタン距離として計算され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

私の見解では、グラフ（またはマップ）がここで言及されていますが、距離を簡単に計算できるように、それらのタスクを最小限に並べ替えることが重要な部分のみであるため、必要ありません。愚かなことは順列であり、コストが最も低いものを選択しますが、それを採用することはありません。Greedy も試しましたが、グローバルな最適解が得られない可能性があります。

問題は、A* アルゴ以来です。はパス検索用に設計されていますが、正しい方法を見つけるというこの問題に、それまたはそのバリエーションをどのように適用できますか?

4

2 に答える 2

0

これらすべてのポイントを取得し、kd ツリーにフィードします。kd-tree を使用して、任意の点の最近傍を見つけることができます。

A* アルゴの実行中に、最近傍を使用して次のノードを展開します。最も近い隣人によって示されるパスの最後に移動し、再度展開します。削除操作には O( log n ) 平均時間がかかりますが、これが実装に適していることを願っています。

例：

n 個のノードが探索されました

コスト = 31

(0,0) => (1,1) の最近傍を見つける

0 0 から 1 1 に移動

1 1 から 9 2 までキャリー

(9,2) => (3,3) の最近傍を見つける

9 2 から 3 3 に移動

3 3 から 5 3 にキャリー

(5,3) => (5,5) の最近傍を見つける

5 3 から 5 5 に移動

5 5 から 5 7 にキャリー

(5,7) => (3,5) の最近傍を見つける

5 7 から 3 5 に移動

3 5 から 2 7 にキャリー

+++++++++++++++++++++++++++++++++++++++++

kd-tree の概要については、こちらを確認してください: http://en.wikipedia.org/wiki/Travelling_salesman_problem

kd-tree の配列ベースの実装については、このビデオを確認してください: http://www.youtube.com/watch?v=2SbVSxWGtpI

PS:- 各パスの最初のノードのみをツリーに挿入します。そしてもう 1 つ.... 力ずくで大域的な最適解を得ることができます... しかし、多くの時間がかかります。

于 2013-05-02T05:12:42.250 に答える
0

巡回セールスマン問題 (TSP) http://en.wikipedia.org/wiki/Travelling_salesman_problemの変種を解決しようとしていると思います

ジョブ A と B について、A の終点とジョブ B の始点の間のマンハッタン距離を計算し、それを A から B までの距離として扱うことができます。この操作により、問題は TSP に変換されます。

変換後、問題は「A* を使用して巡回セールスマン問題を解決する」となりましたが、これは完全に一致しています。A* アルゴリズムを巡回セールスマン問題にどのように適用できますか?

于 2013-04-29T15:57:10.067 に答える