【アルゴリズム】限られた資源で最大の戦果を！「部分巡回セールスマン問題」｜情報処理問題1000本ノック
すべての都市を回る時間がないとき、どの地点を「厳選」して回るべきか。実務の物流や観光ルート作成でも大活躍する、巡回セールスマン問題の重要な派生形を攻略しましょう。
1. 【 問題 】：グラフ理論と数理最適化問題
【 問題 】 巡回セールスマン問題（TSP）の派生問題の一つであり、移動時間や予算などの「限られた資源（制約条件）」の範囲内で、各地点に設定された価値や得点を考慮し、それらの合計が最大となるように「できるだけ多くの重要な地点」を選別して巡回する最適なルートを求める問題を何と呼ぶでしょうか？
① 中国人郵便配達問題 (Chinese Postman Problem)
② 最小全域木問題 (Minimum Spanning Tree Problem)
③ 部分巡回セールスマン問題 (Orienteering Problem / オリエンテーリング問題)
④ 最短経路問題 (Shortest Path Problem)
2. 正解：
正解： ③ 部分巡回セールスマン問題（オリエンテーリング問題）
3. 解説：「全部回る」から「価値の高い場所を厳選する」へのシフト
通常の巡回セールスマン問題は「指定された都市をすべて回り、その移動コストを最小にする」というルールですが、現実のビジネスでは時間や燃料に制限があって全部回れないことも多いです。そこで登場するのが部分巡回セールスマン問題です。
・問題の定義：各地点に「スコア（重要度や価値）」が設定されています。すべての地点を回る必要はなく（資源の制約で回れない）、「決められた制限時間内に、どの地点を組み合わせて回れば最も高いスコアを獲得して帰ってこられるか」を計算します。 ← ココが問題の正解！
・実務での応用：営業マンが1日（8時間という限られた資源）の中で、見込み度の高い顧客（重要な地点）をいくつかピックアップして効率よく回る訪問ルートの作成や、限られたバッテリーで多くの荷物を届けるドローンの配送ルート計画などに直接応用されています。
★ ① 中国人郵便配達問題：すべての「地点（点）」ではなく、すべての「道路（辺）」を少なくとも1回は通って元の場所に戻る最短ルートを求める問題です（ゴミ収集車の巡回など）。
★ ② 最小全域木問題：閉路（ループ）を作らずに、すべての地点を最小の結線コストで「一本のネットワークに繋ぐ（全域木）」問題です（光ファイバーの配線計画など）。
★ ④ 最短経路問題：出発地から目的地までの「2点間」を結ぶ、最もコストが低い1本のルートを求める問題です（カーナビの純粋な2点間検索など）。
1. 理解のコツ: 「制限時間1時間のテレビ番組のロケ（観光）」に例えてみましょう。
・京都にある観光名所を20箇所「すべて」最速で回るルートを決めるのが、通常の巡回セールスマン問題です。
・しかし、ロケ時間は1時間（限られた資源）しかありません。全部回るのは不可能です。そこで、「映え度（重要度）が高い金閣寺と清水寺は絶対にルートに入れ、近くの小さな神社をいくつか組み合わせて、ちょうど59分でロケバスが駅に戻ってくる最高効率のルートを厳選する」。この、制限時間の中で得点を最大化する数理パズルが部分巡回セールスマン問題です。スポーツの「オリエンテーリング」そのもののルールであるため、海外ではオリエンテーリング問題という名前で広く知られています。
2. 試験対策の視点: 「巡回セールスマン問題の中で」「限られた資源の中で」「できるだけ多くの重要な地点を回る」という、地点の取捨選択と資源制約のフレーズがあれば「部分巡回セールスマン問題」が一択です。基本情報や応用情報の午前試験では、アルゴリズムやグラフ理論の応用、あるいは高度試験（システムアーキテクトやエンベデッド）において、AIや自動運転、物流最適化システムの要件定義を読み解くための数理モデルの背景として非常によく狙われます。
4. まとめ
「資源（時間や予算）に上限がある現実の制約下で、訪問先の価値を最大化するために、行くべき地点の『選別』と『巡回ルート』を同時に最適化する高度な探索問題」。これが部分巡回セールスマン問題です。真面目に全探索をするとこれも組合せ爆発を起こすため、前回学んだ「ヒューリスティックアルゴリズム」などを使って高速に近似解を求めるアプローチが実務では一般的に使われています。