不適格路除去法による巡回セールスマン問題の解法

スポンサーリンク

概要

論文の詳細を見る
「巡回セールスマン問題」(以下、TSPという)について、最も基本的な解法は、ハミルトン閉路の長さをすべて検証する方法である。この方法の欠点は、頂点の数がnのとき、ハミルトン閉路の数が(n-1)!/2通りあり、ハミルトン閉路の長さをすべて計算するには指数時間を要することにある。最小の長さを持つハミルトン閉路を見つけるのに、実際には、長さを求める必要のないハミルトン閉路が数多く存在する。それらのハミルトン閉路の長さの計算を省くことによって、多項式時間にまで計算量を減らすことは無理としても、より多くの頂点をもつTSPを解くことが出来るようになる。
一般社団法人情報処理学会の論文
1996-03-06

著者

関連論文

スポンサーリンク