2006年11月29日
日程クンのアルゴリズム
気がついたら一ヶ月以上更新してないのかぁ…。時の流れはなんと速い。
なにはともあれ，スポーツナビ | ニュース | カズ 来季Ｊ１開幕は横浜ダービー!?より。注目すべきは以下の部分。
Ｊリーグの対戦日程はコンピューターソフトの「Ｊリーグマッチスケジューラー」（愛称・日程クン）に、各クラブの要望（スタジアム使用の可否）や同一地域での試合が重複しないなど、さまざまな条件をインプットし、対戦カードが決定される。
今季のＪ１は１２月２日で全日程が終了。そこから入れ替え戦でどちらが勝ってもいいように、２パターンの日程を作る。条件が複雑すぎると“日程クン”は約９０時間もの稼働の末に「答えはありません」の無情な回答を出すこともあるという。
０４年から約２０００万円をかけて導入された“日程クン”は、昨季は優勝を争う５チームの直接対決がないドラマを生み、今季は浦和対Ｇ大阪の最後の大一番を演出した。
日程は人手で決まってるわけだし，J1だと18チーム34試合で90時間も稼働させないと答えが出ないような複雑な問題に見えないんだけど…。全ての条件を総当たりでやってるのかな？ ちゅーか，人手で行う条件付けが一番大変そう…。
とはいえ，最良の組み合わせを人が考えるのには限界があるわけで，システムを作ること自体は楽しそう。
投稿者 たけ＠ねくさす : 2006年11月29日 12:08
トラックバック
このエントリーのトラックバックURL:
* 本エントリと関連しない記事へのトラックバックはご遠慮下さい。
* Trackbacks not to relate to this entry are NOT permitted.
* 本エントリに関連しないコメントは内容の如何に関わらず掲載いたしません。
* Comments not to relate to this entry are NOT permitted even if those are not a spam.
もっと複雑なチェスや将棋、オセロのことを考えると、90時間は痛いねぇ。
昔、小学校の時間割を作成するプログラムを作るって話を考えてみたことがあったけど、これは制約最適化問題に属しますね。「答えはありません」なんて言うところを見ると、制約充足問題なのかな？
ともかく、CSPのプログラムをどっかから落としてきて、条件を入力する部分をGUIで提供すれば、もっとましなシステムになるような気がする。
あぅ，こんな難解なコメントがつくとはw
Jリーグの場合は試合会場が使えるかどうか，同地域で2試合以上ないかどうか，ホームがずっと続いたりしないかどうか，同じチームと対戦が続かないかどうか，などなど条件は大量にあります。半分以上は商業的な条件でしょう。
いずれにしても，2000万もかけるほどのことがあるのかどうか。
（素性はばれてると思いますが、まあいいとして）
実は条件が多い方が効率的に解を出せますし、解がない場合の判断もやりやすいです。
難しいのは、解がない場合に、条件を緩めて次善の解を提案する処理なんですが、（これを制約最適化といいます）それはやってないので、条件が多いからシステムが高くつくということにはならないと思いますね。
条件が多い分、解空間を効率的に絞り込むための難しいロジックを考えなくて済む訳ですから。。。
2000万ねぇ。ちゃんとしたシステムなら妥当と思いますよ。
ゴメン。本音を書きます。
2000万なら、1分以内に、次善の候補も含めて解を出すくらいのシステムにしてほしかった。
(こんなコメントをいただける人は日本広しといえども限られておりますが，まあいいとして)
なるほど。
おそらく日程クンは条件が増えるたびに条件分岐が増えているだけなんでしょう。それを延々ループを繰り返すので，90時間もかかる，と。最適化問題に造詣が深い人がそこらのベンダーにいるとは思えないので，こんなので納得するんでしょうね。
# 解がないのに90時間も動き続けるのがその証拠。枝切りもしないのか？
不幸中の幸い(？)なのは，年に1回しか(J2も使ってるなら2回しか)使われないことでしょう。
そうか、年に1回ねえ。
そりゃもったいないですね。
イベント的なもんなんだから、公募すりゃよかったのにね。
たぶん、頭のいい学生が1週間くらいで作ってしまいますよ。話題性も出るし、工学部も活気付くかもしれないです。予算も20分の1くらいになるかなあ。
JFAは青少年の育成を掲げているものの，さすがにここまで気が利かないでしょう。俗に言う「健康な肉体に…」という思想が背景にあると思いますので。
もっとも，実際に公募するとなると，サポーターに見せたくない商業的側面を赤裸々に示さなくてはならないので，微妙です。