【アルゴリズム・データ構造】矢印（方向）を持つ頂点と辺で構成されたネットワーク！「有向グラフ」｜情報処理問題1000本ノック

基本情報技術者試験、応用情報技術者試験、高度試験のアルゴリズム・データ構造（グラフ理論）分野で極めて高頻出の重要概念。「有向グラフ（Directed Graph）」の定義と、前回学習した「無向グラフ」との比較、および実社会での適用例を攻略しましょう。

1. 【 問題 】：テクノロジ系（アルゴリズム・データ構造）

【 問題 】 グラフ理論におけるデータ構造に関する記述です。頂点（ノード）同士を結ぶ辺（エッジ）に向き（順序関係）が指定されており、指定された方向にのみ辿ることができる構造を持つグラフは、次のうちどれか。

（ア）無向グラフ（Undirected Graph）
（イ）有向グラフ（Directed Graph）
（ウ）完全グラフ（Complete Graph）
（エ）二部グラフ（Bipartite Graph）

2. 正解：

正解：（イ）有向グラフ（Directed Graph）

3. 解説：「『一方通行や手順・依存関係』を表現する基本構造！」

有向グラフは、エッジ（辺）が矢印の形をしており、起点（始点）から終点への方向を持ちます。
順序関係や依存関係が存在するデータ構造をモデル化する際に幅広く使われます。

【有向グラフと無向グラフの比較】 ← 超頻出ポイント！

項目	（イ）有向グラフ	（ア）無向グラフ
エッジ（辺）の性質	向き（矢印）がある	向き（矢印）がない
移動のルール	矢印の方向にのみ進行可能	双方向に自由移動可能
隣接行列の性質	非対称行列になることが多い	対称行列になる（$A_{ij} = A_{ji}$）
代表的な適用例	Webのリンク構造、タスク依存（PERT図）、一方通行路	SNSの友達関係、路線図（双方向）

1. 理解のコツ:
・「一方通行の道路網」や「タスクAが終わってからタスクBを進める（作業手順）」のように、**「順序や向き」が決まっているネットワーク**を描く時はすべて有向グラフになります。

2. 試験対策の視点:
・問題文に「ノード間の関係に向きがある」「矢印付きのエッジ」「一方通行」「順序関係」と来たら、迷わず有向グラフを選択しましょう！
・有向グラフの中でも、閉路（サイクル）を持たないものをDAG（Directed Acyclic Graph：有向非巡回グラフ）と呼び、ジョブスケジュール管理などで非常に重要な応用知識となります。

---

4. まとめ

頂点間のエッジに向き（順序関係）が存在し、一方通行の移動をモデル化するデータ構造。これが有向グラフです。向きを持たない「無向グラフ」との違いを隣接行列の性質も含めてしっかり整理しておきましょう！

【アルゴリズム・データ構造】方向を持たない頂点と辺で構成されたネットワーク！「無向グラフ」｜情報処理問題1000本ノック

基本情報技術者試験、応用情報技術者試験のアルゴリズム・データ構造（グラフ理論）分野で基本となる重要用語。「無向グラフ（Undirected Graph）」の性質と、隣接行列によるデータ表現方法を攻略しましょう。

1. 【 問題 】：テクノロジ系（アルゴリズム・グラフ理論）

【 問題 】 グラフ理論におけるデータ構造に関する記述です。すべての辺（エッジ）が方向や順序関係を持たない無向エッジで構成されており、接続された頂点（ノード）間を双方向に相互移動することができるグラフ構造は、次のうちどれか。

（ア）有向グラフ（Directed Graph / Digraph）
（イ）無向グラフ（Undirected Graph）
（ウ）完全二分木（Complete Binary Tree）
（エ）DAG（Directed Acyclic Graph）

2. 正解：

正解：（イ）無向グラフ（Undirected Graph）

3. 解説：「『双方通行の網の目』＝対称性を持つグラフ構造！」

無向グラフは、頂点間の結びつきに対称性（$A$から$B$に行けるなら、$B$から$A$にも行ける）があるネットワークを表現するのに最適なデータ構造です。
プログラミングやアルゴリズムで表現する際、隣接行列（Adjacency Matrix）で表すと対角線を挟んで対比が「線対称（対称行列）」になるという重要な数学的特徴があります。

【無向グラフと有向グラフの特性比較】 ← 超頻出ポイント！

