So-net無料ブログ作成

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

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







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


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

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






ナナフシ




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

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

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


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都市の問題を解いてみました。
z3_TSP.png

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


nice!(17)  コメント(2) 

nice! 17

コメント 2

U3

夜に咲くものとばかり思っていました。
by U3 (2018-05-27 18:43) 

aoken

U3さんコメントありがとうございます。

コメントいただくまで、気が付きませんでしたが、去年までは、夜咲いていました。

http://aoken.blog.so-net.ne.jp/2017-06-11



by aoken (2018-05-27 19:05) 

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。