問題タブ [sports-league-scheduling-problem]

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

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

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

考え？

一連のチームのスケジュールを生成するアルゴリズムを探しています。たとえば、各チームがお互いに対戦するスポーツ シーズンを想像してみてください。1 回はホーム チームとして、もう 1 回は別のチームのフィールドでビジター チームとしてプレーします。

シーズン中のすべての試合のセットを生成するのは簡単です。teams がチームのリストである場合、次のようになります。

しかし、有効なゲームスケジュールの制約を満たし、「自然にランダム」に見えるように、ゲームを時系列で並べ替えたいと考えています。

制約は、各チームが別のチームとペアになる n / 2 ゲーム (n はチームの数) で構成される複数のラウンドにゲーム リストをグループ化できる必要があることです。

スケジュールをより自然に見せるために、2 つのチームが連続して 2 回対戦しないようにします。つまり、(a, b) が 1 つのラウンドでプレイされる場合、ゲーム (b, a) は次のラウンドでプレイされるべきではありません。

また、可能な限り、すべてのチームが 1 ラウンドおきにアウェイ チームとしてプレーし、残りのラウンドはホーム チームとしてプレーする必要があります。この制約を常に満たすことができるとは思わないので、あると便利です。たとえば、1 つのチームがホームで 8 試合、アウェイで 8 試合を行うべきではありません。

以下は、私が今得たものです。このアルゴリズムの主な問題は、while ループで頻繁にスタックすることです。特にチーム数が16以上の場合。また、ランダム サンプル関数を使用し、それを正しく取得することを望んでいるため、非常に非効率的です。

n 個のクラス (生徒名のリスト) から w 週間のペアを計算するアルゴリズムを探しています。これにより、生徒が 2 つの異なる週に同じ生徒と協力することはありません。n が偶数であると仮定します。

例：

クラス: 学生 1,2,3,4

週: 3

• 1週目のスケジュール: (1,2), (3,4)
• 第 2 週のスケジュール: (1,3)、(2,4)
• 3 週目のスケジュール: (2,3)、(1,4)

w は n - 1 以下である必要があると考えました。なぜなら、すべての生徒は n - 1 人の他の生徒と最大限に協力できるからです。しかし、常に n - 1 の解があるかどうかはわかりません。もしあれば、これらの n - 1 の解を力ずくで生成するアルゴリズムを見たいと思います。

この問題の名前と、注目すべき一般的なアルゴリズムはありますか?

スポーツ リーグのスケジューラを作成しようとしています。チームをグループでスケジュールして、すべてのチームがグループごとに 1 つのゲームを取得できるようにしたいと考えています。私がやろうとしていることは、コンピューター サイエンスの既存の問題だと思いますが、それが何と呼ばれているのかわかりません。それに関する情報を見つけるのに苦労しています。いずれにせよ、状況は次のとおりです。

A = {1,2,3,...,n}team のセットとそれらの team のペアのセットがあるとしましょうB = {(1,2), (1,3), (2,4), (6,9),...}。B には、A からのチームのすべての可能な組み合わせがあるわけではありません。A には偶数のチームがあると仮定します。私のプログラムは、A のすべてのチームが S に 1 回だけ出現するように、B のサブセット (そのサブセットを S と呼びましょう) を作成しようとしています。これは、ペアを B から S に 1 つずつ移動することによって行われます。すでにいくつかのペアが S に配置されているとしましょう。現在の状況で S を正常に作成できるかどうかを確認するにはどうすればよいですか?

例：

更新: このアルゴリズムは、スケジュール ジェネレーターで使用するヒューリスティックの 1 つです。目標は、各チームがウェーブごとに 1 つのゲームを持つ「ウェーブ」にスケジュールを暗黙的に分割することです。たとえば、16 チームのプールがあり、各チームがプール内の他のチームと 5 試合を行うとします。理想的なスケジュールでは、すべてのチームが少なくとも 1 つのゲームを行う前に、どのチームも 2 番目のゲームを行わないようにします。スケジューラーはゲームを 1 つずつ選択し、日付を割り当てます。したがって、この「ウェーブ」でスケジュールされたゲームをスケジューラーに追跡させ、現在のウェーブで各チームが 1 回だけプレイするのを妨げるようなゲームを決して選択しないようにするという考え方です。スケジューラーは他の多くのヒューリスティックも使用するため、ゲームを明示的に順序付けして順番に実行することはできません。

これが不明確であるか、あまり厳密でない場合は申し訳ありません。ご不明な点がございましたら、お気軽にお問い合わせください。さらに説明できるよう最善を尽くします。

ラウンド ロビン トーナメント アルゴリズムは、チームがゲームごとに対戦する場合にのみ機能します。しかし、同じゲームで 2 つ以上のチームが対戦するスポーツやゲームのトーナメントにどのように実装するのでしょうか。たとえば、2 対 n のチームが 2 対 n のゲームで対戦するペイントボール トーナメント。すべてのチームが可能な限り 1 回だけホーム チームになる必要があるという制約を引き続き維持します (チームを均等に分割できない場合は、ホーム チームにならないチームをできるだけ少なくしてもかまいません)。

