12

私は Python でスイス トーナメント システムに取り組んでおり、最適なペアリング アルゴリズムを見つけようとしています。
私の最大の問題は、私が持ってきたすべてのアルゴリズムがいくつかのシーケンスでエラーを生成したことです。そこでは、選択される最後のペアがすでに互いにプレイされており、ペアリングが無効であると判断されています.

私が取り組んでいるスイスのシステムは単純です: プレイヤーでさえ、誰もが各ラウンドでプレイし、ペアリングは勝利の近さに基づいて行われます (つまり、強いプレーヤーは強いプレーヤーと対戦し、弱いプレーヤーは弱いプレーヤーと対戦します)。
No Bye、勝ち負けのみ（引き分けなし）、対戦相手は2回対戦できません。

私が行った現在のアルゴリズムは次のように機能します。

  1. ランキング順 (勝数の多い順) でプレイヤー リストを作成します。
  2. 勝利数の多いプレイヤーから順に選ぶ
  3. 最も近いランクのプレーヤーと彼を一致させます。彼らがすでにプレーしている場合は、一致が見つかるまで、彼を次の人と一致させます
  4. リストからペアを取り出して 1 に戻す

例:
2 ラウンド後のランキング: 

1. P1: [P2 win, P3 win] 2 wins
2. P5: [P6 win, P2 win] 2 wins
3. P3: [P4 win, P1 lost] 1 win, 1 loss
4. P4: [P6 win, P3 lost] 1 win, 1 loss
5. P2: [P1 lost, P5 lost] 2 losses
6. P6: [P5 lost, P4 lost] 2 losses

最初のピックは P1 で、最初の試合は P5 です。リストから (P1,P5) を取り出します。

1. P3: [P4 win, P1 lost] 1 win, 1 loss
2. P4: [P6 win, P3 lost] 1 win, 1 loss
3. P2: [P1 lost, P5 lost] 2 losses
4. P6: [P5 lost, P4 lost] 2 losses

最初のピックは P3 で、すでに P4 でプレイされているため、試合は P2 になります。リストから (P3,P2) を取り出します。
このシーケンスでは、互いに対戦したペアで終了し、ペアリングは無効です。

1. P4: [P6 win, P3 lost] 1 win, 1 loss
2. P6: [P5 lost, P4 lost] 2 losses

質問: お互いにプレイした 2 人のプレイヤーで最後に「スタック」しないことを確認しながら、最適なペアリング モジュールを保証するアルゴリズムはありますか?

4

4 に答える 4

5

多分私はそれを手伝うことができます。チェスでは、さまざまなスイス ペアリング アルゴリズムがありますが、それらはすべて強弱ペアリングで機能します (驚くことがあります)。

オランダ語 (最も使用されている) の基本原則は、ペアリング番号を割り当てたら、各スコア ブラケットにアルゴリズムを適用することです。

アルゴリズムは、おおよそ次のように機能します。

最初のスコア ブラケットでは、(約) 半分のプレーヤーを選び、それらをサブグループに配置し、残りのプレーヤーを別のサブグループに配置します。プレーヤーに互換性がある場合は、それらをペアリングします。互換性がない場合は、2 番目のサブグループのプレーヤーを交換してみてください。ペアリングに互換性がない場合は、サブグループ間でプレーヤーを交換します。ブラケットに奇数のプレイヤーがいた場合、1 人がフロート ダウンします。

次のスコア ブラケット: フローターがある場合は、まずそれらをペアにします。次に、残りのグループで前と同じことを行います。

少なくとも 1 つのペアリングが可能であることを確認するために、さらにいくつかのルールが追加されます。

例: 十分なペアリングを行うことができる取引所がない場合は、前のスコア ブラケットに戻り、ペアリングを解除してフローターを作成します。

これはオランダのペアリングシステムの非常に大まかな説明ですが、それがあなたの質問に対する私の答えでした.

于 2015-12-15T19:11:33.723 に答える
2

しばらく前に同じ質問があり、Python で最小重量最大マッチング アルゴリズムを使用してソリューションを構築することになりました。このための素敵なライブラリさえあります！https://healthyalgorithms.com/2009/03/23/aco-in-python-minimum-weight-perfect-matchings-aka-matching-algorithms-and-reproductive-health-part-4/

私は自分の思考プロセスをブログ投稿に書き、それを構築する際に使用したリソースへのリンクを必ず付けました。これがお役に立てば幸いです: https://www.leaguevine.com/blog/18/swiss-tournament-scheduling-leaguevines-new-algorithm/

于 2016-06-24T22:00:02.610 に答える