スポーツスケジューリング
東京大学大学院 情報理工学系研究科 松井 知己
東京大学 今堀慎治
筑波大学 鈴鹿順美
東京大学 藤原伸友
東京農工大学 宮代隆平
筑波大学 吉瀬章子
スポーツスケジューリング
中央大学 理工学部 松井 知己
東京大学 今堀慎治
筑波大学 鈴鹿順美
東京大学 藤原伸友
東京農工大学 宮代隆平
筑波大学 吉瀬章子
発表の概要






はじめに
スケジュール
スケジュール+試合場所
スケジュール→HAT
HAT→スケジュール
応用と実用
3
スポーツ・スケジューリング
 スポーツ・スケジューリング (対戦日程計画)
• Timetabling の一分野

スポーツ競技などの最適な対戦日程を決める

スケジュール作成アルゴリズムの構築
• 初期の研究: 1970 年代後半
ここ数年で研究が活発化
Timetabling の中でも大きな分野に
4
Bibliography on Practice and Theory of Automated
Timetabling
 http://liinwww.ira.uka.de/bibliography/Misc/timetabling.html
~1995まで論文数の推移
5
はじめに
はじめに
読売新聞
2004/11/9はじまりは,6年前 .....
スケジューリングの実務における現状 (アメリカ)
MLB: 26週間の間に30球団による2430試合を開催
公募採用の外部業者が受託
1982--2004は,マサチューセッツ在住の夫婦に依頼.
2005年はカーネギーメロン大学のグループが作成.
~~~(2004年にスケジュール作成会社を起業)
NFL: 17週間の間に32チームが16試合ずつ,
年間256試合以上を開催.
TV中継の視聴率は40%超で,
1億3000万人以上が観戦していると言われている.
2003年より最適化技術(ILOG社)を用いて開発された
システムで作成.
7
スケジューリングの実務における現状 (日本)
プロ野球 セリーグ: 6球団,年間420試合
球団の営業担当者と連盟職員で構成される「日程編成会議」
で作成.リーグ理事会の承認を経て前年秋ごろに発表.詳
細は非公開 (計算機は用いているらしい).
サッカー J1リーグ:10チーム(1993年)から18チーム(2005年)の
総当り戦.スケジュール作成の詳細は完全非公開.
アイスホッケー アジアリーグ:9チーム各4回戦総当たりとグ
ループゲームを含め、全171試合1チーム38試合。 (中国(3),
日本(4),韓国(2))
海外遠征が頻繁にあり移動コスト削減が課題.航空機運行日
程がきつい制約.自由度はかなり低い.特異な制約が多い.
アメリカンフットボール 社会人リーグ:18チーム(6チーム×3
ディビジョン)による総当たり戦.年間45試合
子問題に分割可能,比較的簡単.事務局長が作成.
8
スポーツ・スケジューリングの実例
 スケジューリングの目的
• 移動距離最小化,観客数最大化,
公平性最大化,… → 収益最大化
 スケジュールへの要求
• 試合開催場所,固定された試合,
TV中継,各チームの強さ,予備日,…
現実問題から発生した研究分野
9
現在の手法
 スケジューリング問題の理論的研究
• 抽象化された問題,先行研究ともに少ない
• グラフ理論,デザイン理論,実験計画法,…
 スケジューリングに用いている数理手法
• 数理計画法

整数計画,分枝限定法,組合せ多面体論,…
• メタ・ヒューリスティクス

SA, GA, ローカルサーチ,タブーサーチ,…
• 制約論理法
10
Section 1 スケジュール
スケジュール
①
巨人:中
阪神:ヤ
広島:横
中日:巨
横浜:広
ヤクルト:阪
(チーム)
②
阪
巨
中
広
ヤ
横
③
横
中
ヤ
阪
巨
広
④
広
横
巨
ヤ
阪
中
⑤ (スロット)
ヤ
広
阪
横
中 リーグ戦のスケジュール
巨
・ チーム数:2n
・ スロット(試合日):2n-1
チーム数が奇数の時はダミーのチームを加える
12
総当りリーグ戦とグラフ




各チームを頂点とする完全グラフ.
各枝は試合に対応する.
各試合日には,全てのチームが1試合を戦う.
各試合日の試合は,グラフ上の完全マッチング.
F
F
A
E
A
E
B
D
B
D
C
C
13
スケジュールの存在性 [Kirkman 1847 or earlier]
 以下のような円盤を回して,試合を決める.
A
A
A
A
A
E
E
E
B
B
B
E
B
B
F
E
F
F
F
F
D
C
D
C
D
C
D
C
D
C
12345
A:F C E B D
B:E F D A C
C:D A F E B
D:C E B F A
E:B D A C F
F:A B C D E
12チームの場合
このまま回転を続ける‥‥.
14
実際のスケジュールは?
同一性判定
 与えられた2つのスケジュールがチーム名の付け
替えで、一致するか? O(n3)
(2n :チーム数)
O(n2) × n
12345
:中 阪
巨 A:F
C横
E 広
B Dヤ
広 B:E F D A C
阪 C:D A F E B
ヤ D:C E B F A
横 E:B D A C F
中 F:A B C D E
12345
巨人:中 阪 横 広 ヤ
阪神:ヤ 巨 中 横 広
広島:横 中 ヤ 巨 阪
中日:巨 広 阪 ヤ 横
横浜:広 ヤ 巨 阪 中
ヤクルト:阪 横 広 中 巨
巨広阪ヤ横
 スロットの順も入れ替えてよいときは? NP完全?
