update: 9/10/2017

これは配達のアルバイトをしていた時に、最も速く周れる経路を考えていたということの、その調査とまとめです。
巡回セールスマンの問題を聞いたことはありましたが、実際にはどうなのかということです。
つまり、最短の時間で全ての配達先に行くのであり、同じ道を折り返したり、同じ訪問先を再度
通過しても良いのですが、インターネット上で少しだけ調べたところ、次の様なものが近い考え方と思われました。



�@　一筆書き  

　　図のような場合、奇数の分岐が２個か、全て偶数分岐ならＯＫだそうです。

    

　　工業的には、アーク放射の形状切断など、途中停止のできないものなどは
　　応用可能らしいです。つまり往復の２車線のような動きも可です。



�A　ケーニヒスベルグの橋

    

　　これは見たことがありますが、現在はロシア領カリーニングラードだそうです。
　　図のブレーゲル川は舟運のため、新川を開削したということだと思いますが、
　　ブラタモリ流には、防衛上の掘割と見るのが正しそうです。
　　川を越えられないと、全ての橋を１度しか通らないのは無理とわかります。

    グラフ理論に関連するブログ  



�B 巡回セールスマン

　　スーツを着たサラリーマンが得意先を周るというイメージが面白いのですが、
   複数の訪問先を1回ずつ通過して、スタート点に戻るという話で、
   総当たりで考えると計算量が多いのでというＮＰ問題に工夫の余地があります。
　 最近のコンピューターは計算速度が速いので、人間が経路をブロック化したりする方が
　 重要かもしれません。

   研究例（神大）



�C 最適経路

   �Bと重なりますが、実際のように、経路は限定的で、各径路で掛かる時間が異なるような状態です。
   始点と終点が一致しなくても良いようです
　　
　a) ワーシャル・フロイド法　総当たり法
  b) ダイクストラ法　経路を延ばしていって、未確認の経路の方が短い距離になる可能性が出てきた時に、
　　　　　　　　　　 そちらの経路も延ばしてみるという方法。   情報系の用語集より（津田女）

  c) ベルマン・フォード法　負の方向も含めて、全ての辺に対して最短距離の経路を判定する


（まとめ）

　  実際には、前任者の作成した経路があるのですが、実情に合わせて、
　　２つの点について、あれこれと試行錯誤したと思います。

(A) ゆるやかな円を描くようにする。

　　彗星のように円弧を掃いていくのが、自然の摂理と思われます。
　　町が駅を中心に同心円状に広がっているということもあります。

(B) これは、別の変数による制約条件になるのでしょうが、
　　大口の配達先に最初に行き、身軽になることです。また、最初に
　　歩いて円の中心部を配達し、後にバイクで円を描くといった考え方です。

　　特に(A)について、同心円状に配置された２つの正多角形の頂点を周る場合、
　　小さい方の半径がある程度小さければ、大小２つの円を描く方がよく、
　　そうでなければ、歯車状に周る方が良いという計算ができます。（冒頭の図参照）
　　(B)の要素もあり、人口密集地の駅周辺にまず行くという経験則への適合は、
　　こんな程度です。

経験則を英語で rule of thumb と言いますが、繰り返す内に、
近似解の精度が良くなっていくということだと思います。
古来、先人曰く、「これを知るは之を行なうに若かず」（荀子）  
また、「天才は1%のひらめきと99%の汗」（エジソン）
こういう偉い人たちも、ついつい怠けてしまうところを反省したんだニャ。



 
  調査レポート作成 :tmlbworks