4

いくつかのイベントに人を割り当てる必要がある状況があります。価格を要因として考えれば問題ありませんが、いくつかの要因があります。

まず、いくつかの背景。これは、何らかの理由で入院している子供たちの話の時間を促進する非営利団体のためのものであり、そうするために彼らは自主的な仕事に依存しています。したがって、彼らは人々の善意に依存しているので、人々ができる/やりたいと思う限り多くの仕事を人々に与えます。それは次のように異なります。

  • 朝しかできない人もいれば、午後しかできない人もいます。
  • 月曜日しかできない人もいれば、木曜日は行けない人もいます。
  • 月に1回しか行けない人もいれば、4回行ける人もいます（そして、経験が豊富で月に10回できるので、これらのアクションで「優先」が与えられる人もいます）。

それで、私はちょっと最初の2つを理解しました。ハンガリーのアルゴリズムは価格に関するものなので、私は彼らが行けない時のために彼らにばかげて高い価格を与えるでしょう。しかし、他の人はどうしますか？

私は彼らにある種のスコアを与えることを考えました。月に一度これを行うことができる1人の人は1000ポイントのようなものがかかります。誰かが月に10回行くことができる場合、その人は100ポイント（1000ベースを10で割ったもの）の費用がかかります。また、これを配布する方法は、次のように、別のアクションが実行されるたびに価格を上げることです（選択された人は関連するコストに*があります）。

最初の反復

         | August 1st 2009
Person A | 1000
Person B | 500 *

2回目の反復

         | August 8th 2009
Person A | 1000 *
Person B | 1000

これは、すべての人々の間でそれに応じて分配する方法であり、これを数回行うことができる人々により優先されます。

あなたはどう思いますか、そしてそれをどのように行いますか？

4

1 に答える 1

15

これはスケジューリング/最適化の問題であるため、重要な質問は「最大化しようとしている量」です。各ボランティアの時間割の制約を条件として、衝突することなくすべてのボランティアで働いた合計時間数を最大化しようとしていると思います。また、経験豊富なボランティアを優先するとおっしゃっていますので、「ボランティアの方が他のボランティアよりも好まれている」とおっしゃっているようです。

これは、古典的な2部マッチングの問題です。StevenSkienaによるアルゴリズム設計マニュアル（第2版）のegp498を参照してください。基本的なアプローチは、ボランティアのセットと、埋めようとしているタイムスロットのセットの両方を表す頂点を使用してグラフを作成することです。Edgesは、ボランティアを有効なタイムスロットにリンクします。その場合、最適なソリューションは、ボランティアやタイムスロットが繰り返されない、可能な限り最大のエッジのセットです。これはマッチングです。

ボランティアの中には、複数のスロットを実行できる人もいます。これは、そのボランティアの頂点を複数回複製することでモデル化できます。

ボランティアの優先順位付けを実装する場合、これにより各エッジに効果的に重みが追加され、そのタスクに対するそのボランティアの経験がモデル化されます。この場合、あなたが思ったように、ハンガリーのアルゴリズムのようなものが必要になります。これがなくても問題を解決できる場合は、問題を同等のフローグラフに変換し、ネットワークフローアルゴリズムを適用できます。これは、加重マッチングと非加重マッチングの両方を実装するコードの一例です。

他の代替案を含む詳細や実装へのリンクが必要な場合は、アルゴリズム設計マニュアルのコピーを入手することを強くお勧めします。これは驚くほど明確で実用的なリファレンスです。

于 2009-08-03T13:08:17.073 に答える