HAT Feasibility Problem -

スポーツスケジューリング
東京大学大学院情報理工学系研究科松井知己
東京大学今堀慎治
筑波大学鈴鹿順美
東京大学藤原伸友
東京農工大学宮代隆平
筑波大学吉瀬章子
スポーツスケジューリング
中央大学理工学部松井知己
東京大学今堀慎治
筑波大学鈴鹿順美
東京大学藤原伸友
東京農工大学宮代隆平
筑波大学吉瀬章子
発表の概要






はじめに
スケジュール
スケジュール＋試合場所
スケジュール→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はじまりは，６年前．．．．．
スケジューリングの実務における現状 (アメリカ)
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
総当りリーグ戦とグラフ




各チームを頂点とする完全グラフ．
各枝は試合に対応する．
各試合日には，全てのチームが１試合を戦う．
各試合日の試合は，グラフ上の完全マッチング．
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
１２３４５
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
実際のスケジュールは？
同一性判定
 与えられた２つのスケジュールがチーム名の付け
替えで、一致するか？ O(n3)
（2n :チーム数）
O(n2) × n
１２３４５
：中阪
巨 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
１２３４５
巨人：中阪横広ヤ
阪神：ヤ巨中横広
広島：横中ヤ巨阪
中日：巨広阪ヤ横
横浜：広ヤ巨阪中
ﾔｸﾙﾄ：阪横広中巨
巨広阪ヤ横
 スロットの順も入れ替えてよいときは？ NP完全？
15
部分スケジュール完成問題
１２３４５６７８９
Ａ：ＪＦＧＣＨＢ
Ｂ：ＩＧＤＦＥＡ
10チームのリーグ戦
Ｃ：ＨＤＥＡＦＧ
6日目まで作成済み
Ｄ：ＧＣＢＪＩＥ
7日目以降の
Ｅ：ＦＪＣＨＢＤ
対戦を組みたい
Ｆ：ＥＡＩＢＣＨ
Ｇ：ＤＢＡＩＪＣ
Ｈ：ＣＩＪＥＡＦ
Ｉ：ＢＨＦＧＤＪ
Ｊ：ＡＥＨＤＧＩ
16
スケジュール完成問題のNP完全性
NP完全な問題
1. ３つのスロット以外がすべて埋められているとき、残
りの３スロットを上手に埋めて、スケジュールを完成
できるか？ [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 は存在する。
２n＞６ならば、3スロット以下のpremature set は無い。
3スロットまでは、どう決めても大丈夫
Open Problem: 最小 premature set のサイズは？
18
Carry Over Effects （COE)
阪神は横浜にcoeを与える
…
阪神はヤクルトにcoe を与える
ヤクルトは横浜にcoeを与える
横浜は巨人にcoeを与える
…
１２３４５
巨人：中阪横広ヤ
阪神：ヤ巨中横広
広島：横中ヤ巨阪
中日：巨広阪ヤ横
横浜：広ヤ巨阪中
ﾔｸﾙﾄ：阪横広中巨
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]
①
１：６
２：５
３：４
４：３
５：２
６：１
②
３
６
１
５
４
２
③
５
４
６
２
１
３
④
２
１
５
６
３
４
⑤
４
３
２
１
６
５
仮想的に
変形
①
１：１
２：５
３：４
４：３
５：２
６：１
②
３
２
１
５
４
２
③
５
４
３
２
１
３
④
２
１
５
４
３
４
⑤
４
３
２
１
５
５
 チーム 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対4 （1の本拠地）
３
２
対応
１ ← 1対4 （1の本拠地）
スケジュール（4チーム）
25
試合場所の割当（HAT)
①
巨人：中
阪神：ヤ
広島：横
中日：巨
横浜：広
ﾔｸﾙﾄ：阪

②
阪
巨
中
広
ヤ
横
③
横
中
ヤ
阪
巨
広
④
広
横
巨
ヤ
阪
中
⑤
ヤ
広
阪
横
中
巨
① ② ③ ④ ⑤
巨：ＡＡＨＡＨ
阪：ＡＨＡＡＨ
→ 広：ＨＨＡＨＡ
中：ＨＡＨＡＨ
横：ＡＨＡＨＡ
ヤ：ＨＡＨＨＡ
Home-Away Table (HAT)
各試合をどちらの本拠地で行う？
Ｈ：ホーム
Ａ：アウェイ
26
ブレーク
 ＨＡ割当の質の指標：「ブレーク」
 チーム t がスロット s にブレークを持つ ⇔
