スポーツスケジューリング 東京大学大学院 情報理工学系研究科 松井 知己 東京大学 今堀慎治 筑波大学 鈴鹿順美 東京大学 藤原伸友

Presentation on theme: "スポーツスケジューリング 東京大学大学院 情報理工学系研究科 松井 知己 東京大学 今堀慎治 筑波大学 鈴鹿順美 東京大学 藤原伸友"— Presentation transcript:

1 スポーツスケジューリング 東京大学大学院 情報理工学系研究科 松井 知己 東京大学 今堀慎治 筑波大学 鈴鹿順美 東京大学 藤原伸友
東京大学大学院 情報理工学系研究科 松井 知己 東京大学 今堀慎治 筑波大学　鈴鹿順美 東京大学 藤原伸友 東京農工大学　宮代隆平 筑波大学　吉瀬章子

2 中央大学 理工学部 松井 知己 東京大学 今堀慎治 筑波大学 鈴鹿順美 東京大学 藤原伸友 東京農工大学 宮代隆平 筑波大学 吉瀬章子
スポーツスケジューリング 中央大学　理工学部 松井 知己 東京大学 今堀慎治 筑波大学　鈴鹿順美 東京大学 藤原伸友 東京農工大学　宮代隆平 筑波大学　吉瀬章子

3 発表の概要 はじめに スケジュール スケジュール＋試合場所 スケジュール→HAT HAT→スケジュール 応用と実用

4 スポーツ・スケジューリング スポーツ・スケジューリング （対戦日程計画） Timetabling の一分野 初期の研究： 1970 年代後半
スポーツ競技などの最適な対戦日程を決める スケジュール作成アルゴリズムの構築 初期の研究： 1970 年代後半 ここ数年で研究が活発化 Timetabling の中でも大きな分野に

5 Bibliography on Practice and Theory of Automated Timetabling
～1995まで論文数の推移

6 はじめに はじめに 読売新聞 2004/11/9 はじまりは，６年前 ．．．．．

7 スケジューリングの実務における現状 (アメリカ)
MLB: 26週間の間に30球団による2430試合を開催 公募採用の外部業者が受託 は，マサチューセッツ在住の夫婦に依頼． 2005年はカーネギーメロン大学のグループが作成． ~~~(2004年にスケジュール作成会社を起業) NFL： 17週間の間に32チームが16試合ずつ， 年間256試合以上を開催． TV中継の視聴率は40%超で， 1億3000万人以上が観戦していると言われている． 2003年より最適化技術（ILOG社)を用いて開発された システムで作成．

8 スケジューリングの実務における現状 (日本)
プロ野球 セリーグ： 6球団，年間420試合 球団の営業担当者と連盟職員で構成される「日程編成会議」で作成．リーグ理事会の承認を経て前年秋ごろに発表．詳細は非公開 (計算機は用いているらしい)． サッカー J1リーグ：10チーム(1993年)から18チーム(2005年)の総当り戦．スケジュール作成の詳細は完全非公開． アイスホッケー アジアリーグ：9チーム各4回戦総当たりとグループゲームを含め、全171試合1チーム38試合。 （中国(3)，日本(4)，韓国(2)） 海外遠征が頻繁にあり移動コスト削減が課題．航空機運行日程がきつい制約．自由度はかなり低い．特異な制約が多い． アメリカンフットボール 社会人リーグ：18チーム(6チーム×3ディビジョン)による総当たり戦．年間45試合 子問題に分割可能，比較的簡単．事務局長が作成．

9 スポーツ・スケジューリングの実例 スケジューリングの目的 スケジュールへの要求 現実問題から発生した研究分野 移動距離最小化，観客数最大化，
公平性最大化，… → 収益最大化 スケジュールへの要求 試合開催場所，固定された試合， TV中継，各チームの強さ，予備日，… 現実問題から発生した研究分野

10 現在の手法 スケジューリング問題の理論的研究 スケジューリングに用いている数理手法 抽象化された問題，先行研究ともに少ない
グラフ理論，デザイン理論，実験計画法，… スケジューリングに用いている数理手法 数理計画法 整数計画，分枝限定法，組合せ多面体論，… メタ・ヒューリスティクス SA, GA, ローカルサーチ，タブーサーチ，… 制約論理法

11 Section 1 スケジュール

12 スケジュール ① ② ③ ④ ⑤ （スロット） 巨人：中 阪 横 広 ヤ 阪神：ヤ 巨 中 横 広 広島：横 中 ヤ 巨 阪
① ② ③ ④ ⑤ （スロット） 巨人：中 阪 横 広 ヤ 阪神：ヤ 巨 中 横 広 広島：横 中 ヤ 巨 阪 中日：巨 広 阪 ヤ 横 横浜：広 ヤ 巨 阪 中 リーグ戦のスケジュール ﾔｸﾙﾄ：阪 横 広 中 巨 ・ チーム数：2n (チーム) ・ スロット（試合日）：2n－1 チーム数が奇数の時はダミーのチームを加える

13 総当りリーグ戦とグラフ 各チームを頂点とする完全グラフ． 各枝は試合に対応する． 各試合日には，全てのチームが１試合を戦う．
各試合日の試合は，グラフ上の完全マッチング． E D C B A F F A E B D C

14 スケジュールの存在性 [Kirkman 1847 or earlier]
以下のような円盤を回して，試合を決める． A B C D E F １２３４５ 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チームの場合 このまま回転を続ける‥‥. 実際のスケジュールは？

15 同一性判定 与えられた２つのスケジュールがチーム名の付け替えで、一致するか？ O(n3) 　　（2n :チーム数） スロットの順も入れ替えてよいときは？　NP完全？ 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 巨広阪ヤ横中 ：中 阪 横 広 ヤ 巨 広 阪 ヤ 横

