3

スポーツ リーグのスケジューラを作成しようとしています。チームをグループでスケジュールして、すべてのチームがグループごとに 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 を正常に作成できるかどうかを確認するにはどうすればよいですか?

例：

A = {1,2,3,4}, B = {(1,2), (1,3), (1,4), (3,4)}

If after one move, S = {(1,2)}, then it can be completed by moving (3,4).
If after one move, S = {(1,3)}, then it cannot be completed.

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

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

4

2 に答える 2

4

グラフ理論の最大マッチング問題です。それを解決するための既知のアルゴリズムがいくつかあります。

問題のグラフ G (V - 頂点のセット、E - エッジのセット) で、V = A、E = B です。グラフに反対側のエッジも追加します。各エッジの重みは 1 です。

二部グラフにはハンガリーのアルゴリズムを使用し、その他の グラフにはエドモンドのアルゴリズムを使用することをお勧めします。

于 2011-10-24T19:03:09.740 に答える
0

以下に示す内容を明確にするために、いくつかの仮定を行うことが重要です。
まず、卓球リーグの 16 チームについて話しているとします。すべてのチームが対戦相手を複製せずに 5 試合を行うスケジュールが必要であるとします。
2 番目に、16 チームすべてが各セットでプレーを完了してから、いずれかのチームが再びプレーするようにします。
3 番目に、すべてのチームが 8 つのテーブルでプレーするように分散し、1 つのチームが常に同じテーブルでプレーするようにスケジュールされないようにする必要があります。

仮定が正しければ、必要なのは、バランスのとれた 16 チームのラウンド ロビン スケジュールからのゲームの最初の 5 "セット" (各セットをウェーブと呼びます) です。これにより、各チームが 5 つの異なるチームに対して 5 つのゲームをプレイするトーナメント タイプのチーム マッチアップが得られます。各セット (またはウェーブ) には 8 つのゲームがあり、常に同じテーブルでプレーするようにスケジュールされているチームはなく、すべてのチームが現在のセットのプレーを終了するまで、チームは次のセットでゲームをプレーしません。

以下は、私が作成したバランスのとれた 16 チームのスケジュールの最初の 5 つの「セット」です。見てみな。

16 TEAM SCHEDULE       DATE 8/3/14            

DATE   DAY  TIME    LOCATION    GM#  HOME VS VISITOR

___ __ ___ _______  Table #1     1   #1  v  #16
___ __ ___ _______  Table #2     1   #2  v  #15
___ __ ___ _______  Table #3     1   #3  v  #14
___ __ ___ _______  Table #4     1   #4  v  #13
___ __ ___ _______  Table #5     1   #5  v  #12
___ __ ___ _______  Table #6     1   #6  v  #11
___ __ ___ _______  Table #7     1   #7  v  #10
___ __ ___ _______  Table #8     1   #8  v  #9

___ __ ___ _______  Table #1     2   #13 v  #2
___ __ ___ _______  Table #2     2   #15 v  #1
___ __ ___ _______  Table #3     2   #16 v  #14
___ __ ___ _______  Table #4     2   #12 v  #3
___ __ ___ _______  Table #5     2   #11 v  #4
___ __ ___ _______  Table #6     2   #10 v  #5
___ __ ___ _______  Table #7     2   #9  v  #6
___ __ ___ _______  Table #8     2   #7  v  #8

___ __ ___ _______  Table #1     3   #6  v  #7
___ __ ___ _______  Table #2     3   #16 v  #12
___ __ ___ _______  Table #3     3   #15 v  #13
___ __ ___ _______  Table #4     3   #14 v  #1
___ __ ___ _______  Table #5     3   #2  v  #11
___ __ ___ _______  Table #6     3   #4  v  #9
___ __ ___ _______  Table #7     3   #5  v  #8
___ __ ___ _______  Table #8     3   #3  v  #10

___ __ ___ _______  Table #1     4   #8  v  #3
___ __ ___ _______  Table #2     4   #14 v  #12
___ __ ___ _______  Table #3     4   #1  v  #13
___ __ ___ _______  Table #4     4   #9  v  #2
___ __ ___ _______  Table #5     4   #10 v  #16
___ __ ___ _______  Table #6     4   #11 v  #15
___ __ ___ _______  Table #7     4   #4  v  #7
___ __ ___ _______  Table #8     4   #5  v  #6

___ __ ___ _______  Table #1     5   #3  v  #6
___ __ ___ _______  Table #2     5   #13 v  #11
___ __ ___ _______  Table #3     5   #15 v  #9
___ __ ___ _______  Table #4     5   #2  v  #7
___ __ ___ _______  Table #5     5   #10 v  #14
___ __ ___ _______  Table #6     5   #16 v  #8
___ __ ___ _______  Table #7     5   #12 v  #1
___ __ ___ _______  Table #8     5   #4  v  #5

-
于 2014-08-03T05:22:17.290 に答える