… s－1 s …
… s－1 s …
t ： … ＡＡ … もしくは t ： … ＨＨ …
t：ＡＡＡＡＨＨＡ → （チーム t のブレーク数）＝ 4
 HHブレークとAAブレークは，（スロット毎に）同じ数．
AA
AA
AH
HA
HH
HH
27
ブレーク数の下界[de Werra]
ブレーク数の意味で最も良いHATは？
(ブレーク数が少ない方が良い.)
ブレーク最小 HAT [de Werra’80]
補題：ブレーク数の最小値 ≧ チーム数－2
証明：ブレークの無いHA-パターンは２つ
AHAHAHAHAHAHA
HAHAHAHAHAHAH
（HAHAHAHAHAHAH）
許容HATの行は互い異なるHAパターンを持つ．
2チームはブレークを持たない.
他のチームは１つ以上のブレークを持つ.
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
１２３４５
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個ブレークを持つＨＡ割当
①②③④⑤
１：ＡＨＡＨＡ
２：ＨＡＨＡＨ
３：ＡＨＨＡＨ
４：ＨＡＡＨＡ
５：ＡＨＡＨＨ
６：ＨＡＨＡＡ
ブレーク数 2n－2
ブレーク最小HAT
①②③④⑤
１：ＨＨＡＨＡ
２：ＡＡＨＡＨ
３：ＡＨＡＡＨ
４：ＨＡＨＨＡ
５：ＡＨＡＨＨ
６：ＨＡＨＡＡ
ブレークが各チーム１個
ブレーク均等HAT
（ブレーク２n 個とは違う）
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＋スケジュール）は、ブレーク位
置でユニークに表現できる
 最終スロットと開始スロットをつなげる．
１０１０１
するとブレークがあるのはn箇所
１２３４５
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を逆転
①②③④⑤
①②③④⑤
１：ＡＨＡＨＡ
１：ＡＡＡＡＡ
２：ＨＡＨＡＨ
２：ＨＨＨＨＨ
３：ＡＨＨＡＨ
３：ＡＡＨＨＨ
４：ＨＡＡＨＡ変換４：ＨＨＡＡＡ
５：ＡＨＡＨＨ ⇔ ５：ＡＡＡＡＨ
６：ＨＡＨＡＡ
６：ＨＨＨＨＡ
ＨＡ割当Τ
ＨＡ割当Τ’
34
最小化／最大化の変換[Miyashiro&M]
 対戦制約は満たされる
 ブレーク ← （変換） → ブレーク無し
•
•
•
•
ＡＡ → ＡＨ or ＨＡ
ＨＨ → ＨＡ or ＡＨ
ＡＨ → ＡＡ or ＨＨ
ＨＡ → ＨＨ or ＡＡ
∴ （元のブレーク数）＋（変換後のブレーク数）
＝定数＝2n(2n－2)
ブレーク数最小化と最大化は等価
35
ブレーク最大化＋（３H，３A 禁止） [Russell & Leung]
 ３連続H, ３連続Aを持たないHATが存在するスケ
ジュールで，ブレーク数最大のものは？
定理 [Russell & Leung]
３連続H, ３連続Aを持たず、2n(n-1)-(2n-4) 以上のブ
レークが存在するHATを持つスケジュールが存在
する．
open problem: 上記の下界は，下限なのか？
36
Section 3 スケジュール → HAT
スケジュールの作成方法 [Regin]等
①②③
①②③
①②③
１：２４３
１：ＡＨＡ１：ＨＨＨ
２：１３４ → ２：ＨＨＡ２：ＡＡＡ
３：４２１
３：ＡＡＨ３：ＨＨＡ
４：３１２
４：ＨＡＨ，４：ＡＡＨ，…
入力：スケジュール
出力：対応するＨＡ割当
 制約条件：対戦ペアの片方はＨ，片方がＡ
（対戦制約）
→ 目的関数： “ブレーク数”
38
ＨＡ割当のブレーク数
ＨＡ割当に含まれるブレーク数
①②③
１：ＡＨＡ
２：ＨＨＡ
３：ＡＡＨ
４：ＨＡＨ 2個
①②③
１：ＨＨＨ
２：ＡＡＡ
３：ＨＨＡ
４：ＡＡＨ 6個
ブレーク数が小 → ＡとＨなるべく交互
ブレーク数が大 → Ａの連続，Ｈの連続
39
ブレーク数最適化問題
 ブレーク数最小化／最大化問題
• 入力：スケジュール（チーム数 2n）
• 出力：対戦制約を満たすＨＡ割当のうち，
ブレーク数が最小／最大のもの．
→ 最小化，最大化の意味，先行研究
40
ブレーク数最小化の目的
 ブレーク数最小化の目的