16 部分スケジュール完成問題 Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ 10チームのリーグ戦
１ ２ ３ ４ ５ ６ ７ ８ ９ Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ チームのリーグ戦 Ｃ：Ｈ Ｄ Ｅ Ａ Ｆ Ｇ 日目まで作成済み Ｄ：Ｇ Ｃ Ｂ Ｊ Ｉ Ｅ 日目以降の Ｅ：Ｆ Ｊ Ｃ Ｈ Ｂ Ｄ 対戦を組みたい Ｆ：Ｅ Ａ Ｉ Ｂ Ｃ Ｈ Ｇ：Ｄ Ｂ Ａ Ｉ Ｊ Ｃ Ｈ：Ｃ Ｉ Ｊ Ｅ Ａ Ｆ Ｉ：Ｂ Ｈ Ｆ Ｇ Ｄ Ｊ Ｊ：Ａ Ｅ Ｈ Ｄ Ｇ Ｉ

17 スケジュール完成問題のNP完全性 NP完全な問題 ３つのスロット以外がすべて埋められているとき、残りの３スロットを上手に埋めて、スケジュールを完成できるか？　 [Easton, 2003] 禁止集合P：(i,j,k) ∈P ⇔チームiとjの戦いはスロットkで行ってはいけない。Pで与えられる禁止制約を守るスケジュールが存在するか？　[Schaerf, 1999]

18 Premature Sets [Rosa and Wallis]
いくつかのスロットを埋めた時、それを満たしてスケジュールを完成できるか？ premature set：スケジュールを完成できない, 部分割当 定理[Rosa and Wallis] nスロットの premature set は存在する。 ２n＞６ならば、3スロット以下のpremature set は無い。 3スロットまでは、どう決めても大丈夫 Open Problem: 最小 premature set のサイズは？

19 Carry Over Effects （COE)
　 １ ２ ３ ４ ５ 巨人：中 阪 横 広 ヤ 阪神：ヤ 巨 中 横 広 広島：横 中 ヤ 巨 阪 中日：巨 広 阪 ヤ 横 横浜：広 ヤ 巨 阪 中 ﾔｸﾙﾄ：阪 横 広 中 巨 COEは、できるだけ均等に分散している方が良い。 阪神は横浜にcoeを与える … 阪神はヤクルトにcoe を与える ヤクルトは横浜にcoeを与える 横浜は巨人にcoeを与える …

20 COEを均等に分布させる 8チームの場合 1:4567823 2:5483617 3:8652471 4:1276358 5:2138746
完全に均等になるか？ 2n = 2k ならば、完全に均等にできる　[Russell (1980)] 予想：2n≠2k の時, 完全に均等にできない？ 1: 2: 3: 4: 5: 6: 7: 8: 8チームの場合

21 COE値最小化の現状 6 60 (optimal Henz, Mueller, Thiel) 8 56 (optimal Russell)
2n Value　（チーム順序対毎のCOE数の2乗和） 6 60 (optimal Henz, Mueller, Thiel) 8 56 (optimal Russell) 10　　122 (Trick) (HMT and van Brandenburg) (Russell) (optimal, Russell) (Russell) (Russell)

22 Kirkmanスケジュールを用いる [宮代・松井2006]
① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：６ ３ ５ ２ ４ １：１ ３ ５ ２ ４ ２：５ ６ ４ １ ３ ２：５ ２ ４ １ ３ ３：４ １ ６ ５ ２ ３：４ １ ３ ５ ２ ４：３ ５ ２ ６ １ 仮想的に ４：３ ５ ２ ４ １ ５：２ ４ １ ３ ６ 変形 ５：２ ４ １ ３ ５ ６：１ ２ ３ ４ ５ ６：１ ２ ３ ４ ５ チーム n 以外は，1, 3, …, n-1, 2, 4, …, n-2 の対戦順 → 非常に coe値 が大きくなる 置換σをランダムに発生させ， coe値 が小さいスケジュールを求めた 計算時間 10万秒

23 COE値最小化の現状 6 60 (optimal Henz, Mueller, Thiel)
2n Value　（チーム順序対毎のCOE数の2乗和） 6 60 (optimal Henz, Mueller, Thiel) 8 56 (optimal Russell) 宮代・松井(2006) 10　 122 (Trick) →108 (HMT and van Brandenburg) →176 (Russell) →254 (optimal, Russell) (Russell) →400 (Russell) →488

24 Section 2 スケジュール + 試合場

25 場所付き総当りリーグ戦 各チームに本拠地があり，どちらかの本拠地で試合 １ ２ ３ １：３ ２ ４ ← 1対4 （1の本拠地）
本拠地での試合：ホームゲーム 遠征先での試合：アウェイゲーム １ ２ ３ １：３ ２ ４ ← 1対4 （1の本拠地） ２：４ １ ３ ３：１ ４ ２ 対応 ４：２ ３ １ ← 1対4 （1の本拠地） スケジュール（4チーム）

26 試合場所の割当（HAT) ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ 巨人：中 阪 横 広 ヤ 巨：Ａ Ａ Ｈ Ａ Ｈ
① ② ③ ④ ⑤ ① ② ③ ④ ⑤ 巨人：中 阪 横 広 ヤ 巨：Ａ Ａ Ｈ Ａ Ｈ 阪神：ヤ 巨 中 横 広 阪：Ａ Ｈ Ａ Ａ Ｈ 広島：横 中 ヤ 巨 阪 → 広：Ｈ Ｈ Ａ Ｈ Ａ 中日：巨 広 阪 ヤ 横 中：Ｈ Ａ Ｈ Ａ Ｈ 横浜：広 ヤ 巨 阪 中 横：Ａ Ｈ Ａ Ｈ Ａ ﾔｸﾙﾄ：阪 横 広 中 巨 ヤ：Ｈ Ａ Ｈ Ｈ Ａ 　　　　　　　　　　　　　　　　　Home-Away Table (HAT) 各試合をどちらの本拠地で行う？ Ｈ：ホーム Ａ：アウェイ

27 ブレーク ＨＡ割当の質の指標：「ブレーク」 チーム t がスロット s に ブレーク を持つ ⇔ … s－1 s … … s－1 s …
t ： … Ａ Ａ … もしくは t ： … Ｈ Ｈ … t： Ａ Ａ Ａ Ａ Ｈ Ｈ Ａ → （チーム t のブレーク数）＝ 4 HHブレークとAAブレークは，（スロット毎に）同じ数． AA AH HA HH

