ある地域の営業担当のセールスマンが、その地域に住んでいる顧客全員の家を巡回して訪ねることになったとしよう。巡回の順番によって総移動距離（すなわち総移動時間）が大きく変わるので、当然総移動距離が少なくなるような巡回の方法を求めたい。これを求める問題が巡回セールスマン問題である。コンピューターで速く解くのがむずかしい計算量爆発問題の典型として有名である。ある総移動距離以下の巡回方法があるかないかを求める問題はNP完全問題であることが知られている。

図「巡回セールスマン問題」