文献

J-GLOBAL ID：201602018256400204   整理番号：73A0347766

巡回セールスマン問題に対する有効な発見的アルゴリズム

An effective heuristic algorithm for the traveling-salesman problem.

著者 (2件)： LIN S ,  KERNIGHAN B W
資料名： Oper Res  (Operations Research)
巻： 21  号： 2  ページ： 498-516  発行年： 1973年 
JST資料番号： D0249A  ISSN： 0030-364X  CODEN： OPREA   資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： n都市間の距離(所要時間,費用でもよい)のn×n対称行列が与えられたとき各都市をちょうど1回訪問する最短径路を見出すところの対称な巡回セールスマン問題に対して,最適解およびその近似解をつくり出す有効な発見的方法を,組合せ最適問題で広い応用をもっと考えられる一般的接近法(ランダムに選ばれた実行可能解の集合の繰返し改良法)によって求めている。nと共にラン・タイムは急速に増加するから,従来60以上の都市に関する研究成果はきわめて少ないのでここでは100以上の大型問題を扱かっており,たとえばn=100のとき95%信頼度の最適解を求めるのに約3分を必要とする;写図7表4参12

シソーラス用語： 巡回セールスマン問題 ,  順序づけ問題 ,  信頼度 ,  組合せ ,  発見的方法
準シソーラス用語： 最適解 ,  実行可能解

タイトルに関連する用語 (2件)： 巡回セールスマン問題 ,  発見的アルゴリズム