読者です 読者をやめる 読者になる 読者になる
スポンサーリンク

tsp.jsは,GoogleMaps API上で巡回セールスマン問題を解くライブラリ

アルゴリズム GoogleMaps

巡回セールスマン問題は,最短経路問題より難しい。


最短経路問題の場合は,重み付きのエッジをもつグラフ上の2点間を最小のコストで移動すればよい。

これは,電車の乗り換え検索で使われるアルゴリズムだ。

具体的には,ダイキストラ法が最速であると知られている。


巡回セールスマン問題(traveling salesman problem、TSP)は,もっとずっと難しい。

指定したすべてのノードを,重複も漏れもないように巡回して戻ってくるのだが,

その際のコストが最小になるようにルートを計画する必要がある。


すべてのノードを通るので,組み合わせの候補はノード数の階乗だけあり,最適化には莫大な計算量がかかる。

事実,この問題の計算量はNP困難(多項式時間では解けそうにもない問題)のクラスだ。

TSPは,組み合わせ最適化問題の中でも花形と言える。


そんなTSPだが,地図の上で実行する必要が生じることも多い。

そして今の時代,地図と言えばGoogle Mapsである。

Google Map上で,javascriptでTSPを解いて視覚化してくれるライブラリが,tsp.jsだ。

その情報を下記に掲載。



巡回セールスマン問題の解法となるアルゴリズムについて:

巡回セールスマン問題 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%B7%A...


最短経路問題 - Wikipedia
http://ja.wikipedia.org/wiki/%E6%9C%8...


巡回セールスマン問題とGA
http://www.studiok-i.net/tsp/index.html


Algorithms with Python / 巡回セールスマン問題
http://www.geocities.jp/m_hiroi/light...


応用例2:巡回セールスマン問題
http://www.cs.ce.nihon-u.ac.jp/~matsu...


ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける | スラッシュドット・ジャパン
http://slashdot.jp/story/10/10/26/085...


Rで巡回セールスマン問題 With TSP(+RGoogleMap) - Analyze IT.
http://d.hatena.ne.jp/EulerDijkstra/2...

tsp.jsを利用する例:

Die schnellste Route durch Oberhessen
http://www.josef-graef.de/karten/tsp/


サンプルコード - Google グループ
https://groups.google.com/forum/#!msg...


extjs+google map+TSP Solver实现最佳路线 - Joe's IT Blog - ITeye技术网站
http://joeze.iteye.com/blog/1921964


tsp.jsを利用するサンプルコード
https://google-maps-tsp-solver.google...


ふつうのGoogle Maps API (ブラウザ上でのJavaScript)の使い方:

Google Maps APIを使う(前編) - 愚鈍人
http://ichitcltk.hustle.ne.jp/gudon/m...


WebTecNote - Google Maps API V3 基本的な使用方法と設定についてのまとめ
http://tenderfeel.xsrv.jp/googlemap/869/


ナビゲーションコントロールの位置を指定する
http://www.openspc2.org/reibun/Google...


発端:

javascript googlemap api についてです 現在、(1)の様にして..
http://q.hatena.ne.jp/1383469301#comment