28 ブレーク数の下界[de Werra] ブレーク数の意味で最も良いHATは？ (ブレーク数が少ない方が良い.)
ブレーク最小 HAT [de Werra’80] 補題：ブレーク数の最小値 ≧ チーム数－2 証明：ブレークの無いHA-パターンは２つ AHAHAHAHAHAHA HAHAHAHAHAHAH （HAHAHAHAHAHAH） 許容HATの行は互い異なるHAパターンを持つ． 2チームはブレークを持たない. 他のチームは１つ以上のブレークを持つ. In prevous slide, we saw undesired HAT because of unequality among particular teams. What is optimal HAT in terms of equality? As we have seen, HAT consist of small number of breaks is better. It is already known two kinds of HAT with small number of breaks. One, minimizing breaks HAT. Two team have no breaks, and other team have exactly one break. But in this HAT, there is two team which has no breaks. So we prefer equitable HAT rather than minimizing breaks HAT. In equitable HAT, all teams have exactly one break.

29 ブレーク最小HATのスケジュール[de Werra]
ホームゲーム･アウェイゲームを決める． A B C D E F １２３４５ 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 アウェイ ゲームチーム ホーム １２３４５ 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 実際のスケジュールは？

30 ブレーク均等HATのスケジュール ブレーク数 2n－2 → 若干の不公平 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤
全てのチームが 1個ブレークを持つＨＡ割当 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：Ａ Ｈ Ａ Ｈ Ａ １：Ｈ Ｈ Ａ Ｈ Ａ ２：Ｈ Ａ Ｈ Ａ Ｈ ２：Ａ Ａ Ｈ Ａ Ｈ ３：Ａ Ｈ Ｈ Ａ Ｈ ３：Ａ Ｈ Ａ Ａ Ｈ ４：Ｈ Ａ Ａ Ｈ Ａ ４：Ｈ Ａ Ｈ Ｈ Ａ ５：Ａ Ｈ Ａ Ｈ Ｈ ５：Ａ Ｈ Ａ Ｈ Ｈ ６：Ｈ Ａ Ｈ Ａ Ａ ６：Ｈ Ａ Ｈ Ａ Ａ ブレーク数 2n－ ブレークが各チーム１個 ブレーク最小HAT ブレーク均等HAT （ブレーク２n 個とは違う）

31 補完パターン[de Werra] ブレーク最小HATの各行（HA-パターン）は下記のようにブレークが1つ(以下)のもの．
HAHAHAHAHHAHAHA ：HA-パターン AHAHAHAHAAHAHAH ：補完パターン 補題：ブレーク最小HATが，あるHA-パターンを含むならば，その補完パターンも含む． 証明： （背理法） 　　　　　　 s あるパターン： ‥‥‥‥AHAAHA‥‥‥‥‥ ‥‥‥‥HAHAHA‥‥AA ‥ ‥‥‥‥HAHAHA ‥ HH‥‥ ‥‥AA‥AHAHAH‥‥‥‥‥ sスロットとs+1スロットのHとAの数が異なる．矛盾.

32 １０１０１ １２３４５ A：F C E B D F：A B C D E B：E F D A C C：D A F E B
ブレーク最小とブレーク均等スケジュール （ブレーク最小HAT＋スケジュール）は、ブレーク位置でユニークに表現できる 最終スロットと開始スロットをつなげる． するとブレークがあるのはn箇所 各チームは（開始スロット含め） ブレークが丁度1個で， 補完パターン対に分かれている 開始スロットが ブレークが有る所：ブレーク最小 ブレークが無い所：ブレーク均等 n個のブレーク最小HAT n-1個のブレーク均等HAT 　１０１０１　　　 １２３４５ 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

33 ブレーク最小化＝ブレーク最化 [Miyashiro&M]
ブレーク数最小化／最大化 従来は別々に議論 でも，実は同じ問題 与えられた入力に対して， 「ブレーク数最大化の最適解」 ⇔ 「ブレーク数最小化の最適解」 を行う変換

34 最小化／最大化の変換[Miyashiro&M]
ＨＡ割当Τ 偶数スロットのHAを逆転 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：Ａ Ｈ Ａ Ｈ Ａ １：Ａ Ａ Ａ Ａ Ａ ２：Ｈ Ａ Ｈ Ａ Ｈ ２：Ｈ Ｈ Ｈ Ｈ Ｈ ３：Ａ Ｈ Ｈ Ａ Ｈ ３：Ａ Ａ Ｈ Ｈ Ｈ ４：Ｈ Ａ Ａ Ｈ Ａ 変換 ４：Ｈ Ｈ Ａ Ａ Ａ ５：Ａ Ｈ Ａ Ｈ Ｈ ⇔ ５：Ａ Ａ Ａ Ａ Ｈ ６：Ｈ Ａ Ｈ Ａ Ａ ６：Ｈ Ｈ Ｈ Ｈ Ａ ＨＡ割当Τ ＨＡ割当Τ’

35 最小化／最大化の変換[Miyashiro&M]
対戦制約は満たされる ブレーク ← （変換） → ブレーク無し ＡＡ → ＡＨ or ＨＡ ＨＨ → ＨＡ or ＡＨ ＡＨ → ＡＡ or ＨＨ ＨＡ → ＨＨ or ＡＡ ∴ （元のブレーク数）＋（変換後のブレーク数） ＝定数＝2n(2n－2) ブレーク数最小化と最大化は等価

36 ブレーク最大化＋（３H，３A 禁止） [Russell & Leung]
３連続H, ３連続Aを持たないHATが存在するスケジュールで，ブレーク数最大のものは？ 定理 [Russell & Leung] ３連続H, ３連続Aを持たず、2n(n-1)-(2n-4) 以上のブレークが存在するHATを持つスケジュールが存在する． open problem: 上記の下界は，下限なのか？

37 Section 3 スケジュール → HAT

