ある最適化問題 スポーツスケジューリング スポーツスケジューリングとは？ 生成方法 プログラムと問題点 2001年2月7日（水）

Presentation on theme: "ある最適化問題 スポーツスケジューリング スポーツスケジューリングとは？ 生成方法 プログラムと問題点 2001年2月7日（水）"— Presentation transcript:

1 ある最適化問題 スポーツスケジューリング スポーツスケジューリングとは？ 生成方法 プログラムと問題点 2001年2月7日（水）
12月8日発表分資料 2001年2月7日（水） 加倉田　稔　　　　木本　公康

2 スポーツスケジューリングとは？

3 概要と我々の構想 ゲームの面白さ 視聴率の向上 経費の削減 対戦の組み合わせ 試合会場 チーム間の公平性 2重総当たり戦は考えない
ＴＶ放映のスケジュール 視聴率の向上 チームの移動 経費の削減 この条件をもとにスケジュールを作る事は困難である。

4 生成方法 slotとB Patternのランク 探索の構造 整数計画法 予備知識

5 予備知識 同一チームが1日に2試合以上行わないとする 各試合日で全てのチームが試合を行う slot 各チームのスケジュールは配列で表現する
試合の日程 例：slot0=1日目 slot1=2日目 各チームのスケジュールは配列で表現する Pattern : 長さがslotで、H・A（・B）からなる配列。 H A B H ホームゲーム A アウェイゲーム B 休日(チーム数が奇数の場合のみ使用)

6 slotとB(1日休日) チーム数(n)が偶数 slotの数と１つのチームが行う試合数が等しい １ ２ ３ n n-1
Ｂ slot=n 奇数 偶数

7 探索の構造 STEP1 : 全ての組み合わせのPatternを生成し、 使用可能なものを選ぶ。
探索手順 STEP1 : 全ての組み合わせのPatternを生成し、 　　　　　　 使用可能なものを選ぶ。 STEP2 : Patternの集合の中からチーム数と 　　　　　　等しい数だけ選ぶ。 その集合を Pattern Set と呼ぶ。 STEP3 : Pattern Setに試合を割り当てる。 　　　　　　 これを Time Table と呼ぶ。

8 H H H H H H H H H H H A H A A A A A A A A A A A P STEP1 Pattern
STEP2 Pattern Set H H H ・・・ H H H ・・ ・・ H H H ・・・ H H A ・・・ pCn個 H A A ・・・ A A A A A A ・・・ A A A slot (slot-1) 偶：2　　奇：2　 ×slot ・・・ 5チームなら5個のpatternしかないと思う人がいるかもしれないが、それは×。 まず、全てのpatternの組み合わせを生成し、使用可能なものをPの集合とする。 それからチーム数分抜き取る（pattern set）。このときに初めてpatternに仮チーム名が書き加えられる。 P STEP3 Time Table p個 ・・ ・・・

9 STEP1 Pattern生成の条件 Patternの長さがslot。 チーム間の公平性より、H・Aの数を下記に示す。 Hの数 Aの数
Bの数 n:偶数 slot=n-1 slot/2 n:奇数 slot=n 1 Patternの中に、３連続H・Aがない。 上記の条件に合っていても「あまり好ましくない」状態がある。 それらに値を与え、ランクをつける。

10 「あまり好ましくない」状態を値にする 試合日程 状態 悪さ 全ての日程内の4連戦 HBHH,HHBH 1 最初、最後以外の3連戦
AAB,ABA,BAA 2 最初の2試合 AA 3 　　　　 2試合 AB,BA 4 　　　　3試合 AAB,ABA,BAA 5 最後の2試合 AA 6 　　　　 2試合 AB,BA 7 　　　　3試合 AAB,ABA,BAA 8

11 STEP2 Pattern Setの生成 P ・・・ H A B 使用可能なPatternの集合（P）からチーム数分選ぶ。
・あるPattern set内に同じPatternが存在しない。 各slotのH・Aの数が等しい。 チーム数が奇数の場合、各slotにBが1つある。 P slot4 slot3 slot2 slot1 slot0 1 2 3 4 5 H A B ・・・

