9

まず、このトピックが複雑であり、おそらく簡単な答えがないことを理解していると言うことから始めましょう。それが簡単なら、誰もがやっているでしょう。そうは言っても…

スポーツ リーグを管理するためのアプリケーションを作成するよう依頼されました。概念のほとんどは、次の 1 つを除いて、かなり簡単に理解できます: 重複のない (チームが一度に 2 つのチームと対戦する) 試合のスケジュールを生成する方法。他のディビジョンを1回、スケジュールに空きがないことを確認する（各チームは毎週プレーする）

現在、このプロセスは、この目的のために作成したロゼッタ ストーン タイプのスプレッドシートを使用して手動で行われていますが、設計された数のチームに対してのみ機能します。30チーム、24チーム、28チームのバリエーションを作っています。変換テーブルを継続的に再調整しようとするのではなく、そのロジックを体系化し、代わりにそのプロセスを微調整できるようにしたいと考えています。

考え？

4

4 に答える 4

14

ラウンドロビンと呼ばれるチェス トーナメントなどで使用される非常に単純なシステムがあります。

アイデアは、プレーヤーをテーブルの両側に分割することです。プレイヤーの 1 人が「ハブ」として指定されます (より適切な言葉が必要です)。トーナメントは、プレイヤー同士が向かい合って対戦することから始まります。最初のラウンドの後、ハブ以外の全員が椅子を 1 つ前に移動し、白/黒 (スポーツではホーム/アウェイ) の順序が入れ替わります。プレイヤーが元の場所に着席すると、総当り競技全体が終了します。全員に 2 回プレイしてもらいたい場合は、同じことをもう一度行います。

実装の詳細を含むウィキペディアの記事。

あなたの特別なケースでは、すべてのチームを含めてラウンドロビンを1回実行してみます. 次に、ディビジョンごとに同じことを 1 回行い、ディビジョン内のチームがホームで 1 回、アウェイで 1 回対戦することを確認するために、チームがそのラウンドでどのようにプレーしたかを最初のラウンドロビンから確認します。

もちろん、これの欠点は、トーナメントが終了するかなり前にすべてのディビジョン間の試合を行うことです (最後の n-1 試合はディビジョン内のチームと対戦するため [n = ディビジョン内のチームの数])。これが問題になる場合は、マッチを少し交換するだけです。

私は実際に、これを行う簡単な Python スクリプトを作成しました。多くのコード行を必要とせず、かなり良い結果が得られました。これにより、各チームが同じディビジョンの各チームと 2 回対戦し、他のディビジョンのチームと 1 回対戦するスケジュールが作成されます。ただし、同じチームがホームにいるような方法で、チームが互いに 2 回会うことを確認するためのチェックはありません。しかし、このコードは、独自のスケジューリング コードを作成する方法についての良いアイデアを提供するはずです。

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = int(len(list) / 2)
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()
于 2009-06-24T08:47:47.350 に答える
9

ラウンドロビンを確実に行うために、奇数チーム用と偶数チーム用の 2 つのアルゴリズムがあります。

可能であれば、グラフィックを生成します。

奇数チーム数

アルゴリズムは、すべてのチームを時計回りに回転させることです。チームが 5 つある場合:

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3

この時点で、全員が 1 回ずつ対戦する 1 つのラウンド ロビンを完了しました...次のラウンドは再び..

1 2
3 4
5

偶数チーム数

チームの数が偶数の場合、同じローテーションを行いますが、チーム #1 を固定位置に保持し、他のすべてのチームを #1 の周りで時計回りに回転させます。だから、4チームだったら…

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3

これは 1 つの完全なラウンド ロビンになります...次の対戦は..

1 2 
3 4

プログラム的に、これにアプローチできる方法はいくつかあります。たぶん、上に投稿されたコードは同じことをします笑..

于 2009-06-24T16:37:29.227 に答える
3

これらの制約をブール式としてエンコードし、いくつかの SAT ソルバーを使用してソリューションを取得します (たとえば、C++ の場合は MiniSAT、Java の場合は SAT4J で、独自の単純なソルバーを作成することもできます)。これらのソルバーへの入力は、DIMACS によって標準化されています。

同様の問題の SAT エンコーディングについては、「ソーシャル ゴルファー問題の SAT エンコーディング」および「トーナメント スケジュール用の SAT ベースのスケジューラ」も参照してください。

于 2009-06-24T09:02:14.823 に答える
2

これが実装のショットです

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in gameDays)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

紙の上でテストしただけですが、私のセットアップでは機能します。チーム リストの最初と最後を交互に開始することで、ペーパー テストで同じチームが同じチームと何度も対戦する (または同じ日に繰り返し対戦する) 状況を回避できます。可能性のあるすべての遭遇を別の対戦相手として表しましたが、それは基本的に CanPlay メソッドが行うべきことです。完全な解決策ではありませんが、これが役立つことを願っています

于 2009-06-24T10:52:42.560 に答える