-1

すべての配送を完了するための最短経路を計算できるプログラムを作成する必要があります。マップは x、y 座標として表され、パスはマンハッタン距離を使用して計算されます (つまり、x に沿って、次に y に沿って進みます)。開始点は常に (0, 0) であり、クーリエは任意の点で終了できます。宅配業者は一度に 1 パケットしか持ち込めません。

これは A* 検索アルゴリズムを使用して実装できます。私の質問は、A* アルゴリズムは私が作成した検索であるため、statusNode のヒューリスティック値を知る必要があるということです。この問題の適切なヒューリスティック実装は何ですか? それとも、ヒューリスティック値のアイデアですか?

サンプル入力があります：

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)

そして出力:

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

私の現在の検索方法は次のとおりです。

jobToBeDone と jobDone のリストがあります

  1. 現在位置の初期値を初期化します 0, 0

  2. すべてのジョブが完了したかどうかを確認する

  3. そうでない場合は、残りのすべてのジョブについて、合計コスト = そこに到達するためのパス + ジョブのヒューリスティック値を計算します。

  4. それらをjobsToBeDoneに入れ、最短パスでソートするとインデックスが低くなります（JavaのpriorityQueueのように）。

  5. 現在の位置を最初のインデックスのジョブに更新することにより、2 番からの命令を繰り返します。

4

1 に答える 1

0

2 つの問題があります。最短経路と巡回セールスマン。

ポイント間のすべてのパスを計算し、ポイントを並べ替えて最終的な最短ルートを取得する必要があります。最後の部分では、少量のポイントに対してヒューリスティックまたはブルート フォースが必要です。

A* の代わりに Dijkstra と同様に Dijkstra を使用すると、一度に複数のパスを簡単に計算できます (1 対多であるため)。

于 2013-05-08T10:11:25.353 に答える