15
部分スケジュール完成問題
123456789
A:J F G C H B
B:I G D F E A
10チームのリーグ戦
C:H D E A F G
6日目まで作成済み
D:G C B J I E
7日目以降の
E:F J C H B D
対戦を組みたい
F:E A I B C H
G:D B A I J C
H:C I J E A F
I:B H F G D J
J:A E H D G I
16
スケジュール完成問題のNP完全性
NP完全な問題
1. 3つのスロット以外がすべて埋められているとき、残
りの3スロットを上手に埋めて、スケジュールを完成
できるか? [Easton, 2003]
2. 禁止集合P:(i,j,k) ∈P ⇔チームiとjの戦いはスロットk
で行ってはいけない。Pで与えられる禁止制約を守
るスケジュールが存在するか? [Schaerf, 1999]
17
Premature Sets [Rosa and Wallis]
 いくつかのスロットを埋めた時、それを満たしてスケ
ジュールを完成できるか?
premature set:スケジュールを完成できない, 部分割当
定理[Rosa and Wallis]
nスロットの premature set は存在する。
2n>6ならば、3スロット以下のpremature set は無い。
3スロットまでは、どう決めても大丈夫
Open Problem: 最小 premature set のサイズは?
18
Carry Over Effects (COE)
阪神は横浜にcoeを与える
…
阪神はヤクルトにcoe を与える
ヤクルトは横浜にcoeを与える
横浜は巨人にcoeを与える
…
1 2 3 4 5
巨人:中 阪 横 広 ヤ
阪神:ヤ 巨 中 横 広
広島:横 中 ヤ 巨 阪
中日:巨 広 阪 ヤ 横
横浜:広 ヤ 巨 阪 中
ヤクルト:阪 横 広 中 巨
COEは、できるだけ均等に分散している方が良い。
19
COEを均等に分布させる
 完全に均等になるか?
 2n = 2k ならば、完全に均等にできる [Russell (1980)]
 予想:2n≠2k の時, 完全に均等にできない?
8チームの場合
1:4567823
2:5483617
3:8652471
4:1276358
5:2138746
6:7314285
7:6841532
8:3725164
20
COE値最小化の現状
2n
6
8
10
12
14
16
18
20
Value (チーム順序対毎のCOE数の2乗和)
60 (optimal Henz, Mueller, Thiel)
56 (optimal Russell)
122 (Trick)
188 (HMT and van Brandenburg)
260 (Russell)
240 (optimal, Russell)
428 (Russell)
520 (Russell)
21
Kirkmanスケジュールを用いる [宮代・松井2006]
①
1:6
2:5
3:4
4:3
5:2
6:1
②
3
6
1
5
4
2
③
5
4
6
2
1
3
④
2
1
5
6
3
4
⑤
4
3
2
1
6
5
仮想的に
変形
①
1:1
2:5
3:4
4:3
5:2
6:1
②
3
2
1
5
4
2
③
5
4
3
2
1
3
④
2
1
5
4
3
4
⑤
4
3
2
1
5
5
 チーム n 以外は,1, 3, …, n-1, 2, 4, …, n-2 の対戦順
→ 非常に coe値 が大きくなる
 置換σをランダムに発生させ, coe値 が小さいスケジュール
を求めた
 計算時間 10万秒
22
COE値最小化の現状
2n Value (チーム順序対毎のCOE数の2乗和)
6
60 (optimal Henz, Mueller, Thiel)
8
56 (optimal Russell)
宮代・松井(2006)
10 122 (Trick)
→108
12 188 (HMT and van Brandenburg)
→176
14 260 (Russell)
→254
16 240 (optimal, Russell)
18 428 (Russell)
→400
20 520 (Russell)
→488
23
Section 2 スケジュール + 試合場
場所付き総当りリーグ戦
各チームに本拠地があり,どちらかの本拠地で試合
• 本拠地での試合:ホームゲーム
• 遠征先での試合:アウェイゲーム
1
1:3
2:4
3:1
4:2
2
2
1
4
3
3
4 ← 1対4 (1の本拠地)
3
2
対応
1 ← 1対4 (1の本拠地)
スケジュール(4チーム)
25
試合場所の割当(HAT)
①
巨人:中
阪神:ヤ
広島:横
中日:巨
横浜:広
ヤクルト:阪

②
阪
巨
中
広
ヤ
横
③
横
中
ヤ
阪
巨
広
④
広
横
巨
ヤ
阪
中
⑤
ヤ
広
阪
横
中
巨
① ② ③ ④ ⑤
巨:A A H A H
阪:A H A A H
→ 広:H H A H A
中:H A H A H
横:A H A H A
ヤ:H A H H A
Home-Away Table (HAT)
各試合をどちらの本拠地で行う?
H:ホーム
A:アウェイ
26
ブレーク
 HA割当の質の指標:「ブレーク」
 チーム t がスロット s に ブレーク を持つ ⇔
… s-1 s …
… s-1 s …
t : … A A … もしくは t : … H H …
t: A A A A H H A → (チーム t のブレーク数)= 4
 HHブレークとAAブレークは,(スロット毎に)同じ数.
AA
AA
AH
HA
HH
HH
27
ブレーク数の下界[de Werra]
ブレーク数の意味で最も良いHATは?
(ブレーク数が少ない方が良い.)
ブレーク最小 HAT [de Werra’80]
補題:ブレーク数の最小値 ≧ チーム数-2
証明:ブレークの無いHA-パターンは2つ
AHAHAHAHAHAHA
HAHAHAHAHAHAH
(HAHAHAHAHAHAH)
許容HATの行は互い異なるHAパターンを持つ.
2チームはブレークを持たない.
他のチームは1つ以上のブレークを持つ.
28
ブレーク最小HATのスケジュール[de Werra]
 ホームゲーム・アウェイゲームを決める.