• できるだけＡとＨを交互に（公平性）
１２３４５
１：ＡＡＡＡＡ
２：ＡＨＡＨＡ
３：ＨＨＡＡＨ
４：ＨＡＨＡＡ
５：ＡＡＨＨＨ
６：ＨＨＨＨＨ (14)
１２３４５
１：ＡＨＨＡＡ
２：ＨＨＨＡＨ
３：ＡＨＡＨＡ
４：ＨＡＡＨＨ
５：ＡＡＨＡＨ
６：ＨＡＡＨＡ (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)(ブレーク数)
（移動回数は，リーグの最初と最後の移動を含
む）
ＡＨＨＡＨ (ブレーク数1，移動回数4）
→ 経験的に，移動距離最小化問題の
良い解を与える
（アメリカマイナーリーグ野球等での研究）
44
最小(¼) –最大(¾)の存在[Miyashiro&M]
（元のブレーク数）＋（変換後のブレーク数）=4n(n－1)
定理 [Miyashiro&M] 任意のスケジュールは，それに対
応するHATで，ブレーク数が n(n－1) 以下のものを
持つ．（3n(n－1) 以上のものも持つ．）
ブレーク無し
スロットを, 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 のＨＡ割当；
存在しないなら不能．

ブレーク数最小化問題の
判定問題version; 目的関数値 2n－2
 O(n3) アルゴリズムを開発
47
問題の変換
問題 (P)
入力：チーム数 2n のスケジュール
出力：ブレーク数 2n－2 のＨＡ割当；
存在しないなら不能．
（ブレーク数 2n－2）
←（変換）→（ブレーク数 2n(2n－2) － (2n－2)）
問題(P’)
出力：ブレーク数 2n(2n－2) － (2n－2) のＨＡ割当；
存在しないなら不能．
48
ＨＡ割当の変換
ブレーク数 2n－2
①②③④⑤
１：ＡＨＡＨＡ
２：ＨＡＨＡＨ
３：ＨＨＡＨＡ
４：ＡＡＨＡＨ
５：ＡＨＡＡＨ
６：ＨＡＨＨＡ
ブレーク数 2n(2n－2)－(2n－2)
①②③④⑤
１：ＡＡＡＡＡ
２：ＨＨＨＨＨ
３：ＡＡＨＨＨ
４：ＨＨＡＡＡ
５：ＡＡＡＨＨ
６：ＨＨＨＡＡ
 ブレーク 0個のチーム → 全てＡ or 全てＨ
 ブレーク 1個のチーム → 1回だけＡ→Ｈ or Ｈ→Ａ
49
変換後の問題
①②③④⑤
１：ＡＨＨＨＨ
問題 (P’)：左のような
２：ＡＡＡＨＨ
ＨＡ割当が存在？
３：ＨＡＡＡＡ
注意：対戦制約
４：ＨＨＨＨＨ ← 全てＨ
５：ＡＡＡＡＡ ← 全てＡ
６：ＨＨＨＡＡ ← 1回だけ替わる
子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i＜j )
• チーム i が全てＡ，チーム j が全てＨと固定
50
子問題のＨＡ割当
子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i＜j )
•
チーム i が全てＡ，チーム j が全てＨと固定
① ② ③ ④ ⑤
１：４
２：６
３：５
４：１
５：３
６：２

２５
１４
４６
３２
６１
５３
入力
３
５
１
６
２
４
６
３
２
５
４
１
① ② ③ ④ ⑤
１：Ａ
Ｈ
２：
Ａ
Ｈ
３：ＡＡＡＡＡ
４：ＨＨＨＨＨ
５：Ｈ
Ａ
６：
ＨＡ
子問題(P34’)
残りのチーム：Ａ…ＡＨ…ＨもしくはＨ…ＨＡ…Ａ
となる，対戦制約を満たすＨＡ割当が存在するか？
51
制約条件の伝播
① ② ③ ④ ⑤
① ②
１：Ａ
Ｈ
１：Ａ
２：
Ａ
Ｈ
２：ＡＡ
３：ＡＡＡＡＡ → ３：ＡＡ
４：ＨＨＨＨＨ
４：ＨＨ
５：Ｈ
Ａ
５：Ｈ
６：
ＨＡ
６：ＨＨ

③ ④
Ｈ
Ａ
ＡＡ
ＨＨ
⑤
Ｈ
Ｈ
Ａ
Ｈ
Ａ
ＨＡＡ
制約条件：Ａ→Ｈ or Ｈ→Ａが 1回，入力に対応
→ Ｈを FALSE, Ａを TRUE とすれば，
2SAT として定式化可能．
52
計算複雑度の算定
 制約式