38 スケジュールの作成方法 [Regin]等 ① ② ③ ① ② ③ ① ② ③ １：２ ４ ３ １：Ａ Ｈ Ａ １：Ｈ Ｈ Ｈ
① ② ③ ① ② ③ ① ② ③ １：２ ４ ３ １：Ａ Ｈ Ａ １：Ｈ Ｈ Ｈ ２：１ ３ ４ → ２：Ｈ Ｈ Ａ ２：Ａ Ａ Ａ ３：４ ２ １ ３：Ａ Ａ Ｈ ３：Ｈ Ｈ Ａ ４：３ １ ２ ４：Ｈ Ａ Ｈ， ４：Ａ Ａ Ｈ，… 入力：スケジュール 出力：対応するＨＡ割当 制約条件： 対戦ペアの片方はＨ，片方がＡ （対戦制約） → 目的関数： “ブレーク数”

39 ＨＡ割当のブレーク数 ＨＡ割当に含まれるブレーク数 ① ② ③ ① ② ③ １：Ａ Ｈ Ａ １：Ｈ Ｈ Ｈ ２：Ｈ Ｈ Ａ ２：Ａ Ａ Ａ
① ② ③ ① ② ③ １：Ａ Ｈ Ａ １：Ｈ Ｈ Ｈ ２：Ｈ Ｈ Ａ ２：Ａ Ａ Ａ ３：Ａ Ａ Ｈ ３：Ｈ Ｈ Ａ ４：Ｈ Ａ Ｈ 2個 ４：Ａ Ａ Ｈ 6個 ブレーク数が小 → Ａ と Ｈ なるべく交互 ブレーク数が大 → Ａ の連続，Ｈ の連続

40 ブレーク数最適化問題 ブレーク数最小化／最大化問題 ブレーク数が最小／最大のもの． → 最小化，最大化の意味，先行研究
入力： スケジュール （チーム数 2n） 出力： 対戦制約を満たすＨＡ割当のうち， ブレーク数が最小／最大のもの． → 最小化，最大化の意味，先行研究

41 ブレーク数最小化の目的 ブレーク数最小化の目的 １ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ａ Ａ Ａ １：Ａ Ｈ Ｈ Ａ Ａ
できるだけ Ａ と Ｈ を交互に （公平性） １ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ａ Ａ Ａ １：Ａ Ｈ Ｈ Ａ Ａ ２：Ａ Ｈ Ａ Ｈ Ａ ２：Ｈ Ｈ Ｈ Ａ Ｈ ３：Ｈ Ｈ Ａ Ａ Ｈ ３：Ａ Ｈ Ａ Ｈ Ａ ４：Ｈ Ａ Ｈ Ａ Ａ ４：Ｈ Ａ Ａ Ｈ Ｈ ５：Ａ Ａ Ｈ Ｈ Ｈ ５：Ａ Ａ Ｈ Ａ Ｈ ６：Ｈ Ｈ Ｈ Ｈ Ｈ (14) ６：Ｈ Ａ Ａ Ｈ Ａ (8)

42 最小化問題の先行研究 ブレーク数最小化問題 NP-困難?? 先行研究 （分枝限定ベース） Elf et al. による予想 （後述）
Regin (1998), 制約論理，～チーム数20 Trick (2000), 整数計画，～チーム数22 Elf, Jünger, Rinadi (2003), MAX CUT ＋ ABACUS, ～チーム数26 Elf et al. による予想 （後述）

43 最小化の計算時間 チーム数 Regin (CP) Trick (IP) Elf 他 (MAX CUT) （単位：秒） CPU MHz MHz MHz 環境 Solver (ILOG) CPLEX (ILOG) ABACUS

44 ブレーク数最大化の目的 [Rusell&Leung]等
ブレーク数最大化の目的： 総移動回数最小化 総移動回数＝2n(2nー1)－(1/2)(ブレーク数) （移動回数は，リーグの最初と最後の移動を含む） Ａ Ｈ Ｈ Ａ Ｈ (ブレーク数1，移動回数4） → 経験的に，移動距離最小化問題の 良い解を与える （アメリカマイナーリーグ野球等での研究）

45 最小(¼) –最大(¾)の存在[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スロット 各スロットのブレーク数の期待値 n 2n-1

46 先行研究の予想 ブレーク数最小化問題の計算複雑度 Elf らの予想： MAX CUT が多項式時間で解ける グラフのクラスと関連？
NP-困難 ?? Elf et al. (2003)； 最小化問題 最小ブレーク数が小さい入力 → 計算時間小 特に 「最小ブレーク数＝2n－2 の例」 は 短時間で最適解が求まる （チーム数：2n） → 何らかの特殊構造，多項式時間性?? Elf らの予想： MAX CUT が多項式時間で解ける グラフのクラスと関連？

47 ブレーク数の判定問題 問題 (P) O(n3) アルゴリズムを開発 入力： チーム数 2n のスケジュール
存在しないなら不能． ブレーク数最小化問題の 判定問題version; 目的関数値 2n－2 O(n3) アルゴリズムを開発

48 問題の変換 問題 (P) 入力： チーム数 2n のスケジュール 出力： ブレーク数 2n－2 のＨＡ割当； 存在しないなら不能．
←（変換）→（ブレーク数 2n(2n－2) － (2n－2)） 問題(P’) 出力：ブレーク数 2n(2n－2) － (2n－2) のＨＡ割当；

49 ＨＡ割当の変換 ブレーク数 2n－2 ブレーク数 2n(2n－2)－(2n－2) ① ② ③ ④ ⑤ ① ② ③ ④ ⑤
① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：Ａ Ｈ Ａ Ｈ Ａ １：Ａ Ａ Ａ Ａ Ａ ２：Ｈ Ａ Ｈ Ａ Ｈ ２：Ｈ Ｈ Ｈ Ｈ Ｈ ３：Ｈ Ｈ Ａ Ｈ Ａ ３：Ａ Ａ Ｈ Ｈ Ｈ ４：Ａ Ａ Ｈ Ａ Ｈ ４：Ｈ Ｈ Ａ Ａ Ａ ５：Ａ Ｈ Ａ Ａ Ｈ ５：Ａ Ａ Ａ Ｈ Ｈ ６：Ｈ Ａ Ｈ Ｈ Ａ ６：Ｈ Ｈ Ｈ Ａ Ａ ブレーク 0個のチーム → 全てＡ or 全てＨ ブレーク 1個のチーム → 1回だけＡ→Ｈ or Ｈ→Ａ

50 変換後の問題 ① ② ③ ④ ⑤ １：Ａ Ｈ Ｈ Ｈ Ｈ 問題 (P’)： 左のような ２：Ａ Ａ Ａ Ｈ Ｈ ＨＡ割当が存在？
２：Ａ Ａ Ａ Ｈ Ｈ ＨＡ割当が存在？ ３：Ｈ Ａ Ａ Ａ Ａ 注意：対戦制約 ４：Ｈ Ｈ Ｈ Ｈ Ｈ ← 全てＨ ５：Ａ Ａ Ａ Ａ Ａ ← 全てＡ ６：Ｈ Ｈ Ｈ Ａ Ａ ← 1回だけ替わる 子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i＜j ) チーム i が全てＡ，チーム j が全てＨと固定

51 子問題のＨＡ割当 子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i＜j ) １：４ ２ ５ ３ ６ １：Ａ Ｈ
① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：４ ２ ５ ３ ６ １：Ａ Ｈ ２：６ １ ４ ５ ３ ２： Ａ Ｈ ３：５ ４ ６ １ ２ ３：Ａ Ａ Ａ Ａ Ａ ４：１ ３ ２ ６ ５ ４：Ｈ Ｈ Ｈ Ｈ Ｈ ５：３ ６ １ ２ ４ ５：Ｈ Ａ ６：２ ５ ３ ４ １ ６： Ｈ Ａ 入力 子問題(P34’) 残りのチーム： Ａ…ＡＨ…Ｈ もしくは Ｈ…ＨＡ…Ａ となる，対戦制約を満たすＨＡ割当が存在するか？

