【アルゴリズム】最悪のシナリオを最小限に抑える！「ミニマックス問題」｜情報処理問題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. まとめ
「複数の評価軸や目的関数が存在するとき、それぞれの選択肢における最大のリスクや損失（最大値）を評価し、その最大値が最も小さくなる選択肢を最適解として決定する手法」。これがミニマックス問題です。リスク管理やインフラ設計の基本思想となる重要な概念ですので、表の読み方をしっかりマスターしておきましょう！