巡回セールスマン問題が解けた!

 巡回セールスマン問題が解けた。 円環アルゴリズム。


 そのアルゴリズムを以下に示す。

 

  1. 右回りか左回りかを決める

  2. 一筆書きの問題ととらえる。

  3. 円環を描くように訪問する。

その軌跡が交錯しないように訪問する

その軌跡が描く閉空間の面積が最大になるように訪問する。


この問題はすでに現実社会の中に答えがある。


例 ヨーロッパ5か国周遊の旅。

  東京 山手線 大阪 環状線。

  企業活動におけるルートセールス


解説 

 階乗の計算量爆発により解けそうで解けない問題の代表格として知られるこの問題であるが。私たちの日常では苦も無く解いている問題であることに気づいた。このモバイルの時代にこの問題が放置されることはあり得ない。


巡回セールスマン問題とは

あるセールスマンが自分の会社を出発点として得意先を何件か巡回して最後には自分の会社に戻ってくるとして最も時間のかからないルートをどのように決定すればいいかという問題である。得意先が3軒、4軒、5軒と増えていくとルートの候補も3通り、12通り、60通りと急激に増えていく。


                            2022 藤原憲一




0 件のコメント:

コメントを投稿