A
A
B E
E
F
D
B E
D
A
B
E
F
F
C
A
B E F
A
C
12345
A:F C E B D
B:E F D A C
C:D A F E B
D:C E B F A
E:B D A C F
F:A B C D E
D
C
D
アウェイ
ゲームチーム
C
D
F
B
C
ホーム
ゲームチーム
29
実際のスケジュールは?
ブレーク均等HATのスケジュール
 ブレーク数 2n-2 → 若干の不公平
• 全てのチームが 1個ブレークを持つHA割当
①②③④⑤
1:A H A H A
2:H A H A H
3:A H H A H
4:H A A H A
5:A H A H H
6:H A H A A
ブレーク数 2n-2
ブレーク最小HAT
①②③④⑤
1:H H A H A
2:A A H A H
3:A H A A H
4:H A H H A
5:A H A H H
6:H A H A A
ブレークが各チーム1個
ブレーク均等HAT
(ブレーク2n 個とは違う)
30
補完パターン[de Werra]
ブレーク最小HATの各行(HA-パターン)は下記のよう
にブレークが1つ(以下)のもの.
HAHAHAHAHHAHAHA :HA-パターン
AHAHAHAHAAHAHAH :補完パターン
補題:ブレーク最小HATが,あるHA-パターンを含む
ならば,その補完パターンも含む.
証明: (背理法)
s
あるパターン: ‥‥‥‥AHAAHA‥‥‥‥‥
‥‥‥‥HAHAHA‥‥AA ‥
‥‥‥‥HAHAHA ‥ HH‥‥
‥‥AA‥AHAHAH‥‥‥‥‥
sスロットとs+1スロットのHとAの数が異なる.矛盾.
31
ブレーク最小とブレーク均等スケジュール
 (ブレーク最小HAT+スケジュール)は、ブレーク位
置でユニークに表現できる
 最終スロットと開始スロットをつなげる.
10101
するとブレークがあるのはn箇所
12345
A:F C E B D
F:A B C D E
B:E F D A C
 開始スロットが
C:D A F E B
ブレークが有る所:ブレーク最小 D:C E B F A
ブレークが無い所:ブレーク均等 E:B D A C F
各チームは(開始スロット含め)
ブレークが丁度1個で,
補完パターン対に分かれている
n個のブレーク最小HAT
n-1個のブレーク均等HAT
32
ブレーク最小化=ブレーク最化
[Miyashiro&M]
 ブレーク数最小化/最大化
• 従来は別々に議論
• でも,実は同じ問題
 与えられた入力に対して,
「ブレーク数最大化の最適解」
⇔ 「ブレーク数最小化の最適解」 を行う変換
33
最小化/最大化の変換[Miyashiro&M]
 HA割当Τ
• 偶数スロットのHAを逆転
①②③④⑤
①②③④⑤
1:A H A H A
1:A A A A A
2:H A H A H
2:H H H H H
3:A H H A H
3:A A H H H
4:H A A H A 変換 4:H H A A A
5:A H A H H ⇔ 5:A A A A H
6:H A H A A
6:H H H H A
HA割当Τ
HA割当Τ’
34
最小化/最大化の変換[Miyashiro&M]
 対戦制約は満たされる
 ブレーク ← (変換) → ブレーク無し
•
•
•
•
AA → AH or HA
HH → HA or AH
AH → AA or HH
HA → HH or AA
∴ (元のブレーク数)+(変換後のブレーク数)
=定数=2n(2n-2)
ブレーク数最小化と最大化は等価
35
ブレーク最大化+(3H,3A 禁止) [Russell & Leung]
 3連続H, 3連続Aを持たないHATが存在するスケ
ジュールで,ブレーク数最大のものは?
定理 [Russell & Leung]
3連続H, 3連続Aを持たず、2n(n-1)-(2n-4) 以上のブ
レークが存在するHATを持つスケジュールが存在
する.
open problem: 上記の下界は,下限なのか?
36
Section 3 スケジュール → HAT
スケジュールの作成方法 [Regin]等
①②③
①②③
①②③
1:2 4 3
1:A H A 1:H H H
2:1 3 4 → 2:H H A 2:A A A
3:4 2 1
3:A A H 3:H H A
4:3 1 2
4:H A H, 4:A A H,…
入力:スケジュール
出力:対応するHA割当
 制約条件: 対戦ペアの片方はH,片方がA
(対戦制約)
→ 目的関数: “ブレーク数”
38
HA割当のブレーク数
HA割当に含まれるブレーク数
①②③
1:A H A
2:H H A
3:A A H
4:H A H 2個
①②③
1:H H H
2:A A A
3:H H A
4:A A H 6個
ブレーク数が小 → A と H なるべく交互
ブレーク数が大 → A の連続,H の連続
39
ブレーク数最適化問題
 ブレーク数最小化/最大化問題
• 入力: スケジュール (チーム数 2n)
• 出力: 対戦制約を満たすHA割当のうち,
ブレーク数が最小/最大のもの.
→ 最小化,最大化の意味,先行研究
40
ブレーク数最小化の目的
 ブレーク数最小化の目的
• できるだけ A と H を交互に (公平性)
12345
1:A A A A A
2:A H A H A
3:H H A A H
4:H A H A A
5:A A H H H
6:H H H H H (14)
12345
1:A H H A A
2:H H H A H
3:A H A H A
4:H A A H H
5:A A H A H
6:H A A H A (8)
41
最小化問題の先行研究
 ブレーク数最小化問題
• NP-困難??
• 先行研究 (分枝限定ベース)

Regin (1998), 制約論理,~チーム数20

Trick (2000), 整数計画,~チーム数22

