TIM Labs

できるだけ曲がりたくない巡回セールスマン問題

| コメント(0) | トラックバック(0)

標準的な巡回セールスマン問題は、経路長が最短のものを見つけるのであるが、これを変えてみた。

最適化の対象になる関数を適応度関数(fitness function)とか、コスト関数、評価関数とか呼ぶわけだが、このfitness関数を距離ではない次のようなものに変えてみた。

AngleExp.JPG

各頂点で曲がることになるのだが、そのときの回転角度の2乗和を最小にすることにした。

プログラムで変更したのはたったそれだけ。

すると、こんなことになった。500-Angle.pngこれは前のより点数が増えて500点であり、もっとぐるぐる回っているように見える。

つまり、fitness関数は、なにか適当なのをでっちあげて、その関数の値を最適なもの(通常は最小か最大)を指定すると、後は延々と計算して、結果を表示してくれる。

ということで、巡回セールスマン問題だからといって、最短距離に凝り固まる必要はなく、ちょっと頭を柔軟にすると、色々なことを調べるのに使えるのだ。

巡回セールスマン問題は、実はもっともっと汎用性に富んでいるのだが、その話はまた次で。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/748

コメントする

このブログ記事について

このページは、fujiが2018年11月22日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「Azure VM Scale Setsの営業時間外自動シャットダウン」です。

次のブログ記事は「戻ってこない巡回セールスマン問題」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