• Ａ→Ｈ，Ｈ→Ａが1回だけ起きる
• 対戦制約を満たす
→ 2SAT で定式化可能！
 2SAT: 変数，2-クローズの個数 O(n2)
→ 子問題 1個あたり O(n2), 問題(P) は O(n4)
 アルゴリズムの工夫 → O(n3)
53
ブレーク数 2n－2 に対する結果
問題 (P)
入力：チーム数 2n のスケジュール
出力：ブレーク数 2n－2 のＨＡ割当；
存在しないなら不能．
 O(n3) アルゴリズム
• ブレーク数 2n－2 の解 → 最小化問題の最適解
• Elf たちの予想に対する一つの答え
54
ブレーク数最小化問題を解く
[Miyashiro&Matsui 2004]
[Suzuka, Miyashiro, Yoshise, Matsui 2005]
[Suzuka, Miyashiro, Yoshise, Matsui 2006］
ブレーク数がチーム数以上
 与えられたスケジュールが，
ブレーク数 2n 以下のＨＡ割当を持たない場合は？
→ 先行研究（分枝限定ベース）では，
計算時間がかかる
• 最小ブレーク数が大きい問題例
• チーム数の大きな問題
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
①②③
１：２４３
①
１ ●
②
●
③
●
２：１３４
２ ●
●
●
３：４２１
３ ●
●
●
４：３１２
４ ●
●
●
A
頂点集合を「Ａの集合」と「Ｈの集合」に分割
カット＝ブレーク無
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
総移動距離最小化：
各チームの移動距離の総和
チームｋの移動距離：
対戦組合せ表と会場割当が与えられたとき、ｋのホーム
を出発し、対戦組合せ表と会場割当で規定される順に、
対戦会場を訪問し、最後にｋのホームに戻るまでの経
路の長さ
総移動回数最小化：各ホーム間距離が１の特殊ケース
総移動回数＝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→スケジュール
スケジュールの作成方法
１２３
１２３
１：２４３
１：２４３
２：１３４ → ２：１３４
３：４２１
３：４２１
４：３１２
４：３１２
① 対戦相手決定
② 場所を割当
線
１２３
１２３
１：ＡＨＡ
１：２４３ ① HATを決定
２：ＨＨＡ → ２：１３４ ② 対戦相手を割当
３：ＡＡＨ
３：４２１
４：ＨＡＨ
４：３１２
66
許容HAT
HAT作成 →（チーム割当）→ スケジュール作成
１２３
１：ＡＨＡ
２：ＨＨＡ →
３：ＡＡＨ
４：ＨＡＨ
１２３
１２３
１：２４３１：２３４
２：１３４２：１４３
３：４２１３：４１２
４：３１２，４：３２１
許容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である必要条件
１２３４５
１２３４５
１：ＡＡＨＡＨ１：ＡＡＨＡＨ
２：ＡＨＨＡＨ２：ＡＨＨＡＨ
３：ＡＨＡＡＨ３：ＡＨＡＡＨ
４：ＨＨＡＨＡ
０１１００
５：ＨＡＡＨＡ
６：ＨＡＨＨＡ
min{#Ａ, #Ｈ}
α({1,2,3}) = (0+1+1+0+0) － 3×2/2 = －1 ⇒ 不能
α(T) ＝ ∑s min{#Ａ(T, s), #Ｈ(T, s)} － |T| C 2
69
関数αの定義
許容HATの必要条件
∀T⊆U, ∑s min{#Ａ(T, s), #Ｈ(T, s)} ≧ |T| C 2
関数αの定義
α(T) ＝ ∑s min{#Ａ(T, s), #Ｈ(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
８チームの問題例（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
１０チームの問題例（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
１２チームの問題例（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
実例
 実例では？
 ３Hと３Aの禁止
 各チームのブレークは２回程度
95
1993年のＪリーグ前半戦(ブレーク数）
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
１０チーム
96
望ましい
2001年のＪリーグ後半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
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年のＪリーグ前半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
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
読み方
セリエＡ2000/2001シーズン（２重総当たり戦）
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
セリエＡ2000/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
100
セリエＡ2000/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
セリエＡ2000/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
セリエＡ2000/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
２重総当り戦
4
4
3
4
4
4
4
3
4
4
4
4
4
3
3
3
4
4
67
103
課題
 各チームのブレーク２回の（スケジュール＋HAT）
の特徴付け．
 ２重総当り戦での，ブレーク数最小化
 ３Hと３Aの禁止
 移動距離
 観客動員数予想
104
おわり
105
106

Download Report