Elf, Jünger, Rinadi (2003), MAX CUT + ABACUS,
~チーム数26
• Elf et al. による予想 (後述)
42
最小化の計算時間
チーム数
16
18
20
22
24
26
Regin (CP)
5
80
5603
CPU
200MHz
環境 Solver (ILOG)
Trick (IP)
34
43
1092
7802
266MHz
CPLEX (ILOG)
Elf 他 (MAX CUT)
1
6
9
37
73
339
(単位:秒)
300MHz
ABACUS
43
ブレーク数最大化の目的 [Rusell&Leung]等
 ブレーク数最大化の目的: 総移動回数最小化
総移動回数=2n(2nー1)-(1/2)(ブレーク数)
(移動回数は,リーグの最初と最後の移動を含
む)
A H H A H (ブレーク数1,移動回数4)
→ 経験的に,移動距離最小化問題の
良い解を与える
(アメリカマイナーリーグ野球等での研究)
44
最小(¼) –最大(¾)の存在[Miyashiro&M]
(元のブレーク数)+(変換後のブレーク数)=4n(n-1)
定理 [Miyashiro&M] 任意のスケジュールは,それに対
応するHATで,ブレーク数が n(n-1) 以下のものを
持つ.(3n(n-1) 以上のものも持つ.)
ブレーク無し
スロットを, 2スロット以降を2つづ区切る.
対の後ろのスロットは,ブレークを無くす.
各対毎に,HAを(1/2)の確率で反転.
ブレーク総数の期待値は n(n-1)
2n
第 i スロット
第 i +1スロット
2n-1
各スロットのブレーク数の期待値 n
45
先行研究の予想
 ブレーク数最小化問題の計算複雑度
• NP-困難 ??
• Elf et al. (2003); 最小化問題
最小ブレーク数が小さい入力 → 計算時間小
• 特に 「最小ブレーク数=2n-2 の例」 は
短時間で最適解が求まる (チーム数:2n)
→ 何らかの特殊構造,多項式時間性??
Elf らの予想: MAX CUT が多項式時間で解ける
グラフのクラスと関連?
46
ブレーク数の判定問題
問題 (P)
入力: チーム数 2n のスケジュール
出力: ブレーク数 2n-2 のHA割当;
存在しないなら不能.

ブレーク数最小化問題の
判定問題version; 目的関数値 2n-2
 O(n3) アルゴリズムを開発
47
問題の変換
問題 (P)
入力: チーム数 2n のスケジュール
出力: ブレーク数 2n-2 のHA割当;
存在しないなら不能.
(ブレーク数 2n-2)
←(変換)→(ブレーク数 2n(2n-2) - (2n-2))
問題(P’)
出力:ブレーク数 2n(2n-2) - (2n-2) のHA割当;
存在しないなら不能.
48
HA割当の変換
ブレーク数 2n-2
①②③④⑤
1:A H A H A
2:H A H A H
3:H H A H A
4:A A H A H
5:A H A A H
6:H A H H A
ブレーク数 2n(2n-2)-(2n-2)
①②③④⑤
1:A A A A A
2:H H H H H
3:A A H H H
4:H H A A A
5:A A A H H
6:H H H A A
 ブレーク 0個のチーム → 全てA or 全てH
 ブレーク 1個のチーム → 1回だけA→H or H→A
49
変換後の問題
①②③④⑤
1:A H H H H
問題 (P’): 左のような
2:A A A H H
HA割当が存在?
3:H A A A A
注意:対戦制約
4:H H H H H ← 全てH
5:A A A A A ← 全てA
6:H H H A A ← 1回だけ替わる
子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i<j )
• チーム i が全てA,チーム j が全てHと固定
50
子問題のHA割当
子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i<j )
•
チーム i が全てA,チーム j が全てHと固定
① ② ③ ④ ⑤
1:4
2:6
3:5
4:1
5:3
6:2

2 5
1 4
4 6
3 2
6 1
5 3
入力
3
5
1
6
2
4
6
3
2
5
4
1
① ② ③ ④ ⑤
1:A
H
2:
A
H
3:A A A A A
4:H H H H H
5:H
A
6:
H A
子問題(P34’)
残りのチーム: A…AH…H もしくは H…HA…A
となる,対戦制約を満たすHA割当が存在するか?
51
制約条件の伝播
① ② ③ ④ ⑤
① ②
1:A
H
1:A
2:
A
H
2:A A
3:A A A A A → 3:A A
4:H H H H H
4:H H
5:H
A
5:H
6:
H A
6:H H

③ ④
H
A
A A
H H
⑤
H
H
A
H
A
H A A
制約条件:A→H or H→Aが 1回,入力に対応
→ Hを FALSE, Aを TRUE とすれば,
2SAT として定式化可能.
52
計算複雑度の算定
 制約式
• A→H,H→A が1回だけ起きる
• 対戦制約を満たす
→ 2SAT で定式化可能!
 2SAT: 変数,2-クローズの個数 O(n2)
→ 子問題 1個あたり O(n2), 問題(P) は O(n4)
 アルゴリズムの工夫 → O(n3)
53
ブレーク数 2n-2 に対する結果
問題 (P)
入力: チーム数 2n のスケジュール
出力: ブレーク数 2n-2 のHA割当;
存在しないなら不能.
 O(n3) アルゴリズム
• ブレーク数 2n-2 の解 → 最小化問題の最適解
• Elf たちの予想に対する一つの答え
54
ブレーク数最小化問題を解く
[Miyashiro&Matsui 2004]
[Suzuka, Miyashiro, Yoshise, Matsui 2005]
[Suzuka, Miyashiro, Yoshise, Matsui 2006]
ブレーク数がチーム数以上
 与えられたスケジュールが,