グラフの種類	エッジの特徴	隣接行列の性質	代表的な適用例
（イ）無向グラフ	すべての辺に矢印（方向）がない。	行列が「線対称（対称行列）」になる。 （$A_{ij} = A_{ji}$）	路線図（双方向運転）、SNSの相互友達関係、電気回路網
（ア）有向グラフ	辺に矢印（方向）がある。	非対称になることが多い。 （一方向のみの接続があるため）	Webページのハイパーリンク構造、タスクの依存関係（PERT図）、一方通行路

1. 理解のコツ:
・「路線図」で「A駅とB駅の間を電車が往復している」状態が無向グラフです。
・一方、「一方通行の道路網」や「タスクの処理順序（Aが終わらないとBができない）」は有向グラフで表現します。

2. 試験対策の視点:
・問題文に「無向エッジからなる」「方向を持たない辺で構成」「双方向に移動可能」「隣接行列が対角線に対して対称」と出たら、迷わず無向グラフを選択しましょう！

---

4. まとめ

すべての辺が方向を持たない無向エッジで構成され、接続された頂点間を双方向に辿ることができるデータ構造。これが無向グラフです。矢印で進行方向が指定される有向グラフとの相違点を含めて、確実にマスターしておきましょう！

【アルゴリズム・データ構造】方向を持たない頂点間のつながり！「無向エッジと無向グラフ」｜情報処理問題1000本ノック

基本情報技術者試験、応用情報技術者試験のアルゴリズム・データ構造（グラフ理論）分野で基本となる重要概念。「無向エッジ（無向辺）」の定義と、対となる「有向エッジ（有向辺）」との違いを攻略しましょう。

1. 【 問題 】：テクノロジ系（アルゴリズム・グラフ理論）

【 問題 】 データ構造におけるグラフ（Graph）に関する記述です。頂点（ノード）同士を結ぶ辺（エッジ）のうち、接続する2点間に方向や順序関係を持たず、両方向に双方向で辿ることができるエッジは、次のうちどれか。

（ア）有向エッジ（Directed Edge）
（イ）無向エッジ（Undirected Edge）
（ウ）重み付きエッジ（Weighted Edge）
（エ）自己ループ（Self-loop）

2. 正解：

正解：（イ）無向エッジ（Undirected Edge）

3. 解説：「『矢印のない線』＝どちらからでも通れる双方向の結びつき！」

グラフ構造は、点である「頂点（ノード / バート・Vertex）」と、点を結ぶ線である「辺（エッジ・Edge）」で構成されます。
エッジに矢印（向き）がなく、順序関係を持たないものを無向エッジと呼び、全エッジが無向エッジであるグラフを無向グラフと呼びます。

【無向エッジと有向エッジの比較】 ← 基礎・超重要ポイント！

種類	エッジの表記	関係性の特徴	現実世界の例
（イ）無向エッジ （Undirected Edge）	単なる線 （$A - B$）	順序関係を持たない。 $A \to B$ も $B \to A$ も同等。	SNSの「相互フレンド関係」、双方向通行の道路網
（ア）有向エッジ （Directed Edge）	矢印付きの線 （$A \to B$）	明確な方向・順序関係を持つ。 起点（始点）と終点が決まっている。	SNSの「フォロー・フォロワー」、一方通行の道路、処理の依存関係・フローチャート

1. 理解のコツ:
・「AさんとBさんは友達である」という関係は、互いに向きがないため無向エッジです。
・「AさんがBさんのWebサイトへリンクを貼っている」という関係は、一方通行の矢印になるため有向エッジです。

2. 試験対策の視点:
・問題文に「順序関係を持たない」「方向がない」「双方向に辿れる」と出たら、迷わず無向エッジ（無向グラフ）を選択しましょう！
・グラフの最短経路問題（ダイクストラ法やプリム法など）を解く際も、対象が「無向グラフ」か「有向グラフ」かで隣接行列・隣接リストの構造が変わるため、基礎として必須の概念です。

---

4. まとめ

頂点間に方向や順序関係を持たず、両方向に辿ることができる辺。これが無向エッジです。矢印によって明確な進行方向を持つ有向エッジとの違いも含めてしっかり整理しておきましょう！

【アルゴリズム設計】その場その場の「ベスト」を愚直に選ぶ！「貪欲法（Greedy Algorithm）」｜情報処理問題1000本ノック

