TSP面接で詰まらない答え方を解説。定義、NP困難性、Held-Karp、近似法の順で整理し、実例と追加質問対策まで分かるのでぜひ読んでください。
多くの候補者が巡回セールスマン問題の面接でうまく答えられないのは、TSPが何かを知らないからではありません。知りすぎているからです。Wikipediaを読み、DPテーブルを見て、いざ面接で質問されると、実際に何を解こうとしているのかを言う前に、すぐにビットマスクの状態空間の話を始めてしまうのです。すると面接官は話の筋を見失い、候補者は場を失います。
この記事では、うまくいく順番で答えを示します。まず平易な定義、それから厳密解と近似解の選択、次にHeld-Karpの解説、最後に追加質問への返し方です。この順番を一度練習すれば、パニックの連鎖は止まります。
まず、賢そうなことを言う前に、TSPが実際に何かを言う
平易な言葉で言うTSPの意味
巡回セールスマン問題とは何か。都市の一覧と都市間の距離が与えられたとき、すべての都市をちょうど1回ずつ訪れて出発点に戻る、最短の経路を見つける問題です。それだけです。1文で言えます。ホワイトボードを見なくても10秒以内で説明できるべきです。
候補者がこれをきれいに言えない理由は、TSPを問題文ではなくグラフ理論の概念として内面化してしまっているからです。概念として内面化すると、まだ何を最適化しているのかを伝える前に、NP困難性や動的計画法、ビットマスクDPといった仕組みに手が伸びます。これは順序が逆です。定義は、本当の答えにたどり着く途中の形式的な通過点ではありません。残りの答えが乗る土台です。
Cormen らのIntroduction to Algorithms* による形式的な扱いでは、TSPはNP困難に分類されます。つまり、すべての入力に対して最適解を多項式時間で求めるアルゴリズムは知られていないということです。この分類は重要ですが、定義の後に来るべきものであって、先に来るものではありません。
なぜ面接官はこれを聞くのか
巡回セールスマン問題の面接は、暗記テストではありません。TSPを出す面接官が見ているのは、もっと具体的な点です。この人は、難しい最適化問題を、解き始める前に明確な前提へ落とし込めるか。制約に応じて、厳密さと実用性のどちらを選ぶかを、見栄えのいいアルゴリズムではなく意図的に選べるか。
コーチングの現場でよく見る失敗は、候補者がDPが何を解くのかを言う前に、いきなり動的計画法に飛びつくことです。「訪問済み都市の部分集合に対するビットマスクDPを使います」と言って面接官が丁寧にうなずいたあと、「でも、実際の問題は何ですか？」と聞かれる。すると候補者は、解の内側から定義を説明し始めることになり、これはずっと難しくなります。定義は先に、落ち着いて、昼食中に同僚に説明するような感覚で言うべきです。その後はずっと整理されます。
実際に口に出せる60秒のTSP回答を持つ
自然に聞こえる暗唱用スクリプト
強いTSPの面接回答には、順番どおりに4つの動きがあります。4つ全部でも90秒以上は要りません。
まず問題を定義します。「TSPは、すべてのノードをちょうど1回ずつ訪れて始点に戻る、最短経路を求める問題です。」一文で十分です。
次に難しさを言います。「難しいのは、都市の数が増えると取りうる経路数が階乗的に増えるので、総当たり探索はすぐに実用的でなくなることです。」
三つ目に、制約に応じて解法を選びます。「入力が小さい、たとえば都市数が20未満なら、Held-Karpによる厳密な動的計画法が使えます。計算量は O(n² 2ⁿ) です。もっと大きい入力なら、近似法かヒューリスティックを使います。たとえば貪欲な最近傍法、あるいは保証付きの境界が必要ならChristofidesのアルゴリズムです。」
四つ目に、次の質問を促します。「DPの方法を詳しく見ますか、それともヒューリスティック側を話したほうがよいですか？」
この最後の一手を省く候補者が最も多いです。厳密解と実用解の両方が正しいことを理解していて、相手に不要な方を延々と聞かせるつもりがない、ということを示せます。Harvard Business Review に掲載された技術面接パフォーマンスに関する研究によれば、構造化されたコミュニケーションと、トレードオフを明示的に枠づける力は、採用担当者がシニア候補とミドル候補を見分ける際の強いシグナルの一つです。
実際にはこう見える
ホワイトボードの前に立っている場面を想像してください。面接官が「巡回セールスマン問題について説明してください」と言います。よくある失敗は、すぐに5つのノードを持つグラフを描いて辺にラベルを付け始めることです。やめましょう。まず定義を口に出し、そのあとでグラフを描くべきです。グラフは定義を示すためのものであって、置き換えるものではありません。
実務では、4つの動きのあるスクリプトを練習している候補者のほうが、場当たりで答える候補者よりも明らかに練習づけされた感じがしません。なぜなら、構造が「次に何を言うか」を考える認知負荷を取り除くからです。ある候補者はTSPの概念理解は優れていたのですが、3つか4つの説明の切り口を行ったり来たりしてから、ようやく1つに落ち着く話し方でした。4つの動きのスクリプトを2回ほど叩き込んだあと、回答は十分に鋭くなり、面接官はすぐに追加質問へ進みました。これはまさに理想的です。深さを示すのは追加質問への応答だからです。
1つの正解があるふりをせず、厳密DPかヒューリスティックかを選ぶ
厳密な動的計画法が適切な場面
Held-Karpが正解になるのは、面接官が厳密さを求めているとき、入力サイズが小さいとき、あるいは問題が授業レベルの演習として出されているときです。この手法は厳密、つまり最適経路を見つけます。学術的・面接的な文脈でTSPに対する標準的なDPです。状態は、どの都市を訪問済みかと、現在の経路の終点がどこかを表し、遷移によって部分経路を積み上げ、最終的な経路を再構成します。
構造上の限界は明確です。Held-Karpの計算量は O(n² 2ⁿ) 時間、空間は O(n 2ⁿ) です。n = 20 なら状態数は約2,000万で、何とか扱えます。n = 30 になると10億超です。厳密さは状態空間が実用的である間だけ役に立ちます。率直な答えは、その境界を曖昧にせずに言うべきです。
ヒューリスティックのほうが賢い場面
ヒューリスティックは二流の答えではありません。実世界のTSP問題での近似としては、むしろそれしか正直な答えがないことも多いです。貪欲な最近傍法は速くて単純です。ある都市から始め、未訪問のうち最も近い都市へ常に移動し、最後に始点へ戻ります。最適性は保証しませんが、O(n²) で動き、最適解の20〜25%以内に収まる経路をよく出します。
より理にかなった選択肢がChristofidesのアルゴリズムです。距離が三角不等式を満たすメトリックTSPでは、最適解の1.5倍を超えない経路を保証します。多くのプロダクションシステムでは、多項式時間で解ける1.5倍保証のほうが、指数時間をかけて求める厳密解よりはるかに価値があります。
実際にはこう見える
2つの場面を考えてみてください。最初の場面では、面接で問題が「12都市の最適ツアーを求めてください」と出されます。Held-Karpが適切です。入力は小さく、面接官はDPの構造を見たがっており、厳密解が現実的に得られます。
2つ目の場面では、問題が「12,000件の配送先について、当日配送のルートを最適化してください」です。12,000ノードに対してHeld-Karpを回す人はいません。答えはヒューリスティック、あるいはメタヒューリスティックです。たとえば焼きなまし法、遺伝的アルゴリズム、商用ソルバーなどです。回路基板の配線や物流で使う車両ルーティングシステムは、入力サイズが完全最適化を罠にするため、1970年代から近似アルゴリズムに頼ってきました。NIST Dictionary of Algorithms and Data Structures では、TSPの厳密解法のスケーリング挙動が整理されており、実務で近似法が主流になる理由も説明されています。
厳密解から近似解へのこの移行と、その理由を言語化できる候補者こそが、教室の外の問題まで考えている人に見えます。
ホワイトボードの前にいるつもりでHeld Karpを説明する
状態、遷移、そして厄介な部分
Held-Karpアルゴリズムの面接での説明は、遷移を述べる前に状態定義を固定するのが最も有効です。状態は `dp[S][i]` で、`S` はこれまでに訪問した都市の集合を表すビットマスク、`i` は現在の経路の終点の都市です。格納する値は、固定した始点から出発して、集合 `S` に含まれる都市だけをちょうど訪問し、都市 `i` で終わる最小コストです。
遷移は、新しい都市 `j` を `S` に追加して経路を延長することです。`dp[S | (1 << j)][j] = min(dp[S][i] + dist[i][j])` を、妥当なすべての `i` について計算します。つまり、「ちょうど `S` の都市を訪問したあと、都市 `i` から来た状態で、都市 `j` に到達する最安の方法は何か？」を問うています。
多くの人が忘れがちで、面接官が欠けていると気づくのもここです。最後のステップ、つまりツアーの完了です。DPテーブルを埋めたあと、答えは `min over all i of (dp[(1<<n)-1][i] + dist[i][0])` になります。これで始点へ戻るループが閉じます。このステップがなければ、解いているのはTSPではなくハミルトン路問題です。
実際にはこう見える
4都市、0, 1, 2, 3 を考えてみましょう。都市0から始めます。
- `dp[{0}][0] = 0`（始点にいるのでコストは0）
- `dp[{0,1}][1] = dist[0][1]`（0から1へ移動）
- `dp[{0,2}][2] = dist[0][2]`（0から2へ移動）
- `dp[{0,1,2}][2] = min(dp[{0,1}][1] + dist[1][2], dp[{0,2}][2] + dist[2][2])` — ただし `dist[2][2] = 0` は役に立たないので、最初の項を採用します。つまり、都市1へ到達してから2へ進むコストです。
こうした表をホワイトボードに描く、あるいは2〜3行だけでも示すと、候補者が公式を知っているだけでなく、DPがどのように経路を段階的に構築するかを理解していることが伝わります。
ごまかさない計算量
Held-Karpの計算量は O(n² 2ⁿ) 時間、O(n 2ⁿ) 空間です。こんなにすぐ重くなる理由は、n都市の部分集合の数が 2ⁿ 個あり、それぞれについて n 通りの終点を追跡するため、状態数が n · 2ⁿ になるからです。各状態を埋めるには最大 n 通りの遷移を確認する必要があるので、時間計算量は n² · 2ⁿ になります。Bellmanの1962年の原論文と、その後のHeld-Karp定式化における古典的な扱いによれば、これはTSPに対する漸近計算量の観点で最良の既知の厳密アルゴリズムです。
計算量を知っていること自体より、それがなぜ重くなるかを説明できることのほうが重要です。「指数個の部分集合があり、それぞれについて現在地を追跡しているからです」という一文は面接官の記憶に残ります。「O(n² 2ⁿ)」だけでは、説明ではなく式です。
TSPの難しさを、講義ではなく実務者として説明する
なぜTSPはそもそも難しいのか
NP困難とは、平易に言えば、都市数が増えても最適経路を多項式時間で必ず見つけるアルゴリズムは知られていない、という意味です。解けないという意味ではありません。既知の最良の厳密手法が指数時間でスケールし、その指数的増加が大きな入力では実用にならない、という意味です。Stanford Encyclopedia of Philosophy の計算量理論の項目 は、NP-hard と NP-complete の違いを明確に説明しています。TSPの判定版は NP-complete、最適化版は NP-hard です。
面接で重要なのはこの帰結です。巡回セールスマン問題を大規模に総当たりすることはできませんし、既知の方法で多項式時間の厳密解法もありません。だからこそ、アルゴリズム選択が問題になるのです。
言いすぎずにどう言うか
使いやすい一文はこうです。「TSPはNP困難で、既知の最良の厳密アルゴリズムは都市数に対して指数的にスケールするので、大きな入力では近似法を使います。」それだけで十分です。3-SATからの帰着を図示する必要はありません。Cook-Levin定理を説明する必要もありません。
「難しい」と「不可能」は違います。TSPは「解けない」と言う候補者は減点されます。面接官が細かいからではなく、不正確さを示すからです。TSPは小さい入力なら解けます。Held-Karpならおよそ20都市までは厳密に解けます。「難しい」とは「多項式時間の厳密解法は知られていない」という意味であって、「諦める」という意味ではありません。
実際にはこう見える
面接官が「では、なぜ総当たりではだめなのですか？」と聞いたら、答えは階乗的増加と実用上の境界を結びます。「総当たりでは `(n-1)!` 通りの順列を調べます。10都市なら362,880通りで、何とか扱えます。20都市だと60兆通りを超えます。だから厳密探索は破綻し、DPや近似法が必要になるのです。」
この答えは3文です。簡潔で、感情的ではなく、面接官が求めている情報をちょうど与えます。
TSPを、混同されがちな問題と切り分ける
TSP vs 最短経路 vs 巡回郵便配達問題
TSPと最短経路の違いは、想像以上に多くの候補者をつまずかせます。最短経路、つまりDijkstra法やBellman-Ford法は、特定の2ノード間の最小コスト経路を求めます。TSPは、すべてのノードをちょうど1回ずつ訪れて始点に戻る、最小コストの経路を求めます。目的は完全に違います。片方は点から点へ、もう片方は全体を巡るツアーです。
巡回郵便配達問題（Chinese postman problem とも呼ばれます）も別物です。これは、すべてのエッジを少なくとも1回通る最小コスト経路を求めます。すべてのノードではありません。すべての道路を歩く郵便配達員を想像してください。一方、セールスマンは各顧客を一度ずつ訪問します。同じグラフでも、目的はまったく違います。
三角不等式と非対称性がなぜ重要か
メトリックTSPでは、距離が三角不等式を満たします。つまり、2都市間の直行距離は、第三の都市を経由する距離を上回らないということです。この制約があるからこそ、Christofidesのアルゴリズムの1.5倍近似保証が成り立ちます。これがなければ、P = NP でない限り定数近似は知られていません。
非対称TSPでは、都市AからBへの距離とBからAへの距離が同じであるとは限りません。一方通行道路、方向付きの航空路、時間依存コストなどがこれを生みます。問題はさらに難しくなり、対称TSPで成り立つ近似結果の多くがそのままでは使えません。
実際にはこう見える
例えば、道路A→Bは10分なのに、B→Aは一方通行のせいで25分かかるとします。これは非対称TSPです。次に、三角不等式が成り立ち、どんな近道も中継都市を経由するより悪くならないグラフを考えます。これはメトリックTSPで、Christofidesが使えます。どのバージョンを扱っているかで、選ぶアルゴリズムも、主張できる近似保証も変わります。
追加質問には、形式に惑わされずに答える
面接官が口に出してほしい前提条件
アルゴリズムを決める前に、次を確認してください。グラフは完全か。全ペアの距離は既知か。距離は対称か。近似解でよい時間制約があるか。これは時間稼ぎではありません。1つのTSPアルゴリズムしか知らない候補者と、問題空間を理解している候補者を分ける質問です。
面接官は追加質問で、あなたが目の前の問題に答えているのか、それとも自分が勉強した問題に答えているのかを見ています。アルゴリズムを選ぶ前に「これはメトリックTSPですか、それとも非対称ですか？」と聞ける候補者は、まさに上位層を分ける前提条件の置き方を示しています。
良い答えを弱く見せるミス
最も多い失敗は、候補者が「NP困難」と「動的計画法」を暗記しているのに、問題文の制約と結びつけられないことです。「TSPはNP困難なのでDPを使います」と、まるでそれで完結した文のように言ってしまう。そうではありません。NP困難性は、総当たりがなぜ失敗するかを説明します。DPはそれに対する一つの応答であり、小さい n に対して有効です。両者の関係を結ぶには、どの応答が適切かを決める制約、つまり入力サイズを言わなければなりません。
候補者が損をする構造的な理由は、別の質問に対する答えを暗記したように聞こえるからです。面接官は特定の制約を持つ具体的な問題を出しているのに、候補者は抽象版に答えている。このズレは見えますし、経験豊富な面接官はすぐに気づきます。
実際にはこう見える
強い追加質問への流れはこうです。面接官: 「どうスケールしますか？」 候補者: 「Held-Karpは O(n² 2ⁿ) なので、小さい n、たとえば20都市程度までは扱えますが、それを超えるとすぐ厳しくなります。」 面接官: 「もっと大きい入力ならどうしますか？」 候補者: 「ヒューリスティックに切り替えます。速度重視なら貪欲な最近傍法、保証付きの近似境界が必要ならChristofidesです。」 面接官: 「Christofidesの計算量は？」 候補者: 「最小全域木とマッチングのステップで O(n³)、全体では多項式時間で、メトリックTSPに対して最適値の1.5倍保証があります。」
候補者は各質問のたびに定義に戻りません。問題の内側にとどまり、層を一つずつ進みます。プレッシャーの下で見える強いTSP回答は、まさにこういうものです。
FAQ
Q: 面接で巡回セールスマン問題を平易に説明するにはどう言えばいいですか？
1文で言ってください。すべての都市をちょうど1回ずつ訪れて、出発点に戻る最短経路を見つける問題です。グラフ理論の語彙は、この文を明確に言ってから使えば十分です。定義が土台であり、他のすべてはまずそれが伝わることに依存しています。
Q: TSPはなぜ難しいのですか。NP困難性を、説教臭くならずにどう説明すべきですか？
NP困難とは、入力が増えてもTSPを最適に解く多項式時間アルゴリズムが知られていない、という意味です。実用上の帰結は、総当たりだと `(n-1)!` 通りを調べることになり、10都市なら扱えても20都市では壊滅的だということです。理論分類を暗唱するより、この帰結を口に出してください。「難しい」とは指数的にスケールする、という意味であって、「不可能」ではありません。
Q: 動的計画法と、ヒューリスティックや近似法は、いつ言及すべきですか？
入力が小さい（おおよそ n ≤ 20）うえ、面接官が厳密な最適解を求めているなら Held-Karp DP を使います。入力が大きい、時間制約が厳しい、あるいは実運用でどうするかを聞かれたなら、ヒューリスティックか近似法を使います。アルゴリズム名だけでなく、その境界を言うことが、回答を強くします。
Q: Held-Karpの状態、遷移、計算量をどう説明すればいいですか？
状態を `dp[S][i]` と定義します。これは、ビットマスク S に含まれる都市だけをちょうど訪問し、都市 i で終わる最小コストです。遷移は、未訪問の都市 j へ経路を延ばすことです。最後に始点へ戻ることで閉路を完成させます。計算量は時間 O(n² 2ⁿ)、空間 O(n 2ⁿ) です。式だけでなく、なぜそうなるか、つまり指数個の部分集合と n 通りの終点があるからだと必ず説明してください。
Q: 面接官はTSPのどんなトレードオフを見ていますか？
厳密さとスケーラビリティをどう天秤にかけるか、習慣ではなく明示された制約に基づいてアルゴリズムを選べるか、何を犠牲にしているかを認められるか、を見ています。指数コストに触れずにHeld-Karpを選ぶのも、近似であることに触れずにヒューリスティックを選ぶのも、どちらもトレードオフを考えていない印象を与えます。トレードオフこそが答えです。
Q: TSPは最短経路問題や巡回郵便配達問題とどう違いますか？
最短経路は、特定の2ノード間の最安ルートを求めます。TSPは、すべてのノードを通る最安の完全ツアーを求めます。巡回郵便配達問題は、すべてのエッジを少なくとも1回通ります。郵便配達員がすべての道路を回るのに対し、セールスマンは各顧客を訪ねるイメージです。同じグラフ構造でも、目的は完全に違います。
Q: 候補者がTSPについて話すときによくあるミスは何ですか？
代表的なミスは3つです。問題を定義する前にアルゴリズムに飛びつくこと、NP困難性を総当たりがなぜ失敗するかと結びつけないこと、そして問題文の制約付きのTSPではなく抽象版に答えてしまうことです。見落とされがちな4つ目のミスは、TSPを「解けない」と言ってしまうことです。これは、問題を知っている人には不正確さとして伝わります。
Q: 採用担当者はこの質問を使って、問題解決力とコミュニケーション力をどう見極めますか？
TSPは、いくつもの側面を同時に見るのにきれいなシグナルです。解く前に定義できるか、アルゴリズムを選ぶ前に前提条件を言えるか、計算量の結果を暗唱するだけでなく説明できるか、追加質問の圧力の下でも落ち着いていられるか。定義、難しさ、アルゴリズム選択、計算量という構造化された答えを出し、そのあと追加質問にリセットせず答えられる候補者は、実際のエンジニアリング問題に転用できる思考を示しています。
Verve AI が、巡回セールスマン問題の面接準備をどう支援できるか
TSP対策で構造的に難しいのは、アルゴリズムを知っていることと、実際のプレッシャーの中でそれを明確に伝えられることが、まったく別のスキルだという点です。多くの候補者は知識を持っています。場で崩れるのは順番です。定義が先、アルゴリズムが次、制約確認がその次、そして面接官に聞かれる前に計算量を説明する。この順序は、実際のフィードバックを伴う反復でしか安定しません。
Verve AI Interview Copilot は、まさにそのギャップのために作られています。後から書いた要約ではなく、あなたが話している最中の回答をリアルタイムで聞き取り、あなたが実際に言った内容に反応します。省略した部分や、想定していなかった追加質問も含めてです。Held-Karpの説明はしたのに最後の閉路完成ステップを飛ばしたなら、Verve AI Interview Copilot がそこを拾います。「NP困難」と言っただけで階乗増加と結びつけていなければ、その抜けを表に出します。フィードバックは一般的なTSP採点表ではなく、あなたの回答に特化しています。Verve AI Interview Copilot は、実際の技術面接のような追撃質問の圧力を再現する模擬面接も行います。「なぜ総当たりではだめなのか」「大規模ならどうするのか」「計算量は？」といった質問により、順番が努力ではなく自動化されます。
結論
TSPは、正しい順番で答えればそれほど怖くありません。定義が先、難しさが次、アルゴリズム選択が三番目、計算量が四番目です。この順番なら、各段階で次に何を言うべきかが明確なので、パニックの連鎖が起きませんし、面接官も最後まで話を追えます。
60秒のスクリプトを一度、頭の中ではなく声に出して練習してください。次に、4都市の例を使ってHeld-Karpの説明をもう一度通してください。この2回で、たいていパニックは収まり、罠のように感じた質問が、構造的に考えられることを示す機会へ変わります。
Taylor Nguyen
アーカイブ