ブレーク数 2n 以下のHA割当を持たない場合は?
→ 先行研究(分枝限定ベース)では,
計算時間がかかる
• 最小ブレーク数が大きい問題例
• チーム数の大きな問題
56
LP/SDP 緩和を用いたアルゴリズム
 線形計画/半正定値計画緩和を用いた
多項式時間確率的アルゴリズム
• MAX(MIN) RES CUT として定式化
• LP緩和: ランダム化丸め法を適用
• SDP緩和:Goemans, Williamson (1995) の
0.878 確率的近似アルゴリズムを適用
• 極めて高速な,質の良い解の生成を確認
57
MAX RES CUT
MAX RES CUT
入力: 無向グラフ G=(V, E), 各枝に対する非負重み
+ 頂点ペア {vi1, vj1}, …, {vik, vjk}
出力: 頂点ペア{vi1, vj1}, …, {vik, vjk}を分け,
重み最大のカット集合
 NP-困難
 Goemans, Williamson (1995) による
0.878 確率的近似アルゴリズム
58
ブレーク数最小化問題と MAX RES CUT
①②③
1:2 4 3
①
1 ●
②
●
③
●
2:1 3 4
2 ●
●
●
3:4 2 1
3 ●
●
●
4:3 1 2
4 ●
●
●
A
頂点集合を「Aの集合」と「Hの集合」に分割
カット=ブレーク無
H
59
MAX RES CUT のグラフ
チーム数 頂点数
16
18
20
22
24
26
30
40
枝数
240 288
306 224
380 360
462 440
552 528
650 624
870 840
1560 1520
近似比
計算時間[秒]
1.000
2.1
1.000
3.4
0.994
4.9
0.995
8.0
0.989
12
0.985< 18
?
38
?
179
60
計算実験の結果
チーム数
16
18
20
22
24
26
30
40
最適値(IP)
192
248
312
382
458
540 or 542
―
―
SDP緩和
192
248
310
380
452
534
720
1306
差
0
0
2
2
4
6 or 8
?
?
近似比率
1.000
1.000
0.994
0.995
0.989
0.985<
?
?
(超平面分離1000回)
61
計算時間の比較
チーム数
16
18
20
22
24
26
30
40
Régin
1
18
1245
Trick
6.5
13
323
678
(2ヶ月<)
Elf et al.
0.3
2
3
12
24
111
本研究 [秒]
2.1
3.4
4.9
8.0
12
18
38
179
(CPU: 900 MHz, SDP Solver: SDPA 6.0, 超平面分離1000回)
62
総移動距離最小化:
各チームの移動距離の総和
チームkの移動距離:
対戦組合せ表と会場割当が与えられたとき、kのホーム
を出発し、対戦組合せ表と会場割当で規定される順に、
対戦会場を訪問し、最後にkのホームに戻るまでの経
路の長さ
総移動回数最小化:各ホーム間距離が1の特殊ケース
総移動回数=2n(2nー1)-(1/2)(ブレーク数)
総移動距離最小化≒ブレーク最大化
63
計算機実験結果
 総移動距離最小化問題:16~40チーム
LP緩和:近似比率(1~1.002),
8秒(40チーム)
SDP緩和:近似比率(1~1.01), 2000秒(40チーム)
分枝限定法(厳密解法):
52秒(40チーム)
 総移動回数最小化問題:16~40チーム
