私は特定の数のチームを持っています。すべてのチームが、指定された 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
しかし、ここで問題が発生します。
このアルゴリズムが何と呼ばれるかはわかりませんが、これを実装するアルゴリズムを探しています。
ラウンドロビンやその他のマッチング アルゴリズムのようなトーナメントと結婚の問題を検索しましたが、私の問題は別のものだと思います。間違っている場合は修正してください。
どんな助けでも大歓迎です。
チームの数が奇数の場合、解決策はないと結論付けました。チームの数を N とします。N*4/2チームごとに合計 4 試合が必要ですが、各試合は 2 チームとしてカウントされます。N*24 つのタイム スロットでマッチを行うには、N/2スロットごとのマッチを平均化する必要があります。一度に多くのfloor(N/2)試合を行うことができます。N が奇数の場合、floor(N/2) < N/2.
存在する場合でも、N に対してのみ機能するソリューションは役に立ちますか?
単純なアルゴリズム：
Round 1
1 2 3 4
8 7 6 5
次に、場所を2〜8回転させます。
Round 2
1 8 2 3
7 6 5 4
Round 3
1 7 8 2
6 5 4 3
http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm
（奇数の場合は、ダミーのペアを追加してさようならを示すことでこれを拡張できますが、パトリシアシャナハンが指摘するように、すべてのチームがすべてのラウンドでプレーするわけではありません。したがって、偶数のチームと少なくとも6つのチームは要件を満たすために必要です。）