4

N = 4k各メンバーが 1 つのクランに所属できるように、プレイヤー、kテーブル、および多数のクランを検討してください。クランには最大で 1人のkプレイヤーを含めることができます。

ゲームの 3 ラウンドを編成して、ちょうど 4 人のプレイヤーが着席するテーブルごとに、そこに座っている 2 人のプレイヤーが同じクランのメンバーになることはなく、後のラウンドでは、そこに座っている 2 人のプレイヤーが同じ場所に座ることがないようにします。前のテーブル。すべてのプレイヤーがすべてのラウンドをプレイします。

これを効率的に行うにはどうすればNよい~80でしょうか。

私はこれについて考えました：

for each table T:
  repeat until 4 players have been seated at T:
    pick a random player X that is not currently seated anywhere
    if X has not sat at the same table as anyone currently at T AND
       X is not from the same clan as anyone currently at T
       seat X at T
       break

これが常に終了するのか、それとも有効な割り当てがあってもスタックする可能性があるのか​​ はわかりません。これが機能する場合でも、それを行うためのより良い方法はありますか?

4

2 に答える 2

3

クランごとにちょうど k 人のプレイヤー (つまり 4 クラン) が常にいる場合、テーブルには常にクランの 1 人がいるはずです。その場合、各プレイヤーが所属するクランに応じて一定数のテーブルをさらに移動する、事前定義されたローテーション スキームを考え出すことができると思います。

氏族の数が 4 を超える可能性がある場合、それは可能ではないと思います (または、いずれにせよわかりません)。

あなたのアルゴリズムはかなり良いと思います。ランダム化された動作を維持しながら、(有効な解決策がない場合) 決して終了しないようにする方法の 1 つは、無作為なプレイヤーを無限に選ぶのではなく、席を外したプレイヤーのリストを 1 回シャッフルし、このリストの各プレイヤーを次のように処理することです。順番：

編集：ラウンドを繰り返すのを忘れていました。これもアルゴリズムに含めました。

for each round R in {1, 2, 3}
  for each table T:
    UP = a randomly shuffled list of unseated players
    for each player X from UP
      if there are less than 4 people seated at T AND
         X has not previously sat with any of the players currently at T AND
         X is not from the same clan as anyone currently at T
           seat X at T

    //No more players left to try for this table
    if T has less than 4 people seated
      abort;  //No solution possible (at least, with the decisions taken so far)

  //All tables filled with players, prepare for the next round.
  for each table T:
    for each player X on T:
      Register on X that he has sat with each of the other 3 players at T
    Unseat all players at T

このように、アルゴリズムは 1 回のラウンドですべてのプレーヤーをテーブルごとに最大 1 回試行するため、1 回の実行でプレーヤーの着席を最大 3*T*N 回試みてから終了します (解決策の有無にかかわらず)。言い換えれば、1回の実行は非常に迅速に行われる必要があります。

まだランダム化されているため、この同じアルゴリズムを複数回実行してもまったく問題ありません。これは、毎回異なる座席の組み合わせが試行されるためです (いわゆるラスベガス アルゴリズムになります)。

編集 2 : それぞれ 16 人のプレイヤーからなる 5 つのクランでこのアルゴリズムを試してみました。通常、最初の解を見つけるまでに約 400 回の実行が必要ですが、合計実行時間はまだ約 1 秒です。

于 2012-10-26T11:01:44.010 に答える
1

行き詰まる

シートレベルでスタック

これが常に終了するのか、有効な割り当てがあってもスタックする可能性があるのか​​はわかりません。

スタックする可能性があります。k = 4テーブル、N = 16プレーヤー、4クラン、各クランに4人と仮定します。A1からA4をクランAのプレイヤーとし、他のクランも同様にします。次に、アルゴリズムから発生する可能性のある手作りの状況の例を次に示します。

Round 1:
 Table 1: A1, B1, C1, D1
 Table 2: A2, B2, C2, D2
 Table 3: A3, B3, C3, D3
 Table 4: A4, B4, C4, D4

Round 2:
 Table 1: A1, B2, C3, D4
 Table 2: A2, B3, C1 !!!

ラウンドレベルで立ち往生？

まだ残っている興味深い質問は次のとおりです。3ラウンドすべての有効な割り当てが可能である場合、3ラウンドのすべての有効な割り当てを妨げる2ラウンドの有効な割り当てを見つけることができますか？この場合、ラウンドレベルでスタックする可能性があるため、バックトラッキングアルゴリズムを実行するときに、有効なソリューションを取得するために、完全なラウンドを元に戻す必要がある場合があります。私にはこれが起こる例はなく、どちらにしても強い腸の感覚はありません。

より良い方法

それを行うためのより良い方法はありますか

十分な努力を払えば、これをいくつかの標準的なグラフアルゴリズムのフレームワークに詰め込むことができると思います。ほとんどの場合、そのグラフの問題はNP困難であるため、そのために使用できる多項式時間アルゴリズムもありません。

ドナルド・クヌースは、ダンスリンクと正確なカバー問題を解決するためのそれらの応用についての素晴らしい論文を書きました。最悪の場合でもバックトラッキングと指数時間を使用しますが、ほとんどの作業が行われる検索ツリーの部分のデータ構造を小さく保つため、検索が高速化されます。たぶん、これらのアイデアのいくつかはあなたの状況にも適用することができます。ただし、推測するだけでは、まだ特定の実装を念頭に置いていません。

別のアイデア：マッチングを計算するときに使用される、パスの拡張の概念を採用できる可能性があります。アイデアは次のようになります。着席していない人がいない場合は、他のプレイヤーから任意の人を選びます。その人が現在のテーブルと互換性がある場合は、そのテーブルに移動します。そうすることで、他のテーブルは1人のプレーヤーが短くなり、着席していないプレーヤーを使用してそのギャップを埋めることができます。それでも問題が解決しない場合は、既存のプレーヤーを再度装着します。おそらくすぐにプレイヤーを動かし始めるべきではありません。代わりに、最初に空いている席から始まり、着席していない人で終わる完全な拡張パスを見つけようとする必要があります。そのようなチェーンが存在することを確認した後でのみ、それに応じて人々を動かし始めることができます。

于 2012-10-26T10:57:48.943 に答える