基本情報技術者試験、応用情報技術者試験、アルゴリズム・プログラミング分野で頻出の重要設計手法。「貪欲法（グリーディ法）」の定義と、動的計画法（DP）や全探索との違いを攻略しましょう。

1. 【 問題 】：テクノロジ系（アルゴリズム・データ構造）

【 問題 】 段階的に判断を行う最適化問題のアルゴリズム設計技法に関する記述です。各ステップにおいて、全体最適解になるかどうかの検証や将来への影響の考慮を行わず、その時点で最も評価が高い選択肢（局所最適解）を貪欲に選び続けて解を導出する手法は、次のうちどれか。

（ア）動的計画法（Dynamic Programming）
（イ）貪欲法（Greedy Algorithm）
（ウ）分割統治法（Divide and Conquer）
（エ）バックトラッキング（Backtracking）

2. 正解：

正解：（イ）貪欲法（Greedy Algorithm）

3. 解説：「『目先の利益』を最優先で選んで進むシンプル解法！」

貪欲法（Greedy Algorithm）は、「目先の利益（局所解）」だけを見て選択を決定していく手法です。
計算量が少なく高速に解を求められるメリットがある反面、「全体の最適解（全体解）」に到達できるかどうかは問題の構造（マトロイド構造や最適な部分構造をもつか）に依存するという性質があります。

【代表的なアルゴリズム設計技法の比較】 ← 超頻出ポイント！

設計技法	アプローチの特徴	代表的な適用例
（イ）貪欲法 （Greedy）	各ステップで目先の局所最適解を検証せずに選択する。高速。	おつりの枚数最小化（日本円等の硬貨）、ハフマン符号、プリム法・ダイクストラ法（グラフ最短経路）
（ア）動的計画法 （DP）	問題を小さな部分問題に分割し、部分問題の計算結果をメモ（記録）して再利用することで全体最適解を求める。	ナップサック問題、編集距離（Levenshtein distance）
（ウ）分割統治法	大きな問題を小さく分割し、それぞれを独立して解いたあとに解を結合・統合する。	マージソルト、クイックソート
（エ）バックトラッキング	解の候補を探索し、条件に合わないと分かった時点で1つ前の分岐まで戻って別の選択肢を試す（枝刈り）。	Nクイーン問題、迷路解法

1. 理解のコツ:
・例えば「100円、50円、10円、1円で462円のおつりを払う」時、「大きい硬貨から順番に使えるだけ使う」という選び方は貪欲法です（日本円の貨幣体系では、この貪欲法で枚数最小＝全体最適解になります）。
・一方、特殊な硬貨体系（例：1円、4円、5円で8円を作る場合、貪欲法だと `5+1+1+1` で4枚になりますが、全体最適解は `4+4` の2枚）では、貪欲法では最適解にならないケースがあります。

2. 試験対策の視点:
・問題文に「局所解」「全体最適解であるか検証しない」「その時点で最も良い選択肢を選ぶ」「目先の最適」と来たら、迷わず貪欲法（グリーディ法）を選択しましょう！

---

4. まとめ

検証を行わずに各段階の局所最適解（目先の最善）を選択していくアルゴリズム設計手法。これが貪欲法です。部分問題の計算結果をメモしながら全体最適を保証する「動的計画法（DP）」との違いも含めてしっかり整理しておきましょう！

【アルゴリズム】古代ギリシャから続く最古の計算手法！「ユークリッドの互除法」｜情報処理問題1000本ノック

基本情報技術者・応用情報技術者試験の数値計算・アルゴリズム分野で頻出の古典的アルゴリズム。「ユークリッドの互除法」の定義と、選択肢に登場する他の数学的アルゴリズムとの違いを攻略しましょう。

1. 【 問題 】：テクノロジ系（アルゴリズム・数値計算）

【 問題 】 2つの整数の最大公約数（GCD：Greatest Common Divisor）を、割り算（余りを求める計算）を繰り返すことによって効率的に求めるアルゴリズムとして知られているものは、次のうちどれか。

（ア）ユークリッドの互除法
（イ）エラトステネスの篩（ふるい）
（ウ）ニュートン法
（エ）モンテカルロ法

2. 正解：

正解：（ア）ユークリッドの互除法

3. 解説：「『余りで割る』を余りが0になるまで繰り返す！」

ユークリッドの互除法は、「2つの自然数 $a$ と $b$（$a > b$）の最大公約数は、$b$ と『$a$ を $b$ で割った余り $r$』の最大公約数と等しい」という性質を利用して、余りが0になるまで割り算を繰り返す計算手法です。

