上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
こないだ最適化問題を解くことがうちの研究室でやっていることっていったけど、正しくは最適化問題を解くためのアルゴリズムの構築です。5次元くらいまでなら手作業でも解けるけど、100次元とかだったら絶対に無理なのでコンピュータに問題を解いてもらいます。そのとき、どうすればより速く答えを出せるかというのが課題になるわけ。このときの計算方法のことをアルゴリズムというんだけれど、わかりにくいので前回の餃子の例で。

いま c = 300 と仮定すると、制約を満たす x , y の組み合わせは( 0 , 15 ) , ( 2 , 12 ) , ( 4 , 9 ) , ( 6 , 6 ) , ( 8 , 3 ) , ( 10 , 0 )と6通り。その中で x + y を最小にする組み合わせは( 10 , 0 )であることがわかります。でも、このようにすべての組み合わせを列挙する方法は、 c が大きくなるほど手間がかかります。
ちょっと違う角度からこの問題を見ると、最適解においては y は { 0 , 1 , 2 }の中から唯一決まることは明らかです。つまり、y = 0 , 1 , 2 のときに制約を満たす x が存在すればそれが最適解であるのです。前者では c = 200でも6回計算が必要なのに対し、後者は c がどんな数であろうと3回以内で問題が解ける!このように計算の手間をできるだけ省いたアルゴリズムを考えていくのです。

昨日うちの研究室のDrの発表を聞きにいった。研究内容はスポーツスケジューリングで、スポーツのリーグ戦の日程と会場(あるチームが、いつ、どこで、どこと対戦するのか)を最適化問題を使って決めようという研究。既存のアルゴリズムでは6チームの2重総当りで94時間かかった計算が、今回のアルゴリズムをつかうと40チームの2重総当りでも10秒で答えが出るとのこと。こういう問題は、チーム数が倍になると、数千倍とか時間がかかるものなのだけど、これはすごすぎる。。
発表が終わった後いつもどおりゼミをやり、その後食事に誘われて楼蘭へ。つくば三井ビルの19F、はじめていったけど何が何だかわからないままでした。たぶん2度と行くことはないです。
スポンサーサイト
Secret

TrackBackURL
→http://misby2tetsuya.blog14.fc2.com/tb.php/83-7332450e
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。