Nグループの人々とMテーブルがあるとします。各グループのサイズと各テーブルの容量がわかっています。同じグループの2人が同じテーブルに座っていないように、どのように人々をテーブルに一致させるのですか？
貪欲なアプローチはこの問題に対して機能しますか？（貪欲なアプローチは次のように機能します。各テーブルについて、さまざまなグループの人々でテーブルを「埋める」ようにしてください）。
3 に答える
4
グループとテーブルのサイズが等しくない可能性があると仮定すると、説明されているような貪欲なアプローチは機能するとは思いません（少なくとも追加の仕様がない場合はそうではありません）。2つのT1のテーブルと3つのT2のテーブルがあり、3つのグループ{A1}、{B1、B2}、および{C1、C2}があるとします。私があなたのアルゴリズムに従うと、T1は{A1、B1}を受け取り、T2と{B2、C1、C2}が機能しなくなります。しかし、ソリューションT1 {B1、C1}、T2 {A1、B2、C2}があります。
次の貪欲なアプローチが機能していると思います。最大のグループから始めて、各グループを取り、テーブルごとにそのグループの1人を割り当て、最も空いている席のある最初のテーブルを選びます。
于 2012-01-07T17:43:59.877 に答える
2
マティアス：
次の貪欲なアプローチが機能していると思います。最大のグループから始めて、各グループを取り、テーブルごとにそのグループの1人を割り当て、最も空いている席のある最初のテーブルを選びます。
それはそう。そして、tkleczekの議論の小さなバリエーションがそれを証明しています。
解決策があるとしましょう。この場合、アルゴリズムが解決策を見つけることを証明する必要があります。
グループの数が0の場合、これは空虚な真です。
導入ステップでは、解決策がある場合、最大のグループの1人のメンバーが（最大のグループのサイズの）最大のテーブルのそれぞれに座っていることを示す必要があります。
条件L：テーブルのすべてのペア（T1、T2）について、T1 <T2であり、最大グループのメンバーがT1にある場合、最大グループの別のメンバーがT2にあります。
S1を解とします。S1がLを満たす場合、これで完了です。それ以外の場合は、T1 <T2のテーブルのペア（T1、T2）があり、最大グループのメンバーはT1に配置されますが、最大グループのメンバーはT2に配置されません。T2> T1であるため、T2にメンバーがいるグループがありますが、T1にはメンバーがいません（またはT2に空きがあります）。したがって、これら2つはシートを交換でき（または最大グループのメンバーはT2の空き場所に移動できます）、Lに違反するテーブルのペアが少ないソリューションS2を取得します。テーブルの数は限られているため、非常に多くのステップを実行した後Lを満たす解Skを見つけました。
帰納的仮説：N群のすべてのコンステレーションとテーブルのすべての数Mについて、解がある場合、アルゴリズムは解を見つけます。
ここで、解が存在する（N + 1）グループとMテーブルのコンステレーションについて考えます。上記により、最大のグループのメンバーがアルゴリズムに従って配置されるソリューションもあります。それらを配置します。これにより、問題がN群とM'テーブルの解ける星座になり、帰納法の仮説に従ってアルゴリズムによって解かれます。
于 2012-01-08T03:30:52.837 に答える
1
次の貪欲なアプローチが機能します。
座席がなくなるまで、次の手順を繰り返します。
- 最大のグループと最大のテーブルを選択してください
- 選択したグループの1人を選択したテーブルに一致させる
- グループサイズとテーブルサイズを1つ減らします。
証拠：
1つのステップを実行した後でも、最適なソリューションに到達できることを証明する必要があります。
最大のグループのメンバーをかっこいい男と呼びましょう。最大のテーブルにかっこいい男が座っていない、別の最適なソリューションがあるとします。このソリューションで最大のテーブルに座っている人を選び、それをラメガイと呼びましょう。彼はクールなグループ以下のサイズのグループに属している必要があります。だから、クールな男が座っているが、足の不自由な男がいない別のテーブルがあります。足の不自由な人とかっこいい人の席を安全に交換することもできます。これも最適な解決策になります。
于 2012-01-07T20:14:44.637 に答える