Approximation method - Kinjikaiho

Japanese: 近似解法 - きんじかいほう
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

Japanese:

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

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

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

<<:  Kinjigahosha

>>:  Near ultraviolet - Kinshigaisen

Recommend

Eshinni - Eshinni

Year of death: Unknown (Year of death unknown) Yea...

Magnetic Particle Inspection

A non-destructive testing method that utilizes the...

Sea (inkstone) - Umi

...In addition to rectangular, square, circular, ...

Mercury chloride - enkasuigin (English spelling) mercury chloride

Compounds of mercury and chlorine. Both monovalen...

Tyneside

…(2) Northeast: This area, east of the Pennines, ...

Cyclopoida

...free-living). Order Cyclopoida (The boundary b...

Karel tribe - Karel

The Uralic language family is a collective term f...

Benue River

…The Niger River originates in the distant mounta...

Trieste - Torieste (English spelling)

The capital of the Friuli-Venezia Giulia region i...

"Ono no Takamura Collection"

...A story. It is also called "Takamura Diar...

Household discount - Kosuwari

A local tax levied on people who own a home or who...

Thor

Also known as Thor. An ancient Germanic god. In Ge...

Michael Kohlhaas

…Ironically, Kleist was finally able to publish h...

Shinshu Tsumugi

A type of silk fabric. It is hand-woven tsumugi pr...

Abeno Doji - Abeno Doji

...Abe no Doji, Seimei's childhood name, mean...