52 制約条件の伝播 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：Ａ Ｈ １：Ａ Ｈ Ｈ ２： Ａ Ｈ ２：Ａ Ａ Ａ Ｈ
① ② ③ ④ ⑤ ① ② ③ ④ ⑤ １：Ａ Ｈ １：Ａ Ｈ Ｈ ２： Ａ Ｈ ２：Ａ Ａ Ａ Ｈ ３：Ａ Ａ Ａ Ａ Ａ → ３：Ａ Ａ Ａ Ａ Ａ ４：Ｈ Ｈ Ｈ Ｈ Ｈ ４：Ｈ Ｈ Ｈ Ｈ Ｈ ５：Ｈ Ａ ５：Ｈ Ａ ６： Ｈ Ａ ６：Ｈ Ｈ Ｈ Ａ Ａ 制約条件：Ａ→Ｈ or Ｈ→Ａが 1回，入力に対応 → Ｈを FALSE, Ａを TRUE とすれば， 2SAT として定式化可能．

53 計算複雑度の算定 制約式 2SAT: 変数，2-クローズの個数 O(n2) → 子問題 1個あたり O(n2), 問題(P) は O(n4)
Ａ→Ｈ，Ｈ→Ａ が1回だけ起きる 対戦制約を満たす → 2SAT で定式化可能！ 2SAT: 変数，2-クローズの個数 O(n2) → 子問題 1個あたり O(n2), 問題(P) は O(n4) アルゴリズムの工夫 → O(n3)

54 ブレーク数 2n－2 に対する結果 問題 (P) 入力： チーム数 2n のスケジュール 出力： ブレーク数 2n－2 のＨＡ割当；
存在しないなら不能． O(n3) アルゴリズム ブレーク数 2n－2 の解 → 最小化問題の最適解 Elf たちの予想に対する一つの答え

55 ブレーク数最小化問題を解く [Miyashiro&Matsui 2004]
[Suzuka, Miyashiro, Yoshise, Matsui 2005] [Suzuka, Miyashiro, Yoshise, Matsui 2006］

56 ブレーク数がチーム数以上 与えられたスケジュールが， ブレーク数 2n 以下のＨＡ割当を持たない場合は？
→ 先行研究（分枝限定ベース）では， 計算時間がかかる 最小ブレーク数が大きい問題例 チーム数の大きな問題

57 LP/SDP 緩和を用いたアルゴリズム 線形計画／半正定値計画緩和を用いた 多項式時間確率的アルゴリズム
MAX（MIN) RES CUT として定式化 LP緩和： ランダム化丸め法を適用 SDP緩和：Goemans, Williamson (1995) の 0.878 確率的近似アルゴリズムを適用 極めて高速な，質の良い解の生成を確認

58 MAX RES CUT MAX RES CUT 入力： 無向グラフ G=(V, E), 各枝に対する非負重み
＋ 頂点ペア {vi1, vj1}, …, {vik, vjk} 出力： 頂点ペア{vi1, vj1}, …, {vik, vjk}を分け， 重み最大のカット集合 NP-困難 Goemans, Williamson (1995) による 0.878 確率的近似アルゴリズム

59 ブレーク数最小化問題と MAX RES CUT
① ② ③ ① ② ③ １：２ ４ ３ １ ● ● ● ２：１ ３ ４ ２ ● ● ● ３：４ ２ １ ３ ● ● ● ４：３ １ ２ ４ ● ● ● 頂点集合を「Ａの集合」と「Ｈの集合」に分割 カット＝ブレーク無 A H

60 MAX RES CUT のグラフ チーム数 頂点数 枝数 近似比 計算時間[秒] < ? ?

61 計算実験の結果 チーム数 最適値（IP） SDP緩和 差 近似比率 or or < ― ? ? ― ? ? （超平面分離1000回）

62 計算時間の比較 チーム数 Régin Trick Elf et al 本研究 [秒] （2ヶ月<） (CPU: 900 MHz, SDP Solver: SDPA 6.0, 超平面分離1000回)

63 総移動距離最小化： 各チームの移動距離の総和 チームｋの移動距離： 総移動回数最小化：各ホーム間距離が１の特殊ケース
対戦組合せ表と会場割当が与えられたとき、ｋのホームを出発し、対戦組合せ表と会場割当で規定される順に、対戦会場を訪問し、最後にｋのホームに戻るまでの経路の長さ 総移動回数最小化：各ホーム間距離が１の特殊ケース 総移動回数＝2n(2nー1)－(1/2)(ブレーク数) 総移動距離最小化≒ブレーク最大化

