自己組織化マップの応用１-序章-

自己組織化マップを利用した巡回セールスマン問題の準最適解を導く-序章-

今回のキーワード
「巡回セールスマン問題」
「自己組織化マップ(ＳＯＭ)」
「準最適解」

今回は序章として，問題定義と解決方法並びにＳＯＭについてを記す．
結果等は次回の投稿にて行います．

まず，巡回セールスマン問題とはなにかから入ります．
巡回セールスマン問題とは，別名が多くありますが，要するに目的地を最短で回るためのルートはどのルートか導くことです．
最近の話でいうと，Google DevQuizの第３問あたりであったかと思います．
あの問題では，距離が問題なのではなく，移動時間に焦点を当てていました．

本題に戻ると，巡回ルートは都市（以降データ点とする）が多くなれば指数的にルートが増えていきます．
数学的知識を使えば，巡回ルートは減らすことができますが，それでも指数的に増えることには変わりありません．
では，どうやって解けばいいか．
コンピュータを使って，解かせるのが一番早いでしょう．
今回私が用いるのは「自己組織化マップ（以降ＳＯＭ）」です．
ＳＯＭの一般的な使用法は，高次元のベクトルを二次元に射影することで可視化などを促すことが，多いかと思います．
この射影することができる点を利用し，巡回セールスマン問題の準最適解を導きます．
具体的にはマップではなく，１次元にして利用するので，「自己組織化リング」とでもいいましょうか．
準最適解しか導くことができないのは，学習系のアルゴリズムであるため，精密な距離計算を行わないことから
必然的に最適解に近い結果しか導くことができないからです．
しかし，データ点が増えても短時間でルートを算出できる点や，膨大な時間や複雑なアルゴリズムが不要である点など，
多くの利点があります．
（まぁ，ほんとのことを言えば，最近ＳＯＭばっかり使ってるので，ほかのことにも応用させたいと思っているだけなんですけどね）

早いですけど，今回は問題定義だけ行い，グラフィック化させるシステムができれば，解答編を描きたいと思います．

まとめ
今回の目的：巡回セールスマン問題をＳＯＭを利用して解く（データ点に関しては，乱数なり実際の都市なりを利用）
自己組織化写像wikipedia
巡回セールスマン問題