LP緩和:近似比率(1.1~1.4),
10秒(40チーム)
SDP緩和:近似比率(1~1.16), 2200秒(40チーム)
分枝限定法(厳密解法):
2700秒(18チーム)
64
Section 4 HAT→スケジュール
スケジュールの作成方法
123
123
1:2 4 3
1:2 4 3
2:1 3 4 → 2:1 3 4
3:4 2 1
3:4 2 1
4:3 1 2
4:3 1 2
① 対戦相手決定
② 場所を割当
線
123
123
1:A H A
1:2 4 3 ① HATを決定
2:H H A → 2:1 3 4 ② 対戦相手を割当
3:A A H
3:4 2 1
4:H A H
4:3 1 2
66
許容HAT
HAT作成 →(チーム割当)→ スケジュール作成
123
1:A H A
2:H H A →
3:A A H
4:H A H
123
123
1:2 4 3 1:2 3 4
2:1 3 4 2:1 4 3
3:4 2 1 3:4 1 2
4:3 1 2,4:3 2 1
許容HAT: スケジュールを生成できるHAT
cf. 不能HAT
67
HAT 許容性判定問題
HAT 許容性判定問題
Input: HAT (チーム数 2n; 2n-1 スロット);
Output: 与えられたHATが許容HATか?
• 長年の未解決問題 [de Werra 1980,
Nemhauser & Trick 1998]
• 理論的結果ほぼ無し (整数計画法)
• 計算複雑度は未知 (NP-完全??)
目標: 「許容HATの良い特徴付け」
68
許容HATである必要条件
12345
12345
1:A A H A H 1:A A H A H
2:A H H A H 2:A H H A H
3:A H A A H 3:A H A A H
4:H H A H A
01100
5:H A A H A
6:H A H H A
min{#A, #H}
α({1,2,3}) = (0+1+1+0+0) - 3×2/2 = -1 ⇒ 不能
α(T) = ∑s min{#A(T, s), #H(T, s)} - |T| C 2
69
関数αの定義
許容HATの必要条件
∀T⊆U, ∑s min{#A(T, s), #H(T, s)} ≧ |T| C 2
関数αの定義
α(T) = ∑s min{#A(T, s), #H(T, s)} - |T| C 2
許容 HAT であるための必要条件 Ⓐ
∀T⊆U, α(T)≧0
70
許容HATの必要条件
許容HAT の必要条件 Ⓐ: ∀T⊆U, α(T)≧0
• 22n 本の不等式による表現
HAT 許容性判定における新たな解析手法
→ 特殊なクラスの HAT を考え,
それらの許容性と条件 Ⓐ の関係を考察
(最小HAT と均等HAT, 十分条件?)
71
許容性判定と条件Ⓐ
 一般的に好ましい HAT
• ブレーク最小HAT (ブレーク数 2n-2),
• ブレーク均等HAT (ブレーク数 2n)
→ これらの HAT の許容性を簡単に判定したい
 条件Ⓐ 「∀T⊆U, α(T)≧0」 がどのくらい有効か?
→ 計算機実験により評価
72
計算実験の結果
#teams
4
6
8
10
12
14
#総数
3
10
35
126
462
1716
# Ⓐ #許容 #teams
3
5
14
18
55
91
3
5
14
18
55
91
#Ⓐ
#許容
16
6435 255
18
24310 408
20
92378 1102
22 352716 1995
24 1352078 5313
26 5200300 9850
255
408
1102
1995
5313
9850
#総数
26チーム以下の最小HAT,均等HATならば,
「∀T ⊆U,α(T)≧0 ⇔ 許容HAT」
73
実験結果のまとめ
 提案した条件 Ⓐ は,非常に強い必要条件
• 26チーム以下の最小HAT,均等HATの場合
∀T⊆U, α(T)≧0 ⇔ 許容HAT

28チーム以上は未実験
(30チームまでは確認 [池辺 2003])
• 未解決予想: 任意のチーム数で必要十分条件
74
定理の概要
 ∀T⊆U ={1,2,…,2n} に対してα(T) を考えると...
• 22n 本の不等式をチェック?
証明した定理
任意のチーム数の最小HAT,均等HATに関して,
「∀T⊆U, α(T) ≧ 0 (条件 Ⓐ )」 を満たすか否かは
O(n4)でチェック可能
75
条件Ⓐに関する定理
定理: (チーム番号を前処理でソート後)
任意の均等HAT (最小HAT)について,
∀T⊆U, α(T) ≧ 0
不等式 O(22n) 本
⇔
全ての連続な T⊆U に対して α(T) ≧ 0
不等式 O(n2) 本
 連続な T : {1, 2, 3}, {5, 6}, {2, 3, 4, 5}, …
 非連続な T : {1, 2, 4}, {5, 7}, {2, 5, 6, 7}, …
76
成果の応用
 実用上は,均等HATの中でも
さらに “良い” 均等HAT を求めるケース有
• 許容である
• スロット 2, 2n-1 のブレークをできるだけ避ける.
[Nemhauser&Trick 1998]
77
MIM予想と柏原の反例 [Miyashiro,Iwasaki,M]
予想[Miyashiro,Iwasaki,M]
最小HATと均等HATにおいて、
∀T⊆U, α(T) ≧ 0は、
許容となる必要十分条件。
appearing in recent handbooks
[Ikebe]により、30チームまで
反例が無いことが確認された。
一般のHATでは十分でない。
柏原による反例
01:HHHHAAAAHAAAH
02:HHHHAAAAHHAAA
03:HHHHAAAAAHHAA
04:HHHHAAAAAAHHA
05:HHHHAAAAAAAHH
06:HHHHHHHHAAAAH
07:AAAAHHHHHAAAH
08:AAAAHHHHHHAAA
09:AAAAHHHHAHHAA
10:AAAAHHHHAAHHA
11:AAAAHHHHAAAHH
12:HHAAHAAAHHHHH
13:AAHAAHAAHHHHA
14:AAAHAAHHHHHHH
78
Section 5 応用と実用
Traveling Tournament Problem
http://mat.gsia.cmu.edu/TOURN/ (see Trick’s HP)
2重総当り戦 : n で 2n-2 スロット
目的は、総移動距離の最小化 (各チームは、自分の
ホームから出発し、自分のホームに帰ってくる)
どのチームも、3H と 3A は禁止
No repeaters (A 対 Bの直後の B 対 A は禁止)
距離行列は、対称
80
8チームの問題例(NL8)
 Feasible Solution:
•
•
•
•
•
41505 (Easton June 4, 1999),
41113 (Easton Jan 27, 2000),
40416 (Cardemil, July 2 2002),
39947 (Zhang, August 19 2002),
39721 (Easton, August 25 2002)
 Lower Bound:
• 38760 (Trick Dec 15, 2000),
• 38870 (Easton Jan 2, 2001),
• 39479 (Easton Feb 26, 2002)
81
10チームの問題例(NL10)
 Feasible Solution:
•
•
•
•
•
•
68691 (Rottembourg and Laburthe June 2001),
66369 (Dorrepaal, June 21 2002),
66037 (Cardemil, July 2 2002),
64597 (Zhang August 6, 2002),
61608 (Zhang August 19, 2002),
59583 (Van Hentenryck January 14, 2003)
 Lower Bound:
• 56506 (Waalewijn July 2001),
• 57500 (Easton June 2002)
82
12チームの問題例(NL12)
 Feasible Solution:
• 143655 (Rottembourg and Laburthe May 2001),
• 138850 (Larichi, Lapierre, and Laporte July 8 2002),
• 125803 (Cardemil, July 2 2002),
• 119990 (Dorrepaal July 16, 2002),
• 119012 (Zhang, August 19 2002),
• 118955 (Cardemil, November 1 2002),
• 114153 (Van Hentenryck January 14, 2003),
• 113090 (Van Hentenryck February 26, 2003),
• 112800 (Van Hentenryck June 26, 2003),
• 112684 (Langford February 16, 2004),
• 112549 (Langford February 27, 2004),
• 112298 (Langford March 12, 2004),
• 111248 (Van Hentenryck May 13, 2004).
 Lower Bound:
• 107483 (Waalewign August 2001)
83
14チームの問題例(NL14)
 Feasible Solution:
•
•
•
•
•
•
•
•
•
301113 (Rottembourg and Laburthe June 2001),
262010 (Larichi, Lapierre, Laport July 8 2002),
216108 (Cardemil, July 2 2002),
207075 (Zhang, August 28 2002),
205894 (Cardemil, November 20 2002),
195555 (Van Hentenryck January 14, 2003),
190368 (Van Hentenryck February 26, 2003),
190056 (Langford April 22, 2004),
189766 (Van Hentenryck May 13, 2004).
 Lower Bound:
• 182797 (Waalewign August 2001)
84
16チームの問題例(NL16)
 Feasible Solution:
•
•
•
•
•
•
•
•
•
•
312623 (Easton January 2002),
308413 (Cardemil, July 2 2002),
301256 (Zhang August 6 2002),
293175 (Zhang, August 28 2002),
284235 (Shen, October 16 2002),
281660 (Shen, January 6 2003)
277766 (Van Hentenryck January 14, 2003),
273802 (Van Hentenryck February 26 2003),
272,902 (Langford, January 16, 2004),
267,194 (Van Hentenryck, June 26, 2003).
 Lower Bound:
• 248852 (Easton January 2002)
85
総移動回数最小化
Traveling Tournament Problem
総移動回数最小化≒ブレーク数最大化
ブレーク数の上界と,改訂ポリゴン法によるブレーク数
 n ≡ 0 (mod 3)のとき
• (4/3)n2 – 2n – ((2/3)n – 2 ).
 n ≡ 1 (mod 3)のとき
• (4/3)n (n – 1) – (n – 2) – (2/3) (n – 1).
 n ≡ 2 (mod 3)のとき
• (4/3)n (n – 2) – (5/3) (n – 2).
86
改訂ポリゴン法(n ≡ 1 (mod 3) の場合)
1
n
3
頂
点
ご
と
に
向
き
を
反
転
87
改訂ポリゴン法
(n ≡ 1 (mod 3) の場合)
S
S
n
n
3スロット毎に向きを反転
したポリゴンを利用
s {1, 2, 3} mod6
s {4, 5, 0} mod6
88
1重総当たりリーグ戦から2重総当りリーグ戦へ
(n ≡ 1 (mod 3) の場合)
X i とX i をジグザグに接続.
AAA
HHH
AAH
HAA
AHH
HAA
AAH
X
X1
X2 X3
X4
X5
X6
X7
X
X1
X2 X3
X4
X5
X6
X7
AHH
HAA
AHH
HHA
HHH
AAA
HHA
89
整数計画法を用いた構成法のブレーク数
 n ≡ 0 (mod 3)のとき
• (4/3)n2 – 2n – (n – 2 ).
 n ≡ 1 (mod 3)のとき
• (4/3)n (n – 1) – (n – 2) . 最適値
 n ≡ 2 (mod 3)のとき
• (4/3)n (n – 2) – (n – 2).
上界とのギャップ
n ≦ 46 について構成可能であることを
計算機実験により確認.
90
1重総当たりリーグ戦から2重総当りリーグ戦へ
例: n = 22
X  ( X1 , X 2 ,, X n1/ 3 ) と3 スロット毎に分割.
X i:X iのホームアウェーを反転させたスケジュール
X
X1
AAA
X
X1
HHH
X2 X3
X4
X5
X6
X7
AAA
AAA
AAA
AAA
AAA
X2 X3
X4
X5
X6
X7
HHH
HHH
HHH
HHH
AAA
HHH
HHH
91
1重総当たりリーグ戦から2重総当りリーグ戦へ
(n ≡ 1 (mod 3) の場合)
X i とX i を交互に接続.
AAA
AAA
AAA
AAA
AAA
AAA
AAA
X
X1
X2 X3
X4
X5
X6
X7
X
X1
X2 X3
X4
X5
X6
X7
HHH
HHH
HHH
HHH
HHH
HHH
HHH
92
1重総当たりリーグ戦から2重総当りリーグ戦へ
(n ≡ 1 (mod 3) の場合)
X1
X1
X2
X2
X3
X3
X4
X4
X5
X5
X6
X6
X7
X7
4連続H(A)がない.
Xにおいて,全てのチームが,
スロット 3i+1 (i ≧ 1)にブレークをもつ.
このようなXが存在することを
n ≦ 46 について計算機実験により確認.
93
比較(ブレーク数の上界との差)
n (mod 3)
手法
ポリゴン
IP
0
1
2
(2/3)n – 2
(2/3)(n – 1)
(5/3)(n – 2)
n–2
0
n–2
94
実例
 実例では?
 3Hと3Aの禁止
 各チームのブレークは2回程度
95
1993年のJリーグ前半戦(ブレーク数)
1
H
H
A
A
A
H
H
H
A
A
2 3 4 5
K:
H A A H
V:
A A H A
M:
H A A H
E:
H H A H
J:
H A H A
S:
A H H A
F:
A H A H
G:
A H H A
N:
A H H A
R:
H A A H
2 2 6 0
2重総当り戦
6
H
A
A
H
A
A
H
A
H
H
8
7
A
H
H
A
H
H
A
H
A
A
0
8
H
A
A
H
A
A
H
H
H
A
2
9101112131415161718
A A A H A A H A H H
H H A A H H A H A H
H A H H A H A H A H
A A H H A A H A H A
H A H A H H A H A H
H H A A H H A H A A
A H A H A A H A H A
A H A A H H A A H A
A H H A H A H A H A
H A H H A A H H A H
0 4 2 6 0 8 0 2 0 2
7
5
2
5
2
6
2
6
3
6
43
10チーム
96
望ましい
2001年のJリーグ後半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
0
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
A
H
H
H
A
H
A
H
A
H
A
A
A
H
A
2
A
H
A
A
A
H
A
H
A
H
A
H
H
H
A
H
0
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
4
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
A
A
A
A
H
H
H
A
H
A
H
A
H
H
H
A
2
H
H
H
H
H
A
A
A
A
H
A
H
A
A
A
H
2
A A
A A
A A
A A
A A
H H
H H
H H
H H
A H
H A
A H
H H
H H
H A
A A
012
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
0
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
2
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
0
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
8
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
0
3
2
3
2
3
3
2
3
1
1
1
1
2
3
1
1
32
16チーム
97
読み方
2001年のJリーグ前半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
0
A H
H H
A H
H H
A H
H A
A A
H A
A A
H H
A A
H H
A A
H A
A A
H H
010
A
A
A
A
A
H
H
H
H
A
H
A
H
H
H
A
0
H
H
H
H
A
A
A
H
A
H
A
H
A
A
A
H
2
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
2
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
6
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
A
H
H
H
A
A
0
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
0
H
H
H
A
H
A
H
A
H
A
H
A
A
A
H
A
6
A
H
A
A
A
H
A
H
A
H
A
H
H
H
A
H
2
1
3
1
4
1
1
3
1
3
1
3
3
2
1
1
3
32
16チーム
98
読み方
セリエA2000/2001シーズン(2重総当たり戦)
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
HAAHAHAHAHAHHAHAH
HAHAHHAHAHAHAAHAH
AHAHAHHAHAHAHAHAH
AHHAHAHAAHAHAHAHA
AHAHHAHAAHAHAHAHA
AHAHAHHAHAHAAHAHA
AHAHAHAHAHAAHHAHA
AHAHHAHAHAHAHAHAH
AHAHAAHAHAHAHHAHA
HAHAHAAHAHAHHAHAH
HAHAHAHAHAHHAAHAH
HAAHAHAHHAHAHAHAH
HAHAAHAHHAHAHAHAH
HAHAHAAHAHAHAHAHA
HAHAAHAHAHAHAHAHA
HAHAHAHAHAHHAHAHA
AHHAHAHAHAHAAHAHA
AHHAHAHAHAHAAHAHA
AHHAHAHAHAHAAHAHA
AHAHAAHAHAHAHHAHA
HAHAHAAHAHAHAHAHA
HAAHAHAHHAHAHAHAH
HAHAAHAHHAHAHAHAH
HAHAHAAHAHAHHAHAH
HAHAHAHAHAHHAAHAH
HAHAAHAHAHAHAHAHA
HAHAHHAHAHAHAAHAH
AHAHAHHAHAHAAHAHA
AHAHAHAHAHAAHHAHA
AHHAHAHAAHAHAHAHA
AHAHHAHAAHAHAHAHA
AHAHAHHAHAHAHAHAH
AHAHHAHAHAHAHAHAH
AHAHAHAHAHAAHAHAH
HAAHAHAHAHAHHAHAH
HAAHAHAHAHAHHAHAH
99
セリエA2000/2001シーズン(2重総当たり戦)
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA
AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA
AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH
AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH
AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH
AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH
AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA
AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH
HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA
HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA
HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA
HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA
HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH
HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH
HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
100
セリエA2000/2001シーズン(ホームゲーム)
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
H H H H H HH H H HH H H H H H H
H H HH H H H H H H H H H H HH H
H H HH H H H H HH H H H H H H H
HH H H H H H H H H H HH H H H H
H HH H H H H H H H H HH H H H H
H H HH H H H H H H H H H HH H H
H H H H H HH H H H H H H HH H H
H HH H H H H H HH H H H H H H H
H H H H H HH H H H HH H H H H H
H H H H H HH H H H H HH H H H H
H H H H H HH H H H H H H H HH H
H H H HH H H H H HH H H H H H H
H H H HH H H H H H HH H H H H H
H H H H H H H H H H HH H H H H H
H H H H H H H H H HH H H H H H H
H H H H H HH H H H H H H H H H H
HH H H H H H H H H H H H HH H H
HH H H H H H H H H H H H HH H H
030212020022200020202120200132000
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
2
2
33
101
セリエA2000/2001シーズン(アウェイゲーム)
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
AA A A A A A A A A A A A AA A A
A A A A A AA A A A AA A A A A A
A A A A A A A A A A AA A A A A A
A A A AA A A A A AA A A A A A A
A A A AA A A A A A AA A A A A A
A A A A A AA A A A A AA A A A A
A A A A A AA A A A A A A A AA A
A A A A A A A A A AA A A A A A A
A A AA A A A A A A A A A A AA A
A A AA A A A A A A A A A AA A A
A A A A A AA A A A A A A AA A A
AA A A A A A A A A A AA A A A A
A AA A A A A A A A A AA A A A A
A A AA A A A A AA A A A A A A A
A AA A A A A A AA A A A A A A A
A A A A A A A AA A A A A AA A A
A A A A A AA A A AA A A A A A A
A A A A A AA A A AA A A A A A A
020212020013200030302120200222000
2
2
1
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
34
102
セリエA2000/2001シーズン (ブレーク数)
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA
AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA
AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH
AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH
AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH
AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH
AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA
AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH
HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA
HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA
HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA
HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA
HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH
HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH
HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
050424040035400050504240400354000
2重総当り戦
4
4
3
4
4
4
4
3
4
4
4
4
4
3
3
3
4
4
67
103
課題
 各チームのブレーク2回の(スケジュール+HAT)
の特徴付け.
 2重総当り戦での,ブレーク数最小化
 3Hと3Aの禁止
 移動距離
 観客動員数予想
104
おわり
105
106
ダウンロード

H - nifty