64 計算機実験結果 総移動距離最小化問題：16~40チーム LP緩和：近似比率（1～1.002）, 8秒（40チーム）
SDP緩和：近似比率（1～1.01), 2000秒（40チーム） 分枝限定法（厳密解法）： 秒（40チーム） 総移動回数最小化問題：16~40チーム LP緩和：近似比率（1.1～1.4）, 秒（40チーム） SDP緩和：近似比率（1~1.16）, 2200秒（40チーム） 分枝限定法（厳密解法）： 秒（18チーム）

65 Section 4 HAT→スケジュール

66 スケジュールの作成方法 １ ２ ３ １ ２ ３ １：２ ４ ３ １：２ ４ ３ ① 対戦相手決定
１ ２ ３ １ ２ ３ １：２ ４ ３ １：２ ４ ３ ① 対戦相手決定 ２：１ ３ ４ → ２：１ ３ ４ ② 場所を割当 ３：４ ２ １ ３：４ ２ １ ４：３ １ ２ ４：３ １ ２ 　　 線 １ ２ ３ １ ２ ３ １：Ａ Ｈ Ａ １：２ ４ ３ ① HATを決定 ２：Ｈ Ｈ Ａ → ２：１ ３ ４ ② 対戦相手を割当 ３：Ａ Ａ Ｈ ３：４ ２ １ ４：Ｈ Ａ Ｈ ４：３ １ ２

67 HAT作成 →（チーム割当）→ スケジュール作成
１ ２ ３ １ ２ ３ １ ２ ３ １：Ａ Ｈ Ａ １：２ ４ ３ １：２ ３ ４ ２：Ｈ Ｈ Ａ → ２：１ ３ ４ ２：１ ４ ３ ３：Ａ Ａ Ｈ ３：４ ２ １ ３：４ １ ２ ４：Ｈ Ａ Ｈ ４：３ １ ２，４：３ ２ １ 許容HAT： スケジュールを生成できるHAT cf. 不能HAT

68 HAT 許容性判定問題 HAT 許容性判定問題 Input: HAT （チーム数 2n; 2n－1 スロット）;
Output: 与えられたHATが許容HATか？ 長年の未解決問題 [de Werra 1980, Nemhauser & Trick 1998] 理論的結果ほぼ無し （整数計画法） 計算複雑度は未知 （NP-完全??） 目標： 「許容HATの良い特徴付け」

69 許容HATである必要条件 １ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ｈ Ａ Ｈ １：Ａ Ａ Ｈ Ａ Ｈ
１ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ｈ Ａ Ｈ １：Ａ Ａ Ｈ Ａ Ｈ ２：Ａ Ｈ Ｈ Ａ Ｈ ２：Ａ Ｈ Ｈ Ａ Ｈ ３：Ａ Ｈ Ａ Ａ Ｈ ３：Ａ Ｈ Ａ Ａ Ｈ ４：Ｈ Ｈ Ａ Ｈ Ａ ０ １ １ ０ ０ min{#Ａ, #Ｈ} ５：Ｈ Ａ Ａ Ｈ Ａ ６：Ｈ Ａ Ｈ Ｈ Ａ α({1,2,3}) = ( ) － 3×2/2 = －1 ⇒ 不能 α(T) ＝ ∑s min{#Ａ(T, s), #Ｈ(T, s)} － |T| C 2

70 関数αの定義 許容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

71 許容HATの必要条件 許容HAT の必要条件 Ⓐ： ∀T⊆U, α(T)≧0 HAT 許容性判定における新たな解析手法
22n 本の不等式による表現 HAT 許容性判定における新たな解析手法 → 特殊なクラスの HAT を考え， それらの許容性と条件 Ⓐ の関係を考察 （最小HAT と均等HAT, 十分条件？）

72 許容性判定と条件Ⓐ 一般的に好ましい HAT → これらの HAT の許容性を簡単に判定したい
ブレーク最小HAT (ブレーク数 2n－2), ブレーク均等HAT (ブレーク数 2n) → これらの HAT の許容性を簡単に判定したい 条件Ⓐ 「∀T⊆U, α(T)≧0」 がどのくらい有効か？ → 計算機実験により評価

73 計算実験の結果 26チーム以下の最小HAT，均等HATならば， 「∀T ⊆U,α(T)≧0 ⇔ 許容HAT」
#teams #総数 # Ⓐ #許容 #teams #総数 # Ⓐ #許容 26チーム以下の最小HAT，均等HATならば， 「∀T ⊆U,α(T)≧0 ⇔ 許容HAT」 This table shows results of experiments. THIS column shows the number of teams, the number of PSMB, including both feasible and infeasible, the number of “survived” PSMB, and the number of feasible PSMB. You can see, when the number of teams is less than or equal to 26, the number of “survived” and feasible PSMB are equal !!

74 実験結果のまとめ 提案した条件 Ⓐ は，非常に強い必要条件 ∀T⊆U, α(T)≧0 ⇔ 許容HAT
26チーム以下の最小HAT，均等HATの場合 ∀T⊆U, α(T)≧0 ⇔ 許容HAT 28チーム以上は未実験 （30チームまでは確認 [池辺 2003]） 未解決予想： 任意のチーム数で必要十分条件

75 定理の概要 ∀T⊆U ={1,2,…,2n} に対してα(T) を考えると... 証明した定理
任意のチーム数の最小HAT，均等HATに関して， 「∀T⊆U, α(T) ≧ 0 （条件 Ⓐ ）」 を満たすか否かは O(n4)でチェック可能

76 条件Ⓐに関する定理 定理： （チーム番号を前処理でソート後） 任意の均等HAT （最小HAT）について，
∀T⊆U, α(T) ≧ 不等式 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}, …

77 さらに “良い” 均等HAT を求めるケース有
成果の応用 実用上は，均等HATの中でも さらに “良い” 均等HAT を求めるケース有 許容である スロット 2, 2n－1 のブレークをできるだけ避ける． [Nemhauser&Trick 1998]