何か案は？与えられたのは、チーム数、ゲーム数です。おそらく、ゲームごとのチーム数は与えられているかもしれません。

クラスメートと私は大会の準備をしています。60 人を 6 人ずつのチームに分けるのが私の担当です。チームメンバーは毎週ローテーションされます。次の切り替え時に同じチームのメンバーが別のチームに移動しないようにチームを組んでいきたいと思います。スタックオーバーフローをグーグルで調べてチェックすると、これに似た特定の質問が見つかりました(URLをマークするのを忘れました:( )。提供された回答に基づいて、次の結論に達しました:一人一人が他の59人と一緒に座らなければなりません。すべてのシフトでその 人 は 他 の 5 人 と 一緒 に 座ら なければ なり ませ ん . だから , 私 の 制約 を 満たす 人 を 座らせる 59/5 通り の 方法 が あり ます . 59/5 は 整数 で ない から 不可能 です .

1. これを仮定するのは正しいですか？
2. また、バックトラッキングなどの手法を用いて解決することは可能でしょうか? もしそうなら、誰でもそのような解決策を達成する方法を教えてもらえますか?

前もって感謝します ！！！！

私は特定の数のチームを持っています。すべてのチームが、指定された 4 つの時間に 4 人の異なる対戦相手と正確に 4 試合を行うことを望んでいます。

複雑なのは、どのチームも同時に 2 つの異なる試合を行うことができないということです。たとえば、チーム 1 がチーム 1 対チーム 2、チーム 1 対チーム 3、チーム 1 対チーム 4、チーム 1

対 チーム 5 のようにプレーしている場合、チーム 2 は

すでに最初のタイムスロットを占有しているため、チーム 2 はこのようにプレーできます

(チーム 2 対チーム 1)、チーム 2 対チーム 3、チーム 2 vs チーム 4、チーム 2 vs チーム 5

しかし、ここで問題が発生します。

このアルゴリズムが何と呼ばれるかはわかりませんが、これを実装するアルゴリズムを探しています。

ラウンドロビンやその他のマッチング アルゴリズムのようなトーナメントと結婚の問題を検索しましたが、私の問題は別のものだと思います。間違っている場合は修正してください。

どんな助けでも大歓迎です。

可能なすべてのペアリングを生成する必要がありますが、特定のペアリングが結果で1回だけ発生するという制約があります。したがって、たとえば：

可能なすべての2対の順列を生成します。出力の小さなサブセットを次に示します。

さらにフィルタリングして、（8,4）を1回だけ（フィルタリングされたすべての順列全体で）、（8,5）を1回だけ、（0,1）を1回だけ、（4,7）を表示するようにするにはどうすればよいですか？ ）一度だけなど？

基本的に、各2要素のペアリングが1回だけ発生するような順列が必要です。

これを解決する追加のitertoolがあると思いますが、私はそれが何であるかを知るのに十分な専門家ではありません。

更新：GarethReesは正しいです-ラウンドロビン問題を解決しようとしていることに完全に気づいていませんでした。私がしているのはペアプログラミング演習のために人々をグループ化することであるという追加の制約があります。したがって、人数が奇数の場合は、3人のグループを作成して、各エクササイズに奇数人を含める必要があります。私の現在の考えは、（1）見えない人を加えることで偶数人にすることです。次に、ペアリング後、見えない人とペアになっている人を見つけ、それらを既存のグループにランダムに配置して、3人のチームを形成します。ただし、これをより適切に行うラウンドロビンのアルゴリズムや調整はまだないのではないかと思います。

更新2：Theodrosのソリューションは、上記で説明した上品な煩わしさなしに、正確に正しい結果を生成します。誰もが驚くほど役に立ちました。

自動サッカーリーグジェネレーターを作成していて、スケジュールどおりに行き詰まりました。すべてを生成するためのアルゴリズムがありますが、スケジュールはありません。見てください：

例えば：

foreach()そして今、私がそのすべてのデータを取得したとき、私は必要なものを取るためにほんの少ししか使うことができません。しかし、私が望んでいるのは、チームを通常はRED＆BLUEチームに入れることです。

つまり：

• 片側の1つのチーム（青または赤）は最大2回プレイできます。
• 1ラウンドの1チームは、1ラウンドで$totalTours/2ゲームをプレイする必要があります。

たとえば、9つのチームがある場合、第1ラウンドでは、チームはREDで4つのツアー（連続ではなく合計）をプレイし、BLUEで5つのツアーをプレイする必要があります。第2ラウンドでは、REDで5ツアー、BLUEで4ツアーをプレイする必要があります。

チームが100ある場合でも、アルゴリズムは機能する必要があります。