問題は次のとおりです。サイズが A、B、C、D の 4 つの生徒グループと、合計 k 人の付き添い人がいる場合、生徒にほぼ等しい割合で付き添い人を割り当てるアルゴリズムを考案します。
シャペロンの数は正の整数でなければならないため、グループに k*A/N、k*B/N、k*C/N、k*D/N シャペロンを与えることはできません。適切な数のシャペロンを取得できない可能性があるため、丸めることはできません。したがって、私の考えでは、小数部分を捨て、整数部分を各グループに与え、整数除算も行います。その後、シャペロンがいくらか余るかもしれませんが、多くても 3 人なので、残りが最も多いグループに割り当てます。
すると、インタビュアーは、これには問題があると指摘しました。別のシャペロンを追加する場合、k を k+1 に増やすと、グループの 1 つが実際にこの方法でシャペロンを失う可能性があります。彼女は私に例を挙げましたが、覚えていません。
この問題を回避するアルゴリズムを思い付くことができる人はいますか?
解決しようとしている問題は、一般に配分問題または投票配分問題として知られています。これは、アメリカ下院の議席数を各州に割り当てるのと同じ問題です。
あなたのアプローチ (ハミルトンの方法または最大剰余の方法として知られている) が失敗するロバスト性の問題は、アラバマのパラドックスとして知られています。ウィキペディアの記事から、「アラバマのパラドックスは 1880 年に発見され、議席の総数を増やすとアラバマ州のシェアが 8 から 7 に減少することが判明しました。」
歴史的に、少なくとも 4 つの異なる方法が米国で使用されてきました: Jefferson の方法、Hamilton の方法、Webster の方法、および 1941 年から使用されている現在のHuntington-Hill の方法です。
これらの後者の方法の背後にある考え方は次のとおりです。を、総人口を座席/付き添いD = N/kの数で割ったものとします。次に、丸め
が正しい議席数になるまでd = D変更します。dk_i = round(G_i/d)
round(G_1/d) + round(G_2/d) + ... + round(G_m/d) = k
キャッチは、関数がどのように機能するかにありますround。Webster のアプローチは、通常の意味で丸められます。0.5 をわずかに超えると上昇し、厳密に 0.5 を下回ると下降します。これは、算術平均を使用するのとよく似ています。Huntington-Hill 法は、代わりに幾何平均を使用するという考えに基づいています。これらのメソッドの優れた要約が
ここにあります。これらの除数アルゴリズムはすべて、割り当て規則に違反しているという点で欠陥があることに注意してください。状態は、少なくとも
floor(G_m/D)代表を取得することが保証されていません。
これをもっと試してみたい場合は、歴史、方程式、楽しいアプレットを完備したCut The Knotに関する優れた記事があります。
サイズA、B、C、Dの4つのグループの学生と、合計k個のシャペロンがある場合、シャペロンをほぼ等しい比率で学生に割り当てるためのアルゴリズムを考案します。
質問を非常に簡単に解決するアルゴリズムは次のとおりです。
グループごとに0シャペロンの配分から始めます。グループに生徒がいない場合は、そのグループにシャペロンが割り当てられないため、そのグループを破棄します。
割り当てられたシャペロンの総数がkに等しい場合、これで完了です。
1つのグループに1つのシャペロンを割り当てます。シャペロンを受け取るグループは、生徒あたりのシャペロンの比率が最も低いグループです。同点の場合は、生徒あたりのシャペロンの比率が最も低いグループの中から、生徒が最も多いグループを選択します。それでも同点の場合は、選択したグループの中から、アルファベット順で最初のグループを選択します。
手順2に進みます。
それは明確な決定論的割り当てを行います。比率は、値が許す限りほぼ等しくなります。kを増やしても、グループへの割り当ては減りません。これは、事実上、追加の反復が発生するだけであり、反復によってグループの割り当てが減ることがないためです。
同じサイズの2つのグループが異なる数のシャペロンを持つことは可能ですが、kを変更できるように問題を修正せずに、これを修正することはできません。いかなる場合でも、同じサイズの2つのグループの割り当てが1を超えて異なることはありません。
状態に表現を割り当てるための他の回答のすべてのアルゴリズムは、不必要に複雑であり、実行される計算ステップの数を最小限に抑えるように設計されています（増分割り当てではなく数値計算を行うことによって）。私が与えたアルゴリズムは、コンピューターで実行すると非常に単純です。