2

単純化しすぎた例として、出席者が最大のイベントのリストがあります。

 event    | places
===================
 event_A  |   1
 event_B  |   2
 event_C  |   1

そして、イベントまでの距離を含む出席者のリスト:

 attendee    | event_A dist | event_B dist | event_C dist
==========================================================
 attendee_1  |      12      |      15      |      12      
 attendee_2  |      11      |      15      |      11
 attendee_3  |      10      |      11      |      12

最短の合計距離と最短の平均距離に基づいて最良のケースの割り当てを提供する一連のオプションを作成する簡単な方法を誰かが提案できますか?

現在、データは Oracle Spatial データベースに保持されていますが、提案は受け付けています。

4

1 に答える 1

0

私は現在、あなたの問題を次のように理解しています：

  • 各出席者は、正確に 1 つのイベントに割り当てられる必要があります
  • 各イベントには、割り当てられる出席者の数に制限があります
  • 不足しているイベントや空のイベントでも問題ありません
  • イベントと出席者の間の各割り当ては、指定された距離に対応します
  • すべての割り当ての全体的な距離を最小限に抑えたい
  • 合計ではなく平均を使用して結果を出力したい場合があります。

この解釈に基づいて、次のアルゴリズムを提案します。

  1. 参加者用のパーティションAのノードと、イベントの場所用のパーティションBのノードを使用して、完全な 2 部グラフを作成します。したがって、すべての出席者は 1 つのノードに対応し、すべてのイベントは場所と同じ数のノードに対応します。すべての参加者は、距離をエッジ コストとしてすべてのイベント ノードに接続されます。

    この時点で、あなたの問題は一般的な課題の問題に対応し、「エージェント」はイベントの場所に対応し、「タスク」は出席者に対応します。すべての出席者をカバーする必要がありますが、すべてのイベント場所を使用する必要はありません。

  2. ダミーの出席者を追加して、完全に一致させます。単純にすべての場所を合計し、そこから実際の参加者数を引きます。違いとして、すべてのイベント ノードまでの距離をゼロにして、できるだけ多くの参加者ノードを作成します。

    両方のパーティションのサイズを同じにすることで、より一般的な線形割り当て問題の領域に入ります。

  3. ハンガリアン アルゴリズムを使用して、最小コストの割り当てを計算します。おそらく、同等のノードが多数あるという事実を利用するいくつかの単純化を考えることができます。つまり、同じイベントの場所とすべてのダミー出席者です。

これらはすべて、データベースではなく、アプリケーション コードで実行する必要があります。にタグを付けたいと思います。エッジのコストを提供するには、データベースから完全なコスト マトリックスを取得する必要があります。

于 2013-02-21T10:16:53.660 に答える