月下美人が咲きました：たまの週末：SSブログ

	ブログをはじめるログイン

Post-K　（スパコン）｜こども自然公園のホタルブログトップ

月下美人が咲きました　[相鉄沿線] [編集]

ベランダに出していた月下美人が、いつもの年より2週間ぐらい早く咲きました。

まるで、土の中から直接咲いてるように見えます。

屋内にも、ひと鉢あるのですが、こちらは蕾もなくて、今年は咲かないようです。残念...

例年、月下美人が咲く頃には、ホタルが舞い出すので、今年は、そろそろかな？

ナナフシ

最近、デジタルアニーラとか量子コンピュータなどの話題の中で、巡回セールスマン問題（traveling salesman problem、TSP）というのが出てくるようなので、Google Optimization Toolsを使って、家のパソコンで実行して見ました。（Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz）

https://developers.google.com/optimization/routing/tsp

上の、ページのサンプルプログラムを
Jupyter notebookで実行

13都市の結果
Total distance: 7293 miles
Route:
New York -> Boston -> Chicago -> Minneapolis -> Denver -> Salt Lake City -> Seattle -> San Francisco -> Los Angeles -> Phoenix -> Houston -> Dallas -> St. Louis -> New York
CPU times: user 4.07 ms, sys: 1 µs, total: 4.07 ms
Wall time: 3.87 ms

6都市の結果
Total distance: 5213 miles

Route:
New York -> Chicago -> Minneapolis -> Denver -> Los Angeles -> Dallas -> New York
CPU times: user 2.33 ms, sys: 0 ns, total: 2.33 ms
Wall time: 2.25 ms

さすがGoogleのツール
13都市で、0.004秒

ついでに、
Microsoft Research が作った、最強のSAT(SATisfiability problem)/SMT(Satisfiability Modulo Theories) ソルバー z3
https://github.com/Z3Prover/z3

を使って、同じように6都市の問題を解いてみました。

CPU times: user 1min 16s, sys: 15.1 ms, total: 1min 16s
Wall time: 1min 16s
Minneapolis (355 miles to the next city) ->
Chicago (713 miles to the next city) ->
New York (1374 miles to the next city) ->
Dallas (1240 miles to the next city) ->
Los Angeles (831 miles to the next city) ->
Denver (700 miles to the next city) ->
distance_total= 5213 miles

z3を使っても、Google Optimaization Toolsの結果とは、スタートの都市と回る順番が逆回りになっているものの、同じ経路が求められました。しかし、計算時間は、30,000倍以上になってしまいました。
期待していたのに、ちょっと残念な結果です。

最強のSAT/SMTソルバーといっても、TSPは苦手のようです。
問題の定義の仕方が悪いのかな？
あるいは、TSPにSAT/SMTを使うことが、良くないのかな？

巡回セールスマン問題は、広く知られた問題なので、いろいろなアルゴリズムが発見され、現在では5万都市でも解けるようです。

Traveling Salesman Problem
http://www.math.uwaterloo.ca/tsp/index.html
US50K
Shortest-possible tour to 49,603 sites from the National Register of Historic Places.
http://www.math.uwaterloo.ca/tsp/us/index.html