【基礎理論】全体がベストなら途中もベスト！「最適性の原理」｜情報処理問題1000本ノック
カーナビのルート探索や、複雑なAIの意思決定、アルゴリズムの高速化。難解に見える「最適化問題」をパズルのように分解して解くための大前提となる原理を攻略しましょう。
1. 【 問題 】：最適化問題とアルゴリズムの原理
【 問題 】 アルゴリズムや数理計画法（最適化問題）において、「ある出発点から目的地までの『最適な経路（最短ルートなど）』が決定されているとき、その経路の途中に含まれるどの部分的な区間（途中の2点間）をとっても、それはその区間における『最適な経路』でなければならない」という、動的計画法（Dynamic Programming）の基礎となる重要な概念・原理はどれでしょうか？
① ヘールの原理 (Pigeonhole Principle)
② 最適性の原理 (Principle of Optimality)
③ 排他中律の原理 (Law of Excluded Middle)
④ 局所性の原理 (Principle of Locality)
2. 正解：
正解： ② 最適性の原理（ベルマンの最適性原理）
3. 解説：大きな問題を「小さな問題のベスト」に分解する
最適化問題（最もコストが低い、または最も利益が高い選択肢を選ぶ問題）をコンピュータで効率よく解くための強力な武器が「動的計画法」です。そして、これが成り立つための大前提のルールが最適性の原理です。
・例えば、「東京 → 名古屋 → 大阪」というルートが、東京から大阪へ行く【全体として最も早いルート（最適経路）】だったとします。
・このとき、最適性の原理が言っているのは「だったら、途中の『東京 → 名古屋』という区間だけを切り取って見ても、それが東京から名古屋へ行くための【一番早いルート（部分最適）】になっているはずだ」ということです。 ← ココが問題の正解！
・もし、「東京 → 名古屋」に行くのにもっと早い別の裏道があったとしたら、最初の「東京 → 名古屋 → 大阪」は全体ベストではなかったことになり、矛盾してしまいます。
・この原理があるからこそ、コンピュータは「一気に全体のベストを探す」という大変な計算をしなくても、「手前の小さな区間のベストを順番に積み上げていく（動的計画法）」ことで、最終的に全体のベストな答えを導き出すことができます。
★ ① ヘールの原理（鳩の巣原理）：「$n$個の巣に $n+1$羽以上の鳩を入れると、必ず2羽以上が入る巣が少なくとも1つは存在する」という、データ圧縮の限界証明や組み合わせ数学で使われる基本原理です。
★ ③ 排他中律の原理（排中律）：論理学・不真理値において、「ある命題は真であるか、偽であるかのどちらかであり、その中間は存在しない」というルールです。
★ ④ 局所性の原理：以前にキャッシュメモリの解説で触れた、「プログラムがアクセスするデータや命令は、時間的・空間的に狭い範囲（局所）に集中しやすい」というコンピュータシステム構成の経験則です。
1. 理解のコツ: 「世界一おいしいコース料理（全体最適）」をイメージしてください。この原理は、「世界一のコースに含まれている『前菜（部分）』や『メイン（部分）』は、それぞれ単体で見ても、その価格帯・ジャンルの中で最高峰の逸品（部分最適）で構成されているはずだ」という考え方です。だからこそ、シェフは「各パーツで最高の料理」を開発して組み合わせることで、最高のコースを完成させることができます。
2. 試験対策の視点: 「ある経路が最適であるならば」「途中に含まれるすべての区間も最適」「最適化問題の原理」という数理的な性質が語られたら「最適性の原理」が一択です。基本情報や応用情報、さらには高度試験（システムアーキテクトやエンベデッドシステムなど）の午前試験において、アルゴリズムの設計思想や最短経路問題（ダイクストラ法など）の理論的背景を問う上級問題として狙われます。
4. まとめ
「全体にとっての最適解は、細分化されたすべての部分問題にとっても最適解を含んでいるという、最適化問題を効率よく解くための根本ルール」。これが最適性の原理です。この数学的な美しさがあるおかげで、カーナビの超高速なルート検索や、限られたリソースで最大の利益を出すスケジュールをコンピュータが一瞬で計算できるようになっています。