2

裏話

これが問題です。私は3人家族で暮らしており、長男は家事を一人でやるのに飽き飽きしています。私たちはさまざまなタスクのスケジュールを作成しようとしましたが、私たちの1人が家にいなくて雑用が取り残されたか、誰かが他の人よりも多くの仕事をしていると感じて、恨みや雑用を完了したくないという問題が常にありました。

問題

人間は間違いますが、コンピュータプログラムは間違いありませんよね？アイデアは、コンピュータプログラムを使用して、実行する雑用を公平に分散し、誰も自分がもっと仕事をしているように感じられないようにすることができるということです。私はこれらの基準に準拠した雑用を分散するアルゴリズムを考え出そうとしています。

  • 長期的には約1/3の確率で家事を均等に分散する必要があります。
  • 最初のリストが利用できない場合、2番目のリストがそれを完了することができるように、順序付けられた人々のリストを返す必要があります。
  • 同じ日に1人あたり複数の雑用をスケジュールすることは避けてください。
  • 同じ人に同じ雑用を複数回連続してスケジュールすることは避けてください。
  • 偏差に耐える必要があります。予定された人が雑用をしなかった場合でも、実際に雑用をした人がフィードバックされれば、それは公正なままであるはずです。
  • それは異なる頻度で異なる雑用で動作するはずです（あなたは毎日皿洗いをする必要がありますが、週に一度だけバスルームを掃除する必要があります...）

私の質問は、このアルゴリズムを実装するための最良/最もクール/最も公正な方法は何でしょうか？ （ばかばかしいほど洗練されたソリューションは高く評価されています：D）

私は何を試しましたか？

このようなアルゴリズムを実装する簡単な方法は、さまざまな基準のコストテーブルを定義し、加重乱数を使用して人を選択することですが、これは長期的には公平ではないと思います（実際には制限する必要があります） 1人あたり1/3に向かって、またはそれは受け入れられません:)）。

4

3 に答える 3

1

あなたの問題は2つの部分から成ります：

1）スコア関数を定義します。公平で効率的な、...をどのように定義しますか？それらの間のトレードオフは何ですか？トレードオフを行うには、さまざまな手法があります。

  • スコアの重み付け、例：1回（不均一な分布）== 5回（1日に複数の雑用）
  • スコアレベル、たとえば:(不均一な分布）常に（1日に複数の雑用）を上回ります
  • パレートスコアリング：ウィキペディアを参照

2）最適化アルゴリズムを使用して、（可能なすべてのスケジュールから）最高のスコアを持つスケジュールを見つけます。問題がNP完全である場合、そのような完璧なアルゴリズムはありません。しかし、それでも非常に良いものがあります。私はFirstFitDecreasingから始めて、次にTabuSearchを続けることを好みます。

コードを実装した同様の例の完全で詳細な概要については、このチュートリアルに従ってください。Computer精神的に単語をPersonとでProcess置き換えますChore。

于 2012-07-13T08:40:15.493 に答える
1

一般に、制約は十分に緩く、アルゴリズムをあまりスケールアップする必要はないようです。したがって、スケジュールがすべての基準を満たすように強制するアルゴリズムを作成できるはずです。それを実装するためのさまざまな方法がたくさんあります。ここにあなたが始めるのを助けるかもしれないいくつかのランダムな考えがあります。

特定の日に割り当てる家事のリストがあるとします（ただし、これはどの期間でも機能するはずです）。それぞれの雑用には重みがあります（それがどれほど難しいと思うか、どれくらいの時間がかかるかなど）。各雑用には名前があるか、あるクラスのインスタンスです（2つのバスルームの掃除が同じ雑用であり、同じ人に2回割り当てる可能性が低いことがわかるように）。また、過去に人々が行ったすべての雑用のリストもあります（割り当てられた人だけでなく、実際に行った人も含まれます）。

家事を1/3の確率で分配したい場合、これを行う簡単な方法は次のようになります。

while has_more_chores()
  randomize the order of the persons list
  foreach person:
    if (has_more_chores()):
      person.assign_chore()

これは基本的に、各人が他の人と同じくらい多くの雑用をしたことを保証します。ただし、それは重みを考慮に入れていません。体重が重要な場合は、おそらくもっと理にかなっています

foreach chore:
  chore.choose_person()

person.assign_chore（）またはchore.choose_person（）のどちらを実行している場合でも、1人の人がいつもバスルームを掃除してしまうことがないように、何らかのバランス関数を適用する必要があります。修正された指数バックオフを使用して、大量の処理を行った後に雑用を取得する可能性を減らすことができます。

おそらく、問題に取り組むためのより簡単な方法は、無数の異なる人の雑用スケジュールをランダムに生成し、制約を満たさないものを失格にすることです（つまり、1人が連続して複数回同じ雑用を行うか、1人が複数の雑用を行う1日）。

于 2012-07-11T17:07:52.390 に答える
1

効率的な市場が出現し、最適なソリューションを提供することを期待して、実際のお金ではなく、クレジットまたは高級消耗品の価格と賃金で、ある種の「面白いお金」経済を試すことができます。

本当に複雑なものが必要な場合は、Vickrey-Clarke-GrovesオークションのClarkePivotルールを検討してください。ここで、家事をするかしないか、または家事のバッチは、入札される可能性のある結果です。オークションを主催する銀行はわずかな利益しか上げていないことに気付くはずです。十分な量が蓄積されると、それはフェスティバルとしてすべてに再分配される可能性があります。

于 2012-07-12T18:59:50.847 に答える