昨日の秘書問題には最適解がありましたが、最適解がまだ見つかっていない問題もたくさんあります。有名なもののひとつが「巡回セールスマン問題」です。最初に考えたハミルトンは四元数や行列の定理で有名なアイルランドの数学者です。色々なことをやっていますね。
https://www.msi.co.jp/solution/nuopt/docs/designs/articles/traveling-salesman-problem.html
AIによる概要「与えられた複数の都市をすべて一度ずつ巡り、出発地に戻る際の最短経路を求める問題です。この問題は、組合せ最適化問題の中でも特に有名で、物流、配送ルートの最適化、ネットワーク設計など、様々な分野で応用されています」だそうです。
与えられた都市間の距離の一覧から最短経路を求める方法を探す際、出来るだけ最短に近いものを探すか、計算時間を短くするかの兼ね合いです。計算量の議論につながります。すなわち、都市がn個ある時に”単純な計算機”を使って、nが増えたときにnの多項式で増える時間で解けるかどうか(P)、”探索できる計算機”を使ってnの多項式で増える時間で解けるかどうか(NP)、それができないか(NP困難）など、頭が痛くなりそうな未解決領域があります。解説としては下記が簡潔でわかりやすいです。
現実問題としてはセールスマンは巡回しなければ仕事にならないので、良さそうな経路を探すアルゴリズムがいろいろあります。面白そうなのを２つ紹介します。
１つは2-opt法で、短くなる場合に２つの都市を結ぶ経路を交換するアルゴリズムです。これは長さの変化の計算がnによらず短時間で終わることを利用します。決めた回数繰り返して答とするのだと思います。これは局所的にしか見ない方法と言えるでしょう。
https://ja.wikipedia.org/wiki/2-opt
もう一つは焼きなまし法(Simulated annealing)です。
現在の経路から２都市を交換した経路を作り、比べてみて短くなっていれば採用、長くなっていても「ある長さ」までならば許容し採用、そうでなければ変更を却下、というのを繰り返します。許容される増加分は最初は大きい値にして、だんだん小さくしていきます。その様子が金属の焼きなましに似ているというのでこの名前があります。長くなっていても許容される場合があるため、局所的な最適値（極小点）で止まってしまうのを防ぐことができます。
https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95
焼きなまし法は、一種の量子コンピュータで高速に行えることが分かったのでカナダ-米国のベンチャーD-wave社が活動しています。来週細かく見てみましょうか。
英語は https://en.wikipedia.org/wiki/Travelling_salesman_problem から。
”In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.”
Given a list of… ～が与えられたとき (if you are given a list of …)
combinatorial optimization 組み合わせ最適化
”Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%.”
heuristics ヒューリスティックス 発見的手法、経験則による方法
a small fraction of 1% 1%の小さい一部で； 1%よりもずっと小さ（時間）で
”The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. ”
logistics 兵站（へいたん）、補給
manufacture of microchips マイクロチップの製造 （配線が短くなるように)