【問題選択肢（数学的アルゴリズム）の正体一覧】 ← 超頻出ポイント！

アルゴリズム名	概要・何を求めるものか
（ア）ユークリッドの互除法	2つの整数の「最大公約数（GCD）」を求める。
（イ）エラトステネスの篩（ふるい）	指定した範囲の全自然数から「素数」を抽出・列挙する。
（ウ）ニュートン法	方程式の「近似解（ルートの値など）」を収束させて求める。
（エ）モンテカルロ法	「乱数（確率）」を多数発生させて数値計算・近似解（円周率など）を求める。

1. 理解のコツ（ユークリッドの互除法の手順例：1071 と 102 の最大公約数）:
① $1071 \div 102 = 10$ 余り 51
② $102 \div 51 = 2$ 余り 0 ➔ 余りが0になった時の割った数「51」が最大公約数！

2. 試験対策の視点: プログラミングやアルゴリズムの基本問題で非常に頻出です。
問題文に「最大公約数」「あまりを求める」「互いに割る」と出たらユークリッドの互除法、「素数を探す」と出たらエラトステネスの篩を選択しましょう！

---

4. まとめ

2つの整数の最大公約数を求める最古・最重要なアルゴリズム。これがユークリッドの互除法です。素数を見つける「エラトステネスの篩」や近似解を求める「ニュートン法」との言葉の区別も完璧にしておきましょう！

【アルゴリズム】すべての「枝」を1度だけ通る一筆書き！「オイラー回路」｜情報処理問題1000本ノック

アルゴリズムや離散数学における「グラフ理論」。すべての枝（エッジ）を重複なくちょうど1度だけ通って出発点に戻る「オイラー回路」の定義と成立条件を攻略しましょう。

1. 【 問題 】：アルゴリズムとデータ構造（グラフ理論）

【 問題 】 グラフ理論における回路（閉路）に関する記述です。与えられたグラフにおいて、すべての枝（エッジ）をちょうど1度だけ通って出発点に戻ってくる回路（一筆書き可能な閉路）を何と呼ぶでしょうか？

（ア）オイラー回路（Eulerian Circuit）
（イ）ハミルトン閉路（Hamiltonian Cycle）
（ウ）最短経路（Shortest Path）
（エ）完全グラフ（Complete Graph）

2. 正解：

正解：（ア）オイラー回路（Eulerian Circuit）

3. 解説：「一筆書きで元の場所に戻れるか？」

オイラー回路（Eulerian Circuit / オイラー閉路）は、数学者レオンハルト・オイラーが解決した有名な数学問題「ケーニヒスベルクの橋のパズル」に由来する概念です。
すべての「枝（線）」を残さず一筆書きで通り、なおかつ最後に出発点へ戻ってくるルートが存在するとき、そのグラフは「オイラーグラフ」と呼ばれます。

【オイラー回路が存在する定理（必要十分条件）】 ← ココが試験の応用ポイント！

連結な無向グラフにオイラー回路が存在するための条件は、

「すべての頂点の次数（つながっている枝の数）が偶数であること」

※1つでも枝の数が「奇数」である頂点が存在する場合、スタート地点に戻るオイラー回路は絶対に作れません！

【ハミルトン閉路との見分け方】

名称	対象（何を通るか）	条件
（ア）オイラー回路	すべての「枝（エッジ）」	すべての枝をちょうど1度だけ通りスタートへ戻る。
（イ）ハミルトン閉路	すべての「頂点（ノード）」	すべての頂点をちょうど1度だけ通りスタートへ戻る。

1. 理解のコツ: 「道路清掃車」に例えてみましょう。
・オイラー回路：街の中にある「すべての道路（枝）」を、重複なく綺麗に掃除しながら走り、最後に出発点の基地に戻ってくるルートです。同じ交差点（頂点）を何度通り抜けても問題ありません。
・ハミルトン閉路：すべての「チェックポイント（頂点）」を重なりなく巡るルートです。

2. 試験対策の視点: 基本情報技術者試験や応用情報技術者試験で頻出のキーワードです。
問題文に「すべての枝を1度だけ」「一筆書き」「オイラー」とあれば、迷わずオイラー回路（オイラー閉路）を選択してください。
また、知識問題として「全頂点の次数が偶数 ➔ オイラー回路が存在する」という性質が選択肢に組み込まれることもあるため、セットで覚えておきましょう！

