NP-Hard - Npikonn

…If we consider the state of the network corresponding to each minimum value as a recall pattern, it becomes a model of autoassociative memory. Furthermore, Hopfield et al. applied this model to the computationally NP-hard traveling salesman problem, suggesting its effectiveness as a heuristic method for solving combinatorial optimization problems. In combinatorial optimization problems, it is necessary to avoid convergence to local optima such as points A and B in Figure 2 and obtain a global optimum like C or a good approximation thereof. …

*Some of the terminology explanations that mention "NP-hard" are listed below.

Source | Heibonsha World Encyclopedia 2nd Edition | Information

…各極小値に対応するネットワークの状態を想起パターンと考えれば，自己想起型連想記憶のモデルとなる。さらにホップフィールドらは，このモデルを計算論的にNP-困難な巡回セールスマン問題に適用し，組合せ最適化問題のヒューリスティック解法として有効性を示唆した。組合せ最適化問題においては，図2の点A，Bのような局所最適解への収束を避けてCのような大局最適解もしくはそのよい近似解を得ることが求められる。…

※「NP-困難」について言及している用語解説の一部を掲載しています。

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