社会にある問題には、単純そうで実は解くのが難しい問題があります。巡回セールスマン問題は、その中でも有名な例です。

巡回セールスマン問題は、複数の決められた地点をセールスマンが巡回して元に戻る際、どう回れば最も移動距離が少ないか、という問題です。これは例えば、地域の移動手段として増えつつある、乗合タクシーやオンデマンドバスの経路を決める際にも応用できる、実用的な問題です。

単純な解き方は、考えられる全ルートの移動距離を計算し比較する、数え上げの方法です。しかし訪問先の数(n)に対し、（出発点や回る向きの違いは無視した）異なるルートの数は(n-1)の階乗(１から(n-1)までの整数を掛けたもの)÷2で、nが増えると急激に増えます。5地点の巡回ならルートは12(=1×2×3×4÷2)ですが、15地点だとルートは400億以上です。このため訪問先が少ない場合も、単純な数え上げでは事実上解けず、AI等が活用されます。先端技術が身近な問題を解決する一例です。

一方、巡回セールスマン問題はグラフ理論という数学の一分野の問題で、理論的に解き方の簡略化が研究されてもいます。地道な理論研究も、生活を豊かにする大切な要素です。