---

4. まとめ

「すべての枝をちょうど1度だけ通って出発点に戻ってくる一筆書き回路」。これがオイラー回路です。すべての頂点を巡る「ハミルトン閉路」との対比を完璧にしておきましょう！

【アルゴリズム】すべてのペアが直接つながる！「完全グラフ」｜情報処理問題1000本ノック

アルゴリズムや離散数学における「グラフ理論」。すべての頂点間に枝（エッジ）が存在する「完全グラフ」の構造と、試験でよく問われるエッジ数の計算公式を攻略しましょう。

1. 【 問題 】：アルゴリズムとデータ構造（グラフ理論）

【 問題 】 グラフ理論における無向グラフの構造に関する記述です。含まれるすべての異なる2頂点のペアの間に、必ず1本の枝（エッジ）が存在する（すべての頂点が互いに直接結ばれている）グラフを何と呼ぶでしょうか？

（ア）完全グラフ（Complete Graph）
（イ）連結グラフ（Connected Graph）
（ウ）平面グラフ（Planar Graph）
（エ）二部グラフ（Bipartite Graph）

2. 正解：

正解：（ア）完全グラフ（Complete Graph）

3. 解説：「全員が全員と友達！密度の極限グラフ」

完全グラフ（Complete Graph）は、頂点の集合において「これ以上枝を追加できない」限界まで枝が張られたグラフ構造です。
頂点数が $N$ 個の完全グラフは通常 $K_N$ と表記されます。たとえば、頂点数3の完全グラフ（$K_3$）は三角形、頂点数4（$K_4$）は対角線を含む四角形（四面体の展開図のような形）になります。

【完全グラフの「総枝数（エッジ数）」の公式】 ← ココが試験の計算問題で超頻出！

頂点数が N 個の完全グラフにおける枝（エッジ）の総数 E は、以下の公式で求められます。

E = N × (N - 1) / 2

【例】頂点数が 5個（N=5）の完全グラフのエッジ数：
E = 5 × (5 - 1) / 2 = 10本 （※組み合わせ ₅C₂ の計算と同じ）

1. 理解のコツ: 「総当たり戦（リーグ戦）」に例えてみましょう。
・参加チームを「頂点」、対戦試合を「枝（エッジ）」と考えます。
・完全グラフとは、「全員が他のすべてのチームと1回ずつ対戦する総当たり戦」の対戦表そのものです。5チームで総当たり戦を行うと全10試合になりますが、これがそのまま枝の数になります。

2. 試験対策の視点: 基本情報技術者試験や応用情報技術者試験のテクノロジ系（離散数学・アルゴリズム）で出題されます。
用語の定義問題として「すべての頂点間に枝がある」と問われたら即座に完全グラフを選びましょう。
また、「頂点数 N の完全グラフの枝の数はいくつか？」という計算問題も多いため、$N(N-1)/2$ の計算式を頭に入れておくと一瞬で解けます。

---

4. まとめ

「すべての頂点ペアの間に枝が存在するグラフ」。これが完全グラフです。用語の意味に加えて、枝の総数を求める公式 N(N-1)/2 とセットで完璧に記憶しておきましょう！

【アルゴリズム】現実的な時間で合格点を見つけ出す！「ヒューリスティック」｜情報処理問題1000本ノック

すべてのパターンを計算すると宇宙が滅びるほどの時間がかかってしまう難問に対し、経験則や直感的なアプローチを用いて「そこそこ正しく、実用的な答え」を瞬時に導き出す「ヒューリスティック（近似アルゴリズム）」を攻略しましょう。

1. 【 問題 】：難関問題へのアプローチ（ヒューリスティック）

【 問題 】 コンピュータで解くアルゴリズムにおいて、巡回セールスマン問題に代表される「NP困難問題」など、問題の規模が大きくなると現実的な時間内に厳密解（理論上100%正しい最適な答え）を求めることが実質的に不可能になるものがあります。このような問題に対し、計算時間を大幅に短縮する代わりに、必ずしも最適とは限らないものの、実用的に十分な精度を持つ「近似解」を経験則や直感的なルールに基づいて導き出す手法を何と呼ぶでしょうか？

① 動的計画法（ダイナミック プログラミング）
② 力まかせ探索（ブルートフォース探索）
③ 分枝限定法（ブランチ アンド バウンド）
④ ヒューリスティック（近似アルゴリズム）

