イントロダクション

このセクションでは、最適化問題 と 組合せ最適化問題、そしてそれらの背後にある 計算複雑性（計算量クラス／NP困難など） を理解することを目標とします。

量子アニーリングやメタヒューリスティクスといった応用的な話題に入る前に、

• 「そもそも最適化問題とは？」
• 「なぜ組合せ最適化問題は難しいと言われるのか？」
• 「NP困難って聞いたことあるけど、何が “困難” なのか？」

といった土台を揃えておくための導入として位置づけています。

---

このドキュメントの構成

本セクション、次の3つのページから構成されています。

1. 「最適化問題とは何か」
   最適化問題の基本的な定義、連続最適化問題と離散最適化問題の違い、QUBO形式などについて紹介します。 身近な例として勉強時間の配分を通じて、最適化問題の定式化の雰囲気 を理解することが目的です。

2. 「組合せ最適化問題」
   巡回セールスマン問題やナップサック問題など、代表的な組合せ最適化問題を取り上げながら、組合せ爆発 がなぜ起きるのか、そして厳密解法／近似解法・ヒューリスティクスといった 組合せ最適化問題の解き方の大きな分類を説明します。

3. 「【中級者向け】計算複雑性とNP困難」
   ビッグオー記法や最悪計算量、クラスP・クラスNP・NP完全・NP困難といった概念を紹介します。
   数学的な定義も登場するためやや中級者向けですが、「なぜ多くの実務的な最適化問題で厳密解を諦めるのか」 を理解する助けになります。

---

想定読者と前提知識

• 高校レベルの数学（関数・不等式・簡単な順列・組合せ）がなんとなく分かる方
• 機械学習・最適化・量子アニーリングなどに興味があり、「ちゃんと基礎から整理しておきたい」と感じている方

を主な対象としています。
数式は出てきますが、 途中の式変形をすべて追えなくても、文章と図からイメージが掴めるようになることを目標としています。

---

読み進め方のおすすめ

• 一通り流れを掴みたい場合
  → 1 → 2 → 3 の順に、まずはざっと読むのがおすすめです。
• 計算量やNP困難の話は後回しでよい場合
  → 1 と 2 を先に読み、必要になったタイミングで 3 に戻ってくる読み方も問題ありません。
• 数学的な定義が気になる場合
  → 3 の「ビッグオー記法」「クラスP／NP」のあたりを先に読むと、
  1・2章に出てくる「計算量」「難しさ」といった用語がよりクリアになります。

---

このイントロの先へ

ここで述べた内容はあくまで 「地図の概要」 に過ぎません。
詳しい中身は、次のページから順番に見ていきましょう。

• まずは、最適化問題とは何か、その基本的な形と具体例を確認します。
• 次に、組合せ最適化問題がなぜ難しいのか、その直感的な理由を掴みます。
• 最後に、計算複雑性とNP困難という視点から、問題の「本質的な難しさ」に踏み込みます。

それでは、「最適化問題とは何か」 から始めていきましょう。