##vortex.py ###渦巻きのように進んで行くアルゴリズム。

都市の配置から四隅を見つけてその四隅を繋いで４角形を作った時にその４角形の内側か外側かで都市を分ける。

まず、四隅＋その四角形の外側の都市を一方通行で巡る。

その中で一番遠い２都市の間の経路を切り、その片方の都市から一番近い４角形の内側にある都市に行く。

次に、４角形の内側にあった都市の中で４隅を見つけ同じ作業を繰り返す。

＊プログラムにはまだ少しバグがあって完全には思うように動いていない。

###結果 距離の点においては、全然ダメ。まぁ、当然と言えば当然、、、、、。ただ、実行速度は結構早い。そして、ヴィジュアル化してみると、とても可愛い動きをする。なんどでも、みたくなっちゃう（笑）

##greedy.py ###貪欲法 まだ訪れてない中で一番近い都市にいくっていうやつ。

###結果 うん、まぁまぁ。でも、これだけの処理でこれだけまぁまぁな結果を出せるのはすごいね。うん。

##tsp_greedy.cpp ###貪欲法C++バージョン pythonよりごちゃっとしてしまった気がする。オブジェクト指向とか完全に無視したC++という名のCのコードみたいなとこある

##traveling-salesmanレポジトリ ###近似度 1.5 のアルゴリズム(クリストフィードのアルゴリズム Christofides algorithm N. Christofides) これはhttps://github.com/beckysag/traveling-salesmanをcloneして今回の入出力に合うように調整した。

###結果 よい。アルゴリズム理解して実装力あげて自分でささっとかけるようになろう。

##opt_2.py, or_opt.py, optimize.py http://www.geocities.jp/m_hiroi/light/pyalgo64.htmlを参考にして、今回の入出力に合うように調節した。

###結果 強い。

##combine.py 上のoptimize.pyが強いことが分かったので、他の方法でだしたパスを入力として受け取って、そこからoptimizeを実行するようにした。

##devide.py ###分割統治法 これは、http://www.geocities.jp/m_hiroi/light/pyalgo63.htmlを参考にした。出力が今回の形に変更しきれていない。

##kruskal.py ###クラスカルのアルゴリズムの変形版 http://www.geocities.jp/m_hiroi/light/pyalgo62.htmlを参考にした。

##my_random.py ###ランダム 言わずと知れたランダム解。

##make_set.py ###遺伝子の組を作るためのプログラム 好きな方法でといた結果をまとめて出力するプログラム。これの出力を以下の遺伝的アルゴリズムに読み込ませれば、それを最初の遺伝子として、GAしてくれる。

##TSP.cpp, TSP.h, main.cpp ###遺伝的アルゴリズム これは、https://bitbucket.org/knordkvist/tsp-ga/src/ea466fc00a7c?at=masterを参考にした。このサンプルは都市の数を固定長としていて、データを配列で持っているので、まずそこをベクターに変更した。普通にベクターにしちゃうと、コピーがめちゃくちゃ行われてヤバwな感じになっちゃうので、ベクターのポインタを渡すようにしている。うっかり、ローカル変数のアドレスをpush_backしちゃったりして、不正アクセスしまくった。valgrind, lldbさんには大変お世話になった。

それから、最初の遺伝子の組を外から受け取れるように変更した。これで、上記の方法で解いたエリート遺伝子たちと、ランダムで解いた遺伝子と、あとはうまいこと突然変異して、面白い解が得られることを期待したけど、人生そんなに甘くなかった。

##まとめ 最終的に、あらゆる方法で解いた解を遺伝的アルゴリズムに突っ込んで解いたが、結果はoptimize.pyやChristofides algorithmで解いた結果からよくならなかった。それがGAの現実かもしれないけど、かなしい。ちなみに、GAの計算量は都市の数の３乗に比例しているので、そこは改善の余地あり。