78 MIM予想と柏原の反例 [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

79 Section 5 応用と実用

80 Traveling Tournament Problem
(see Trick’s HP) 2重総当り戦 : n で 2n-2 スロット 目的は、総移動距離の最小化　（各チームは、自分のホームから出発し、自分のホームに帰ってくる） どのチームも、3H と 3A は禁止 No repeaters (A 対 Bの直後の B 対 A は禁止) 距離行列は、対称

81 ８チームの問題例（NL8) Feasible Solution: Lower Bound:
41505 (Easton June 4, 1999), 41113 (Easton Jan 27, 2000), 40416 (Cardemil, July ), 39947 (Zhang, August ), 39721 (Easton, August ) Lower Bound: 38760 (Trick Dec 15, 2000), 38870 (Easton Jan 2, 2001), 39479 (Easton Feb 26, 2002)

82 １０チームの問題例（NL10) Feasible Solution: Lower Bound:
68691 (Rottembourg and Laburthe June 2001), 66369 (Dorrepaal, June ), 66037 (Cardemil, July ), 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)

83 １２チームの問題例（NL12) Feasible Solution:
(Rottembourg and Laburthe May 2001), (Larichi, Lapierre, and Laporte July ), (Cardemil, July ), (Dorrepaal July 16, 2002), (Zhang, August ), (Cardemil, November ), (Van Hentenryck January 14, 2003), (Van Hentenryck February 26, 2003), (Van Hentenryck June 26, 2003), (Langford February 16, 2004), (Langford February 27, 2004), (Langford March 12, 2004), (Van Hentenryck May 13, 2004). Lower Bound: (Waalewign August 2001)

84 14チームの問題例（NL14） Feasible Solution: Lower Bound:
(Rottembourg and Laburthe June 2001), (Larichi, Lapierre, Laport July ), (Cardemil, July ), (Zhang, August ), (Cardemil, November ), (Van Hentenryck January 14, 2003), (Van Hentenryck February 26, 2003), (Langford April 22, 2004), (Van Hentenryck May 13, 2004). Lower Bound: (Waalewign August 2001)

85 16チームの問題例（NL16) Feasible Solution: Lower Bound:
(Easton January 2002), (Cardemil, July ), (Zhang August ), (Zhang, August ), (Shen, October ), (Shen, January ) (Van Hentenryck January 14, 2003), (Van Hentenryck February ), 272,902 (Langford, January 16, 2004), 267,194 (Van Hentenryck, June 26, 2003). Lower Bound: (Easton January 2002)

86 総移動回数最小化 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).

87 改訂ポリゴン法(n ≡ 1 (mod 3) の場合) 1 3頂点ごとに向きを反転 n

88 改訂ポリゴン法　　(n ≡ 1 (mod 3) の場合) S S n n 3スロット毎に向きを反転 したポリゴンを利用

89 1重総当たりリーグ戦から2重総当りリーグ戦へ (n ≡ 1 (mod 3) の場合)
AAA HHH AAH HAA AHH HAA AAH HHH AAA HHA AHH HAA AHH HHA

90 n ≡ 0 (mod 3)のとき n ≡ 1 (mod 3)のとき n ≡ 2 (mod 3)のとき
整数計画法を用いた構成法のブレーク数 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 について構成可能であることを 計算機実験により確認.

91 1重総当たりリーグ戦から2重総当りリーグ戦へ
例: n = 22 AAA AAA AAA AAA AAA AAA AAA HHH HHH HHH HHH HHH HHH HHH

92 1重総当たりリーグ戦から2重総当りリーグ戦へ (n ≡ 1 (mod 3) の場合)
AAA AAA AAA AAA AAA AAA AAA HHH HHH HHH HHH HHH HHH HHH

93 1重総当たりリーグ戦から2重総当りリーグ戦へ (n ≡ 1 (mod 3) の場合)
4連続H(A)がない. Xにおいて，全てのチームが， スロット 3i+1 (i ≧ 1)にブレークをもつ． このようなXが存在することを n ≦ 46 について計算機実験により確認.

94 比較(ブレーク数の上界との差) 1 2 ポリゴン (2/3)n – 2 (2/3)(n – 1) (5/3)(n – 2) IP n – 2
1 2 ポリゴン (2/3)n – 2 (2/3)(n – 1) (5/3)(n – 2) IP n – 2 n　(mod 3) 手法

95 実例 実例では？ ３Hと３Aの禁止 各チームのブレークは２回程度

