n 都市の巡回セールスマン問題を、出発都市を固定してすべての巡回路を列挙して解くとき、調べる巡回路の数のオーダーとして適切なものはどれか。

解説

正解は「$O(n!)$」です。出発都市を固定すると、残りの n−1 都市を訪れる順番は $(n-1)!$ 通りあり、それぞれの巡回路の長さを求めて比較する必要があります。$(n-1)!$ は $O(n!)$ に含まれ、n=20 でも約 $1.2\times 10^{17}$ 通りとなり、現実的な時間では解けません。「$O(2^n)$」は、n 個の要素それぞれを選ぶか選ばないかを全列挙する、部分和問題や0-1ナップサック問題の場合で、巡回路の列挙より増加が緩やかです。「$O(n^2)$」と「$O(n\log n)$」は多項式時間で、巡回セールスマン問題の最適解を常に多項式時間で求めるアルゴリズムは知られていません。