【アルゴリズム設計】その場その場の「ベスト」を愚直に選ぶ！「貪欲法（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大巡回アルゴリズムが完全に揃いましたね！

【アルゴリズム】中身をギュッと1つにまとめる！「凝集度（コヒージョン）」｜情報処理問題1000本ノック

プログラムの部品（モジュール）は、あれもこれもできる万能ツールにするより、1つの専門職にするのが正解。モジュール内部の「まとまりの強さ」を測る最重要モノサシを攻略しましょう。

1. 【 問題 】：モジュール設計の評価指標（凝集度）

【 問題 】 ソフトウェアの構造化設計において、作成した一つのモジュール（関数やクラスなどの部品）の内部に含まれる機能やデータが、「どの程度、そのモジュール内で単一の目的のために密接に関連し、独立しているか」という内部の結びつきの強さ（まとまり度合い）を表す指標はどれでしょうか？

① 凝集度 (Cohesion / コヒージョン)
② 結合度 (Coupling / カップリング)
③ 複雑度 (Complexity / サイクロマティック複雑度)
④ 網羅度 (Coverage / カバレッジ)

2. 正解：

正解： ① 凝集度 (Cohesion)

3. 解説：「中身のまとまり」と「外との繋がり」を絶対に見分ける

システムを修正しやすく、バグの起きにくい綺麗な状態に保つための基本原則が「高凝集（凝集度を高くする）」です。問題文にある通り、結合度とは視点の向きが180度異なります。

【凝集度と結合度の決定的な違い】

・凝集度（モジュール「内部」の視点）：今回の正解です。そのモジュールの中にあるコードが、どれだけ純粋に1つの専門機能のために集まっているかを示します。最も理想的なのは、1つのことだけを完璧にこなす「機能的凝集（強度）」です。 ← ココが問題の正解！

・結合度（モジュール「同士」の視点）：ひっかけのライバルです。モジュールAとモジュールBが、どれだけお互いに依存し合っているか（相手の変更に影響を受けるか）という「外部との繋がり」を示します。こちらは逆に、値が低い（疎結合・依存していない）ほど良い設計とされます。

[ 選択肢のシャッフル解説（モジュール評価に関するライバル用語たち） ]
★ ② 結合度：上記の通り、モジュール間の依存度を表す指標です。良い設計にするには「結合度は低く、凝集度は高く」する必要があります。
★ ③ 複雑度：以前学びましたね。プログラム内の条件分岐（if文など）の数から、コードの論理的なルートがどれだけごちゃごちゃしているかを数値化したものです。
★ ④ 網羅度（カバレッジ）：テスト工程において、作成したテストケースによって、ソースコード全体の何％を実際に実行してテストできたかという「テストの達成割合」を表す指標です。

1. 理解のコツ: 「会社の組織（チーム）と部署の連携」に例えてみましょう。
・「経理部」の中に、経理のプロだけが集まっていて、全員が経理の仕事（単一の目的）だけを黙々とこなしている状態。これが内部のまとまりが最高に強い高い凝集度です。もしここに「ついでに営業もやって、ついでに総務の仕事もして」と色々な機能を混ぜると、ごちゃごちゃになって「凝集度が低い（悪い状態）」になります。
・一方で、その経理部が仕事をするために、お隣の営業部から『データをどれくらい細かく、どんな形式でもらっているか（依存しているか）』というのが結合度です。営業部のルールが変わるたびに経理部のやり方も変えなきゃいけない状態は「結合度が強い（悪い状態）」です。『部署の中身はプロ専門（高凝集）、部署同士の連絡はシンプルな書類1枚だけ（疎結合）』が最高の組織ですよね。プログラムも全く同じです。
2. 試験対策の視点: 「モジュールの機能がどの程度、そのモジュール内にあるか」「内部の関連性の強さ」「単一の目的」という記述があれば「凝集度（強度）」が一択です。基本情報の科目Bや応用情報の午前試験において、凝集度の種類（機能的、情報的、連絡的、手続き的、時間的、論理的、偶発的）の強弱順を並び替えさせたり、結合度との関係を正しく理解しているかを問う問題は、ソフトウェア設計理論の王道中の王道です。

---

4. まとめ

「1つのモジュールにあれこれと仕事を詰め込まず、1つの目的のための機能だけをギュッと凝縮して独立性を高めるための設計モノサシ」。これが凝集度です。「凝集度は高く、結合度は低く」。この2大指標のセオリーをマスターすれば、美しいシステム設計の基礎は完全に制覇したも同然です！