2. 正解：

正解： ④ ヒューリスティック（近似アルゴリズム）

3. 解説：完璧さを捨てて「スピード」を取る知恵

アルゴリズムの世界には、データの数が少し増えただけで計算量が爆発的に増えてしまい（指数関数的・階乗的な増加）、最新のコンピュータを何年動かしても解けない問題（NP困難問題など）が存在します。そこで登場するのがヒューリスティックです。これは完璧な正解を保証しない代わりに、「現実的な時間内で、十分実用的な答えを見つける」というトレードオフの思想に基づいています。

【厳密解を求める手法とヒューリスティックの比較】 ← ココが試験のポイント！

手法・アプローチ	得られる答え	計算時間（問題が大規模なとき）	特徴
② 力まかせ探索	100%正しい厳密解	膨大（計算量爆発でフリーズ）	すべての組み合わせを泥臭く全探索する。
① 動的計画法	100%正しい厳密解	問題によっては高速（制限あり）	問題を小さな部分問題に分割し、結果を再利用する。
④ ヒューリスティック	実用的な近似解	圧倒的に短い（一瞬〜数秒）	「近いところから順に選ぶ」などの経験則で解く。

※ ③ 分枝限定法は、全探索の途中で「これ以上探しても無駄」と分かったルートを途中で切り落とす（枝刈り）ことで、厳密解を求める時間を短縮する手法です。

1. 理解のコツ: 「旅行の荷造り（ナップサック問題）」に例えてみましょう。
・カバンに荷物を詰めるとき、持っていくものの組み合わせは数千、数万通りあります。重さや価値をすべて計算して「最も価値が高くなる組み合わせ（厳密解）」を計算しようとすると、出発の時間を過ぎてしまいます（これが②の全探索）。
・そこで私たちは無意識に「とりあえず、絶対に使う大事なもの（スマホや財布）を先に詰め、空いたスペースに小さくて軽いものを適当に詰め込もう」というルールで荷造りをしますよね。これがヒューリスティック（選択肢④）です。この方法なら、1秒で「そこそこ大満足な荷造り（近似解）」が完成します。完璧ではないけれど、実生活でもコンピュータの世界でも、この『割り切り』がめちゃくちゃ重要なのです。
2. 試験対策の視点: 午前試験の問題文に「NP困難問題」「厳密解を求めるのが困難」「近似解」「経験則」というキーワードが並んでいたら、迷わずヒューリスティックを選んでください。 また、午後試験や高度試験のアルゴリズム問題では、具体的に「巡回セールスマン問題に対し、一番近い都市を順番に選んでいくヒューリスティック手法（貪欲法の一種）を採用する」といった形で、長文問題のロジックとして組み込まれることがよくあります。「完璧な答えを諦めて、現実的なスピードを手に入れるための技術なんだ」という目的を理解しておくことが、応用問題を解く鍵になります。

---

4. まとめ

「計算量が爆発するような難問に対し、100%の最適解を求めることを諦め、経験則や簡単なルールを用いて、実用的な時間内に合格点となる近似解を導き出す手法」。これがヒューリスティックです。現代のAI（人工知能）の探索技術や、経路ナビゲーションシステムの裏側でも大活躍している超重要概念としてインプットしておきましょう！

【アルゴリズム】最悪のシナリオを最小限に抑える！「ミニマックス問題」｜情報処理問題1000本ノック

ビジネスやシステムの設計では、「一番うまくいかなかったとき（最悪のケース）」の被害をどこまで小さく抑えられるか、という視点が不可欠です。この思想を数理的に扱う「ミニマックス問題」を攻略しましょう。

1. 【 問題 】：最適化問題（ミニマックス法）

【 問題 】 ある物流センターから3つの都市（都市A、都市B、都市C）へ同時に荷物を配送するため、配送ルートの計画を検討しています。 次の表は、選択肢である4つのルート（ルート1〜4）を選んだときに、各都市にトラックが到着するまでにかかる時間（時間）を示したものです。 3つの都市すべてに荷物が届くまでの「全体の配送時間」は、3都市のうち最も遅く到着したトラックの時間で決まります。 全体の配送時間を最も短くしたいとき、ミニマックス（Minimax）の原則に従って選択すべき最適なルートはどれでしょうか？

【 各ルートにおける各都市への配送時間（表） 】

