日記
日記です。なんかあれば書こうと思いますです…。

イメージ

2006年09月13日(水) 巡回セールスマン問題


高専時代はORの授業でわりとよくやっていたものに巡回セールスマン問題というものがある。これは数ある経路と,ところどころに絶対に立ち寄るポイントを設けて,全部のポイントを通り,かつ一番コストの低い経路をみつけなさいというもの。

例えば,東京都庁をスタート地点として,全国の県庁所在地すべてを一度は必ずとおり,一番安い(もしくは短い)経路をみつけなさいという途方もない問題のこと。

これを解くためには色々と解き方はある。ひとつはGA。遺伝的アルゴリズム。もしくは遺伝的アタックともいう。数ある経路を個体群として,評価関数と乱数による突然変異を用いて,最終的な解をみつけようというもの。これはブームだから手をだしている学者さんがいる。前のところでも2人かぶってたし。今のところでも多分2,3人はこれでかぶっていると思う。評価関数の決め方が重要で,この評価の部分には例えばグリーディー法に準じた関数を使うのがいい。グリーディー法というのは,その地点において一番最適の(最大なり最小なりってことね)解をそれぞれ選んでいくことで全体でも最適になるでしょ,っていういわれてみればそうだと思う関数。これを発明した学者さんって本当にすごいと思う!

でも,GAは今否定されつつある。GAは対象モデルが静止空間じゃないと評価できないといわれている。現在のように,その瞬間で道路事情がかわる(渋滞による交通混雑とか)ようなモデルだと,評価関数を作れないので�世箸いΔ海箸蕕靴ぁ�

これにかわる方法をみつけた人は多分学会賞くらいはもらえる。ほしい人はがんがるんだっ。漏れは致命的なことに別に…そういうのはいいや。学会賞より単位や卒業証書がほしい。そのために勉強がんがる。

ではでは。

 前の日の日記を読む 次の日の日記を読む 目次へ Webページへ