4

n個の別々の場所に移動する必要があるn個のロボットがあるロボットシミュレーターを構築しています。すべてのロボットが一斉に動き始めます。ロボットが割り当てられた場所に到達すると、移動が停止します。すべてのロボットがその場所に到達するのに必要な合計時間は、特定のロボットが割り当てられた場所に到達するのに必要な最長時間によって決まります。目的地をロボットに巧みに割り当てることで、この最長の長さを最小限に抑えたいと考えています。

どうやらこの問題は「線形ボトルネック割り当て問題」です。

この問題を解決するコードが見つかりませんでした。これを効率的に解決するための疑似コードまたは実際のコード (任意の言語、Ruby/Java を推奨) を持っている人はいますか?

4

2 に答える 2

2

しきい値アルゴリズムは、線形ボトルネック割り当て問題を解決するための標準アルゴリズムの1つです。簡単に検索しても、ここに簡単にコピーして貼り付けることができる擬似コードは見つかりませんでしたが、ライナー・ブルクハルト、マウロ・デル・アミコ、シルヴァーノ・マーテッロによる「割り当ての問題」の175ページに擬似コードが記載されています。関連するページへのGoogleブックスのリンクは次のとおりです。数ページ後、それらは二重性を利用する別のアルゴリズムを提供しますが、私はそのアルゴリズムに精通していません。

于 2012-11-27T03:56:42.100 に答える
0

LBAP (線形ボトルネック割り当て) は、ケースに関連する割り当ておよびパス ルーティングの問題のファミリ全体の 1 つの特定のサブクラスにすぎません。

n 個のロボットに実装するMinMaxルーティング アルゴリズムを決定する際には、さまざまな選択肢があります。これが私がすることです: Dijkstra の最短パス アルゴリズムの最も単純な実装から始めます。

Dijkstraのウィキペディア ページには素晴らしい視覚的な例がありますが、その疑似コードは必要以上に難解に見えます。あなたの質問からは、実装するパスアルゴリズムを探しているように見えますが、ロボットの動作計画にもリンクしています。

[OP の明確化 re に基づいて更新。最小最大]

Dijkstra は引き続き機能しますが、いくつかの追加手順が必要です。基本的な戦略は次のとおりです。

For each robot r = 1 to n
   calculate the shortest time-path for r from source of r to sink of r - (suggest starting with Dijkstra's) [if you are assuming constant speeds, then distance and length become equivalent]
Next r

MinMax スキーマ:

  1. すべてのパス (時間) を所要時間でソートし、最も長いパスを取得します。(これはあなたの理論的な最小最大時間です。) - それを呼びましょうt_max
  2. 他のロボット r には時間があります"slack"-t_max マイナス time_r
  3. ロボットの各ペアを取り、パスが競合するかどうかを確認します。
    • 競合がなければ完了です。
    • 競合する場合は、ルートを変更する必要があります (競合するノード/エッジの回避) が、スラック タイムの範囲内です。(最も簡単なルート変更は、競合するロボットがエッジまたは交差点を通過するまで待つことです。)
  4. 内でルーティングできればslack完了です。それ以外の場合は、t_max を更新して、最長の (再ルーティングされた) パスにします。

使用できるダイクストラ コードの例を次に示します。（ウェブ検索でさらに多くの情報が得られます。）

  1. http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html (Java)
  2. ここにRubyの要点があります

その他の注意事項：

  1. ダイクストラの方法にとらわれる必要はありません。他のルーティング アルゴリズムが見つかったら、交換して試すことができます。いくつかのルーティング アルゴリズムを試してください。
  2. 競合をチェックすることを忘れないでください。(つまり、2 つのロボットが同時に同じノードにいる場合) コンフリクトフリー ルーティングの最も基本的な実装には、ノードがクリアされるまで 1 つのロボットが先に進む前に待機する優先ルールが含まれます。

それが役立つことを願っています。

于 2012-11-27T20:11:17.503 に答える