選択ルート	都市Aへの時間	都市Bへの時間	都市Cへの時間
ルート1	5時間	6時間	4時間
ルート2	3時間	8時間	3時間
ルート3	2時間	4時間	9時間
ルート4	7時間	3時間	5時間

① ルート1
② ルート2
③ ルート3
④ ルート4

2. 正解：

正解： ① ルート1

3. 解説：「最大のものを、できるだけ小さくする」

ミニマックス問題の本質は、提示された条件の中から「それぞれの選択肢における最大値（最悪の結果）」をまず特定し、その最大値同士を比べて「一番値が小さくなる選択肢」を選ぶという2ステップの思考にあります。

【ミニマックス評価のステップとメカニズム】

ステップ1（Max：最大値の抽出）：各ルートごとに、最も時間がかかる（ワーストの）都市の時間を抜き出します。
・ルート1：[5, 6, 4] → 最大値は 6時間 (都市B)
・ルート2：[3, 8, 3] → 最大値は 8時間 (都市B)
・ルート3：[2, 4, 9] → 最大値は 9時間 (都市C)
・ルート4：[7, 3, 5] → 最大値は 7時間 (都市A)

ステップ2（Min：最小化の選択）：ステップ1であぶり出した「各ルートの最大時間」を比較し、それが最も小さくなる（早く終わる）ルートを選びます。 ← ココが問題の正解！

【 評価結果のまとめ表 】

選択ルート	各ルートの最大時間（ワーストケース）	判定
ルート1	6時間	★最小（最適）
ルート2	8時間
ルート3	9時間
ルート4	7時間

最悪のケースを比較すると、ルート1の「6時間」が最も短いため、ミニマックスの原則に基づく最適な選択はルート1（①）となります。

[ 受験生を惑わせる「評価基準の勘違い」の罠 ]
★ ②、③ 平均や局所的なメリットに騙される罠：
ルート3は都市Aにわずか「2時間」で届くため一見魅力的に見えますが、都市Cに「9時間」もかかるため全体としては一番遅くなってしまいます。また、各ルートの「合計時間」や「平均時間」を計算すると、ルート1は15時間、ルート2は14時間、ルート3は15時間、ルート4は15時間となり、単純な合計ではルート2が一番優秀に見えます。しかし、今回は「全員に届くまでの最大時間」を競っているため、平均値に惑わされてルート2を選ぶと不正解になります。

1. 理解のコツ: 「グループ登山」に例えてみましょう。
・4つの班（ルート1〜4）がそれぞれ3人のメンバー（都市A〜C）を連れて登山をしています。山のルールは「班全員が山頂に揃った時点でゴール」です。
・どれだけ足の速い人がいても、班で「一番足の遅い人（最大値）」のペースに合わせて進むしかありません。そのため、一番遅い人の到着時刻がその班のゴール時間になります。
・店長やリーダーとしてどの班の作戦を採用するか選ぶとき、「一番遅い人の到着時間が、最も早くなるようなバランスの良い班」を選びますよね。この『足を引っ張る要素（最大値）を、どこまでマシにできるか（最小化）』という選び方こそが、ミニマックス問題の考え方です。
2. 試験対策の視点: 試験で「ミニマックス（Minimax）」という言葉を見たら、言葉を後ろから分解して「まずMax（最大）を見て、次にそれをMin（最小）にする」と機械的に処理してください。 これと対になる概念として、ゲーム理論では「マキシマックス（Maximax：最高のシナリオを想定し、その中で最大の利益を狙う超ポジティブな戦略）」なども出題されます。言葉の定義を正確に捉え、問題文の表のどこに丸をつけるべきかの手順を覚えておけば、計算自体は単純なため確実に得点できるボーナス問題になります。

---

4. まとめ

「複数の評価軸や目的関数が存在するとき、それぞれの選択肢における最大のリスクや損失（最大値）を評価し、その最大値が最も小さくなる選択肢を最適解として決定する手法」。これがミニマックス問題です。リスク管理やインフラ設計の基本思想となる重要な概念ですので、表の読み方をしっかりマスターしておきましょう！

【アルゴリズム】「Aの前に必ずBに立ち寄れ」！「優先順位付き巡回セールスマン問題」｜情報処理問題1000本ノック

一筆書きの美しさよりも、業務の順番（段取り）が最優先。地点同士の「前後関係の縛り」をクリアしながら最短ルートを導き出す、実務直結の最適化アルゴリズムを攻略しましょう。

