Approximation method - Kinjikaiho

... When the transportation network between cities and the travel costs between cities are known, the "traveling salesman problem" of "finding the least expensive route to visit all cities" is extremely difficult, and as the number of cities n increases, an "explosion of calculation time" occurs, and it may not be possible to find the optimal solution within a realistic time frame. Therefore, instead of finding the optimal solution, "approximation solutions" that find an "approximate solution" close to the optimal solution have been researched, and it has been reported that good solutions have been obtained for more than tens of thousands of cities. It has also been proposed to have a neurocomputer solve this problem, but since this is essentially an "approximation solution based on learning," and an "explosion of learning time" occurs as the number of cities increases, only a few dozen cities have been solved, and it is still far from being practical. ...

*Some of the terminology explanations that refer to "approximate solutions" are listed below.

Source | Heibonsha World Encyclopedia 2nd Edition | Information

…　都市の間の交通網と都市間の移動経費がわかっているとき，〈すべての都市を巡回する経費最小の経路を求めよ〉という〈巡回セールスマン問題〉はひじょうにむずかしく，都市数nがふえると〈計算時間の爆発〉が起こり，現実的な時間内には最適解を求められないことがある。そこで最適解を求める代わりに，それに近い〈近似解〉を求める〈近似解法〉が研究され，数万を超える都市についてよい解が得られたとの報告がある。なおこの問題をニューロコンピューターに解かせることも提案されているが，本質的に〈学習に基づく近似解法〉であり，都市数が大きくなると〈学習時間の爆発〉が起こるため数十都市程度しか解かれておらず，まだ実用からはほど遠い。…

※「近似解法」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社世界大百科事典 第２版について | 情報