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

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

1 高速フーリエ変換 (fast Fourier transform). 2 高速フーリエ変換とは? – 簡単に言うとフーリエ変換を効率よく計算 する方法 – アルゴリズムの設計技法は分割統治法に基 づいている 今回の目的は? – 多項式の積を求める問題を取り上げ、高速 フーリエ変換のアルゴリズムを用いた解法.
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
スポーツスケジューリング問題 1993年Jリーグの再スケジューリング ver. 6.0
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
スポーツスケジューリング Jリーグはアウェイゲーム連続が多く, 3連続アウェイゲームもある, 質の悪いスケジュールとなっています.
第八回  シンプレックス表の経済的解釈 山梨大学.
ML 演習 第 8 回 2007/07/17 飯塚 大輔, 後藤 哲志, 前田 俊行
C言語 配列 2016年 吉田研究室.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
Scalable Collaborative Filtering Using Cluster-based Smoothing
On the Enumeration of Colored Trees
ファーストイヤー・セミナーⅡ 第8回 データの入力.
配列(2) 第10回[平成15年6月26日(木)]:PN03-10.ppt 今日の内容 1 素数を求める(教科書の例):復習
5個の数字0,1,2,3,4から異なる3個を選んで3桁の整数を作る。
Princess, a Strategiest
最適化ソルバーのための Python言語入門
4. 順序回路 五島 正裕.
C言語 配列 2016年 吉田研究室.
A班 ランダム選択に一言加えたら・・・ 成田幸弘 橋本剛 嶌村都.
整数計画法を用いた ペグソリティアの解法 ver. 2.1
 Combinations(2)        古川 勇輔.
マイクロシミュレーションにおける 可変属性セル問題と解法
第 七 回 双対問題とその解法 山梨大学.
問題 1 キーボードから入力した数の合計を計算するプログラムを 作成せよ。最初に、何個の数を入力するかその数を入力 するようにする。
ベイジアンネットワーク概説 3.6 構造の探索アルゴリズム
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
Linear Relaxation for Hub Network Design Problems
情報処理3 第5回目講義         担当 鶴貝 達政 11/8/2018.
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
7.4 Two General Settings D3 杉原堅也.
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
第2日目第1時限の学習目標 順列、組み合わせ、確率の入門的知識を学ぶ。 (1)順列とは? (2)組み合わせとは? (3)確率とは?
情報セキュリティ  第8回 RSA暗号.
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
スポーツの最適化 優勝決定可能性問題 スポーツスケジュール問題.
情報基礎Ⅱ (第5回) 月曜4限 担当:北川 晃.
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
1~15までの数字の中から、 1個の数字を選び、覚えて下さい。
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
第4章 識別部の設計 4-5 識別部の最適化 発表日:2003年5月16日 発表者:時田 陽一
日程 :2月10日(土)~11日(日) 会場:兵庫県立丹波年輪の里 丹波市立北小学校
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
15.cons と種々のデータ構造.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
ORの手法ゲームの理論3 (Excelによるゲーム理論実習)
プログラミングⅡ 第2回.
アルゴリズムとデータ構造 2012年7月2日
復習 breakとcontinueの違い int i; for (i = 1; i <= 100; i++) { ・・・処理1・・・・
復習 Cにおけるループからの脱出と制御 break ループを強制終了する.if文と組み合わせて利用するのが一般的. continue
数値解析ⅡーI ~オセロゲームのプログラム~
人工知能特論II 第8回 二宮 崇.
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2013年7月2日
復習 breakとcontinueの違い int i; for (i = 1; i <= 100; i++) { ・・・処理1・・・・
分枝カット法に基づいた線形符号の復号法に関する一考察
4.プッシュダウンオートマトンと 文脈自由文法の等価性
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
プログラミング基礎演習 第4回.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
プログラミング演習I 補講用課題
アルゴリズム ~すべてのプログラムの基礎~.
Presentation transcript:

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

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

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

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

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

slotとB(1日休日) チーム数(n)が偶数 slotの数と1つのチームが行う試合数が等しい 1 2 3 n n-1 B slot=n 奇数 偶数

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

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個 ・・ ・・・

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

「あまり好ましくない」状態を値にする 試合日程 状態 悪さ 全ての日程内の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

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 ・・・

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

整数計画法による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/2 for all k∈T      <Patternの数> Σ{i Є P} X i = n for all i ∈ P

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

整数計画法によるTime Tableの生成 X i j k :slot k でPattern i がPattern j と試合をする とき1、それ以外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

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

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

実験結果 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時間)

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

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

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