96 1993年のＪリーグ前半戦(ブレーク数） K: H H A A H H A H A A A H A A H A H H 7 V: H A A H A A H A H H A A H H A H A H 5 M: A H A A H A H A H A H H A H A H A H 2 E: A H H A H H A H A A H H A A H A H A 5 J: A H A H A A H A H A H A H H A H A H 2 S: H A H H A A H A H H A A H H A H A A 6 F: H A H A H H A H A H A H A A H A H A 2 G: H A H H A A H H A H A A H H A A H A 6 N: A A H H A H A H A H H A H A H A H A 3 R: A H A A H H A A H A H H A A H H A H 6 2重総当り戦 １０チーム 望ましい

97 2001年のＪリーグ後半戦のスケジュール 磐田 : H A H A H A A H A A H A H H A 3
市原 : H A A H A H A H A A H A H A H 2 名古屋: H A H A A H A H A A H A H H A 3 浦和 : H A H A A H A H A A H A H A H 2 C大阪 : H A H A H A H H A A H A H H A 3 札幌 : A H A H H A H A H H A H A A H 3 福岡 : A H H A H A H A H H A H A H A 2 G大阪 : A H A H A H A A H H A H A A H 3 横浜FM: H A H A H A H A H H A H A H A 1 神戸 : A H A H A H A H A H A H A A H 1 F東京 : H A H A H A H A H A H H A H A 1 東京V : A H A H A H A H A H A A H A H 1 柏 : A H A H H A H A H H A H A H A 2 清水 : A H A H A H H A H H A H A A H 3 鹿島 : H A H A H A H A H A H A H H A 1 広島 : A H A H A H A H A A H A H A H 1 16チーム 読み方

98 2001年のＪリーグ前半戦のスケジュール 磐田 : H A H A H H A H A H A H A H A 1
市原 : A H H A H A H H A H A H A H H 3 名古屋: H A H A H A H H A H A H A H A 1 浦和 : A H H A H A H H A H A H A A A 4 C大阪 : H A H A A H A H A H A H A H A 1 札幌 : A H A H A H A A H A H A H A H 1 福岡 : H A A H A H A A H A H A H H A 3 G大阪 : A H A H H A H A H A H A H A H 1 横浜FM: H A A H A H A H A A H A H H A 3 神戸 : A H H A H A H A H A H A H A H 1 F東京 : H A A H A H A H A H A A H H A 3 東京V : A H H A H A H A H A H H A A H 3 柏 : H A A H A H A A H A H A H A H 2 清水 : A H A H A A H A H A H A H A H 1 鹿島 : H A A H A H A H A H A H A H A 1 広島 : A H H A H A H A H H A H A A H 3 16チーム 読み方

99 セリエＡ2000/2001シーズン（２重総当たり戦） Atalanta : HAAHAHAHAHAHHAHAH AHHAHAHAHAHAAHAHA Bari : HAHAHHAHAHAHAAHAH AHAHAAHAHAHAHHAHA Bologna : AHAHAHHAHAHAHAHAH HAHAHAAHAHAHAHAHA Brescia : AHHAHAHAAHAHAHAHA HAAHAHAHHAHAHAHAH Fiorentina: AHAHHAHAAHAHAHAHA HAHAAHAHHAHAHAHAH Inter : AHAHAHHAHAHAAHAHA HAHAHAAHAHAHHAHAH Juventus : AHAHAHAHAHAAHHAHA HAHAHAHAHAHHAAHAH Lazio : AHAHHAHAHAHAHAHAH HAHAAHAHAHAHAHAHA Lecce : AHAHAAHAHAHAHHAHA HAHAHHAHAHAHAAHAH Milan : HAHAHAAHAHAHHAHAH AHAHAHHAHAHAAHAHA Napoli : HAHAHAHAHAHHAAHAH AHAHAHAHAHAAHHAHA Parma : HAAHAHAHHAHAHAHAH AHHAHAHAAHAHAHAHA Perugia : HAHAAHAHHAHAHAHAH AHAHHAHAAHAHAHAHA Reggina : HAHAHAAHAHAHAHAHA AHAHAHHAHAHAHAHAH Roma : HAHAAHAHAHAHAHAHA AHAHHAHAHAHAHAHAH Udinese : HAHAHAHAHAHHAHAHA AHAHAHAHAHAAHAHAH Verona : AHHAHAHAHAHAAHAHA HAAHAHAHAHAHHAHAH Vicenza : AHHAHAHAHAHAAHAHA HAAHAHAHAHAHHAHAH

100 セリエＡ2000/2001シーズン（２重総当たり戦） Atalanta : HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA Bari : HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA Bologna : AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA Brescia : AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH Fiorentina: AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH Inter : AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH Juventus : AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH Lazio : AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA Lecce : AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH Milan : HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA Napoli : HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA Parma : HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA Perugia : HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA Reggina : HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH Roma : HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH Udinese : HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH Verona : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH Vicenza : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH

101 セリエＡ2000/2001シーズン（ホームゲーム） Atalanta : H H H H H HH H H HH H H H H H H 2
Bari : H H HH H H H H H H H H H H HH H 2 Bologna : H H HH H H H H HH H H H H H H H 2 Brescia : HH H H H H H H H H H HH H H H H 2 Fiorentina: H HH H H H H H H H H HH H H H H 2 Inter : H H HH H H H H H H H H H HH H H 2 Juventus : H H H H H HH H H H H H H HH H H 2 Lazio : H HH H H H H H HH H H H H H H H 2 Lecce : H H H H H HH H H H HH H H H H H 2 Milan : H H H H H HH H H H H HH H H H H 2 Napoli : H H H H H HH H H H H H H H HH H 2 Parma : H H H HH H H H H HH H H H H H H 2 Perugia : H H H HH H H H H H HH H H H H H 2 Reggina : H H H H H H H H H H HH H H H H H 1 Roma : H H H H H H H H H HH H H H H H H 1 Udinese : H H H H H HH H H H H H H H H H H 1 Verona : HH H H H H H H H H H H H HH H H 2 Vicenza : HH H H H H H H H H H H H HH H H 2

102 セリエＡ2000/2001シーズン（アウェイゲーム） Atalanta : AA A A A A A A A A A A A AA A A 2 Bari : A A A A A AA A A A AA A A A A A 2 Bologna : A A A A A A A A A A AA A A A A A 1 Brescia : A A A AA A A A A AA A A A A A A 2 Fiorentina: A A A AA A A A A A AA A A A A A 2 Inter : A A A A A AA A A A A AA A A A A 2 Juventus : A A A A A AA A A A A A A A AA A 2 Lazio : A A A A A A A A A AA A A A A A A 1 Lecce : A A AA A A A A A A A A A A AA A 2 Milan : A A AA A A A A A A A A A AA A A 2 Napoli : A A A A A AA A A A A A A AA A A 2 Parma : AA A A A A A A A A A AA A A A A 2 Perugia : A AA A A A A A A A A AA A A A A 2 Reggina : A A AA A A A A AA A A A A A A A 2 Roma : A AA A A A A A AA A A A A A A A 2 Udinese : A A A A A A A AA A A A A AA A A 2 Verona : A A A A A AA A A AA A A A A A A 2 Vicenza : A A A A A AA A A AA A A A A A A 2

103 セリエＡ2000/2001シーズン （ブレーク数） ２重総当り戦
Atalanta : HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA 4 Bari : HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA 4 Bologna : AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA 3 Brescia : AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH 4 Fiorentina: AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH 4 Inter : AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH 4 Juventus : AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH 4 Lazio : AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA 3 Lecce : AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH 4 Milan : HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA 4 Napoli : HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA 4 Parma : HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA 4 Perugia : HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA 4 Reggina : HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH 3 Roma : HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH 3 Udinese : HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH 3 Verona : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH 4 Vicenza : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH 4 ２重総当り戦

104 課題 各チームのブレーク２回の（スケジュール＋HAT）の特徴付け． ２重総当り戦での，ブレーク数最小化 ３Hと３Aの禁止 移動距離
観客動員数予想

105 おわり

106