12 整数計画法とは？ 制約文 目的関数 3x ＋ 2y ≦ 7 5x ＋ 6y ≦ 13 x ≧ 0 y ≧ 0 x ＋ y
線形計画問題に「変数は整数値しかとらない」という制約（整数制約）を加えたもの x+y=k (2 , 0.5)

13 整数計画法によるPattern Set生成
P：Patternの集合　　T：slotの集合 X i :Pattern i をPattern Setに加えるとき1、それ以外0 h i k :Pattern i がslot kでHのとき1、それ以外0 a i k :Pattern i がslot kでAのとき1、それ以外0 b i :Pattern iの悪さ値 目的関数＜Patternの悪さの合計＞ 　　　　　　　Min : Σ{i Є P} b i X i 制約文 ＜slot k のH・Aの数＞ 　　　　　　　Σ{i Є P} h i k X i = n/2 for all k∈T 　 Σ{i Є P} a i k Xi = n/ for all k∈T 　　　　 ＜Patternの数＞ Σ{i Є P} X i = n for all i ∈ P

14 STEP3 Time Tableの生成 5 4 3 2 1 H A B 3 2 4 5 B 1 H・Aの組み合わせで1試合を割り当てる。
Pattern Set に全てのチームが他のチームと1回試合を行うように試合を割り当てる。 各slotで全てのチームが試合を行う。（Bは除く） slot4 slot3 slot2 slot1 slot0 5 4 3 2 1 H A B 3 2 4 5 B 1 A H

15 整数計画法によるTime Tableの生成
X i j k :slot k でPattern i がPattern j と試合をする とき１、それ以外0 S :Pattern Set内のPatternの集合 F :(i, j, k)の集合　 T :slotの集合 目的関数　 ＜Time Tableの試合数＞ 　　　　　　　　　Max : Σ{(i,j,k)ЄF} X i j k 　 制約文 　 ＜Time Table 内でi と jの試合が一回のみ＞ 　　　　　　　　　Σ{k : (i,j,k)ЄF} X i j k = 1 for all i,j∈S , i≠j 　　　　　　　＜slot k で全てのチームが1回試合を行う＞ 　　Σ{j : (i,j,k)ЄF} X i j k ≦ 1 for all i∈S , k∈T

16 プログラムと問題点 実験結果 計算量 問題点 課題と可能性

17 プログラム 整数計画法のプログラム 世の中には整数計画法のエンジンなどが存在するが、
今回はPattern Set , Time Tableにそれぞれ対応した プログラムを作成した。 プログラムの計算量 n:チーム数 n 2 Ο（n　×２　）

18 実験結果 Pattern Pattern Set Time Table 5 24 76 48 6 10 1 8 7 86
スペック：CPU733MHz メモリー128MHz Pattern Pattern Set Time Table 5 24 76 48 6 10 1 8 7 86 83812(36分) 536836(77秒) 138 82688(14秒) 9 270 X 61 283440(14時間)

19 問題点 スポーツの種類・放送・チームの現状などにより制約が変化する。 チーム数が多くなると計算が膨大になる。
最良のスケジュールがいくつもでる可能性がある。 現状のスポーツスケジュール問題の最終決定は人の手作業になってしまうのか？

20 今後の我々の課題と可能性 課題 ・ PatternによってはPattern Set・Time Table が大量にできる。又は1個もできない場合の可能性がある。 可能性 ・ プログラムの効率化 ・ ある種のスポーツに特化したプログラムの作成

21 STAFF ower .Kimoto .Kakurata esume rogram M ● K P P ● K M R ● K M
oint .Kimoto .Kakurata esume rogram .C Special Thanks ● TEAM Knot M　 　●　K P P 　●　K M R 　●　K M P 　●　M K Presented by TEAM SPORTS