【アルゴリズム】ソースコードの「ごちゃごちゃ度」を数値化！「循環的複雑度」｜情報処理問題1000本ノック

プログラムの読みやすさやバグの潜みにくさを科学的に測る。分岐の数からコードの複雑さを割り出す重要指標「循環的複雑度」を攻略しましょう。

1. 【 問題 】：プログラムの構造複雑度とテスト設計

【 問題 】 ソフトウェアのソースコード解析やテスト設計において、プログラムの制御フロー（条件分岐やループなど）に基づき、コードの論理的な複雑さを数理的に示す指標はどれでしょうか？
この値はプログラム内の「独立した実行経路の数」を表しており、ホワイトボックステストにおいてすべてのルートを網羅するために最低限必要な「テストケースの数」を決定する目安としても利用されます。

① 循環的複雑度 (Cyclomatic Complexity / サイクロマティック複雑度)
② 時間計算量 (Time Complexity)
③ 結合度 (Coupling)
④ 認知複雑度 (Cognitive Complexity)

2. 正解：

正解： ① 循環的複雑度 (Cyclomatic Complexity)

3. 解説：「分岐の数」を数えて、コードの危険度を見抜く

プログラミングにおいて、`if` 文や `switch` 文、`while` などのループが何重にも重なったコードは、バグが生まれやすくレビューも困難になります。この「ごちゃごちゃ度」を誰が見ても客観的にわかる数字にしたのが循環的複雑度です。

【循環的複雑度の計算方法と基準値】

・簡単な計算の目安：プログラムのフローチャート（制御フローグラフ）を書かなくても、実は簡単な数式で求められます。
$$ 循環的複雑度 = 条件分岐の数 + 1 $$
例えば、関数の中に `if` 文が3つあれば、複雑度は $$ 3 + 1 = 4 $$ になります。 ← ココが問題の正解！

・運用のガイドライン：一般的に、1個の関数（メソッド）におけるこの複雑度の数値が「10以下」なら非常にシンプルで安全、「20を超えると」バグが混入しやすく危険、「50以上」は絶対に分割すべき（スパゲティコード）と評価されます。

[ 選択肢のシャッフル解説（複雑さやプログラム品質に関する指標） ]
★ ② 時間計算量：アルゴリズムの性能を表す指標で、データ量が大きくなったときに、処理にかかる時間がどれくらい増えるかを「$O(n)$」などのビッグオー記法で表すものです。
★ ③ 結合度：モジュール（プログラムの部品）同士が、どれくらい強くお互いに依存し合っているかを表す度合いです。値が低い（疎結合である）ほど良いコードとされます。
★ ④ 認知複雑度：循環的複雑度の弱点（`switch`文などで単純に数値が跳ね上がる点）を補うために作られた新しい指標です。「人間がコードを読んだときに、どれくらい脳に負担がかかるか（ネストの深さなどを重視）」を測定します。

1. 理解のコツ: 「ドライブのルート（分かれ道）」に例えてみましょう。
・一本道のドライブコースなら、迷う要素はゼロです（複雑度＝1）。
・しかし、途中に「右に行くと海岸、左に行くと山」という交差点（`if`文）が3箇所あったら、ルートの組み合わせが生まれます。この『分かれ道の多さをカウントして、すべてのルートを走り切るために最低何回のドライブ（テストケース）が必要か』を弾き出すのが循環的複雑度です。分かれ道が多い道ほど、事故（バグ）が起きやすいのは当然ですよね。
2. 試験対策の視点: 「条件分岐やループに基づく複雑さ」「独立した実行経路の数」「テストケース数の決定に用いる」という記述があれば「循環的複雑度（サイクロマティック複雑度）」が一択です。基本情報の科目B（アルゴリズム問題）や、応用情報、高度試験（組込みやソフトウェア開発）の午前試験において、静的コード解析やホワイトボックステスト（パス網羅テスト）の設計手法のド真ん中として頻出する重要理論です。

---

4. まとめ

「プログラム内の条件分岐の数から論理的なルートの数を算出し、コードの品質や必要なテスト数を科学的に導き出すための指標」。これが循環的複雑度です。この指標を自動的にチェックするツールを開発プロセスに組み込むことで、現代のIT現場はスパゲティコードの誕生を未然に防いでいるのです。

