あなたは国連加盟国193ヶ国を1度ずつすべて訪問し出発点に戻ってくるとします。

移動距離が最小になる経路をあたは答えられますか？

人工知能↓

こんにちは、こちらはBingです。😊

あなたの質問は、巡回セールスマン問題と呼ばれる組合せ最適化問題の一種です。この問題は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求めるというものです12。

この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属します。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題です23。

国連加盟国193ヶ国を1度ずつすべて訪問し出発点に戻ってくるとしたら、移動距離が最小になる経路を答えることは、現在の技術では非常に困難です。全ての経路を計算することで最適解を得る手法は時間計算量がO(n! ){\displaystyle O(n!)} であり、都市数が20以上になると現実的でないからです2。

しかし、厳密に最適解を求めることを放棄して計算時間を短くする方法はいくつか存在します。たとえば、近似アルゴリズムやヒューリスティックアルゴリズムと呼ばれる手法です2。これらの手法は、最適解に近い解を多項式時間で求めることができますが、出力される解のコストと最適解のコストとの差を保証することはできません。