1. 【 問題 】：グラフ理論と順序制約の最適化問題

【 問題 】 巡回セールスマン問題（TSP）の派生問題の一つであり、特定の訪問先（都市や顧客）の間に「地点Aを訪問する前に、必ず地点Bを訪問していなければならない」といった、訪問順序に関する制約条件（先行制約・優先順位）があらかじめ設定されており、その順序をすべて守りながら全体の移動コストを最小にするルートを求める問題を何と呼ぶでしょうか？

① 優先順位付き巡回セールスマン問題 (Precedence-Constrained TSP)
② 時間窓付き巡回セールスマン問題 (Traveling Salesman Problem with Time Windows)
③ 部分巡回セールスマン問題 (Orienteering Problem)
④ 容量制約付き車両配送問題 (Capacitated Vehicle Routing Problem)

2. 正解：

正解： ① 優先順位付き巡回セールスマン問題 (Precedence-Constrained TSP)

3. 解説：「最短ルート」をへし折る、業務のタスク順序

標準的な巡回セールスマン問題は、すべての地点を一番効率よく回るだけの「空間的なパズル」ですが、そこに「タスクの順序」という制約を足したのが優先順位付き巡回セールスマン問題です。

【優先順位（先行制約）がもたらす計算の難しさ】

・本質：地点同士に「矢印（順序関係）」のネットワークが組み込まれます。 ← ココが問題の正解！

・ビジネスでの発生例：荷物の「集荷と配達（ピックアップ＆デリバリー）」が典型です。当たり前ですが、倉庫や顧客Aの家で荷物を「集荷（先）」しなければ、顧客Bの家に「配達（後）」することはできません。また、工場の組み立てロボットの移動経路であれば、「部品Aを取り付ける（先）」前に「ネジBを締める（後）」ことはできない、といった物理的な順序（優先順位）がルートを縛ります。これによって、見た目の距離がどんなに近くてもその順番でしか進めなくなるため、探索空間が制限され、効率的な解を見つけるアルゴリズムが非常に複雑になります。

[ 選択肢のシャッフル解説（巡回・配送最適化の高度なライバルたち） ]
★ ② 時間窓付き巡回セールスマン問題：前回学びましたね。順序ではなく「9時〜12時の間」のように、各地点に設定された特定の「時間帯の縛り（Time Window）」を守る問題です。
★ ③ 部分巡回セールスマン問題：時間やコストの制限内に、すべての地点ではなく、価値（スコア）が高い地点を「厳選」して巡回し、得点を最大化する問題です。
★ ④ 容量制約付き車両配送問題（CVRP）：1人ではなく「複数台のトラック」を使い、それぞれのトラックの積載重量（容量）を超えないように荷物を小分けにしながら、複数の顧客を効率よく回るルートを設計する、さらに大規模な物流最適化問題です。

1. 理解のコツ: 「ネットオークションの商品の受け渡し」に例えてみましょう。
・地図を広げて、出品者の家、落札者の家、郵便局、自分の家を一番短距離で回るルートを考えるのが通常の巡回セールスマン問題です。
・しかし現実には、『まず出品者の家で商品を預かり（先）、次に郵便局で専用の箱を買い（先）、それを自分の家で梱包し（先）、最後に落札者の家に届ける（後）』という、絶対にひっくり返せない順番があります。距離が近いからといって、最初に落札者の家に行っては元も子もありません。この仕事の段取り（優先順位）を破らずに、なおかつ全体の移動を一番無駄なく組み立てるのが、この優先順位付き巡回セールスマン問題です。
2. 試験対策の視点: 「ある地点は先に、ある地点は後で」「順序に関する制約条件」「優先順位（先行制約）」という文脈があれば「優先順位付き巡回セールスマン問題」が一択です。基本情報の科目B（アルゴリズムの思考力）や、応用情報の午前試験、さらにはシステムアーキテクトや高度な応用数学系の試験において、物流DXの配車管理、製造業の生産工程（スケジューリング）最適化のロジックとして非常によく注目されるホットな問題です。

---

4. まとめ

「距離や時間を短縮するという地理的な効率性に、『このタスクを終わらせてから次へ進め』という厳格な業務順序（優先順位）の縛りを融合させた、実社会のプロセス設計に直結する数理最適化問題」。これが優先順位付き巡回セールスマン問題です。これで「時間窓」と「優先順位」という、現場で使われる2大巡回アルゴリズムが完全に揃いましたね！