ma38su.org - Traveling Salesman Problem
巡回セールスマン問題（TSP）とは、例えばセールスマンが得意先を一度づつまわって会社へ戻ってくるまでの巡回路を探す問題のことで、得意先がNあるとすると巡回路の組み合わせがN!通り存在するため、得意先の数が増えてくると巡回路の組み合わせはものすごい数になります。なので、最短の巡回路を求めることが非常に難しいです。（当然Nが小さければ求まります。）そんなわけで現在、多項式時間での厳密解法のみつかっていない（多分、存在しない）NP-困難な問題です。多項式時間で求まる厳密解法が存在しなければ、条件を変えないで精度... > このページを見る
はてなブックマーク
