tsp.jsは,GoogleMaps API上で巡回セールスマン問題を解くライブラリ
巡回セールスマン問題は,最短経路問題より難しい。
最短経路問題の場合は,重み付きのエッジをもつグラフ上の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