【アルゴリズム】「何時までに届けろ」の制約を守れ！「時間窓付き巡回セールスマン問題」｜情報処理問題1000本ノック

ただ最速で回るだけでは、ビジネスの現場では役に立たない。顧客が指定した「約束の時間」をすべてクリアする超リアルな巡回アルゴリズムを攻略しましょう。

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

【 問題 】 巡回セールスマン問題（TSP）の派生問題の一つであり、各訪問先（都市や顧客）に対して「何時から何時の間に訪問しなければならない」という受け入れ可能な時間帯（制約条件）が設定されており、その制限をすべて満たしながら、全体の移動距離や所要時間を最小にする最適なルートを求める問題を何と呼ぶでしょうか？

① 時間窓付き巡回セールスマン問題 (TSPTW / Traveling Salesman Problem with Time Windows)
② 部分巡回セールスマン問題 (Orienteering Problem)
③ 中国人郵便配達問題 (Chinese Postman Problem)
④ 動的経路計画問題 (Dynamic Routing Problem)

2. 正解：

正解： ① 時間窓付き巡回セールスマン問題 (TSPTW)

3. 解説：「距離の短さ」と「時間の約束」を同時に解く難問

標準的な巡回セールスマン問題は、距離や時間が最短になる順番をパズルのように解くだけですが、そこに「午前中指定」「14時〜16時」といった実務の縛りを組み込んだのが時間窓付き巡回セールスマン問題（TSPTW）です。

【時間窓付き巡回セールスマン問題のアルゴリズム的難しさ】

・「時間窓（Time Window）」とは：各地点に設定された「ここから（開始時刻）ここまで（終了時刻）」という訪問許可時間のことです。 ← ココが問題の正解！

・計算の複雑さ：もし、ある家に指定時間より早く着きすぎてしまったら、その時間（時間窓の開始）になるまでその場で「待機」しなければなりません。逆に、ルートを効率化しようとするあまり1分でも遅れると、制約違反（大クレーム）になります。地理的に隣にある家であっても、時間の指定がバラバラだと効率的なルートが全く組めなくなるため、通常のTSPよりも遥かに計算が難しく、組み合わせが爆発します。

[ 選択肢のシャッフル解説（巡回・配送パズルのバリエーション） ]
★ ② 部分巡回セールスマン問題：以前学んだ問題です。時間や予算などの限られた資源の範囲内で、すべての都市ではなく、価値や得点が高い重要な地点を「厳選」して巡回し、スコアを最大化する問題です。
★ ③ 中国人郵便配達問題：すべての「地点（点）」ではなく、すべての「道路（辺）」を少なくとも1回は通って元の場所に戻る最短ルートを求める問題です。
★ ④ 動的経路計画問題：移動中にリアルタイムで発生する「渋滞情報」や「急な集荷依頼」などに応じて、その都度ルートを柔軟に再計算して変更していく問題です。

1. 理解のコツ: 「ネット通販の宅配ドライバーのルート作成」に例えてみましょう。
・地図だけを見て、15軒の家を一番一筆書きで綺麗に回れるルートを作るのが通常の巡回セールスマン問題です。
・しかし現実には、Aさんは『午前中指定（9時〜12時）』、Bさんは『夜間指定（19時〜21時）』という約束（時間窓）があります。Aさんの家に11時50分に滑り込み、その後他の家を回り、ちょうど19時過ぎにBさんの家に到着するよう、時間軸のパズルを完璧に組み立てるのが、この時間窓付き巡回セールスマン問題です。物流業界（ヤマト運輸やAmazonの配送網など）のルート自動生成システムでは、毎日このアルゴリズムが裏側でフル稼働しています。
2. 試験対策の視点: 「訪問時間に制限がある」「時間窓（タイムウィンドウ）」というキーワードがあれば「時間窓付き巡回セールスマン問題」が一択です。基本情報や応用情報の午前試験、さらには高度試験（システムアーキテクト等）において、物流DXや自動配車システムの数理モデル、あるいはAIによるスケジューリング最適化の文脈で、最も実用的かつ難度の高いアルゴリズム問題として注目されています。

---

4. まとめ

「移動距離のミニマム化という空間的なパズルに、各地点の『時間指定（時間窓）』という厳格な時間軸の制約を掛け合わせた、現代の物流システムを支える最重要の数理最適化問題」。これが時間窓付き巡回セールスマン問題です。これで巡回セールスマン問題の派生形も完璧に網羅できましたね！