近似アルゴリズムとは（全体像）
近似アルゴリズムは、最適解を求めるのが大変な問題に対して、最適ではないが十分良い解を、速く（多項式時間で）出す手法のこと。
身近な例がカーナビ。世界一の最短経路をきっちり計算しようとすると時間がかかりすぎる。そこで「真の最適ではないが、十分速い経路」を一瞬で出す。これが近似の発想だ。
押さえたいのは、ただ適当に解くのではなく、「最適からどれくらいズレるか」を保証すること。たとえば「最適の2倍以内」と分かっていれば、迷わず使える。この保証があるのが近似アルゴリズムの特徴だ。
詳しく：近似比とメタヒューリスティックとの違いだけ覚えれば戦える
ここが記事の心臓部。良さの指標が近似比だ。
近似比の意味
| 言葉 | 意味 |
|---|---|
| 近似比 | 出した解が最適解の何倍かを表す目安（最小化問題では1に近いほど良い） |
| 2-近似 | 出した解が最適の2倍以内に収まる保証 |
| 代表例 | 巡回セールスマン問題や頂点被覆の2-近似 |
たとえば2-近似なら、どんな入力でも「最適の2倍以内」が保証される。巡回セールスマン問題や頂点被覆などに、こうした近似アルゴリズムがある。
よく対比されるのがメタヒューリスティック（遺伝的アルゴリズムなど）。こちらも良い解を探す手法だが、大きな違いがある。
メタヒューリスティックとの違い
| 近似アルゴリズム | メタヒューリスティック | |
|---|---|---|
| 近似比の保証 | ある（最適の○倍以内と言える） | ない（経験的に良い解を探す） |
| 特徴 | 理論的な保証つき | 保証はないが幅広い問題に使える |
つまり、近似アルゴリズムは「最適からのズレを保証する」、メタヒューリスティックは「保証はないが良い解を探す」。この保証のあり・なしが、いちばんの違い、というわけだね。
わかりやすく言い換えると
要するに、近似アルゴリズムは「完璧でなくても、十分良い解を速く・保証つきで出す」やり方だ。
①目的 … 最適が大変な問題に、そこそこ良い解を速く出す（カーナビの経路）
②近似比 … 最適からどれくらいズレるかの保証（2-近似＝最適の2倍以内）
③メタヒューリスティックとの違い … 近似は保証あり、メタヒューリスティックは保証なし
「速いだけ」でなく「ズレの保証がある」のが近似アルゴリズムのポイント。
試験のツボ
🔴 一番出る：最適でなくてもよい解を速く出す
①NP困難など、最適が大変な問題が対象
②多項式時間で、そこそこ良い解を出す
🔴 次に出る：近似比
①最適の何倍かを表す目安（小さいほど良い）
②2-近似＝最適の2倍以内に収まる保証
🟡 押さえると安定：メタヒューリスティックとの違い
①近似アルゴリズムは近似比の保証がある
②メタヒューリスティックは保証なし（経験的に探す）
よくある間違い
①「近似アルゴリズムは必ず最適解を出す」→ ✗ 出すのは最適ではなく、保証された範囲内の良い解。
②「2-近似は最適の半分しか出せないという意味」→ ✗ 最適の2倍以内に収まるという保証。半分ではない。
③「メタヒューリスティックも近似比が必ず保証される」→ ✗ メタヒューリスティックは保証なし。保証があるのは近似アルゴリズム。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（近似アルゴリズムの目的）
近似アルゴリズムに関する次の記述のうち、正しいものはどれか。
- 近似アルゴリズムは、どんな問題でも必ず最適解そのものを出すための手法とされる
- 近似アルゴリズムは、最適が大変な問題にそこそこ良い解を速く出す手法のことだ
- 近似アルゴリズムは、わざと悪い解を選んでなるべく遅く答えを出すための手法だ
- 近似アルゴリズムは、答えをいっさい出さず、問題が難しいかどうかを調べるだけだ
解答は 2 だよ。
近似アルゴリズムは最適が大変な問題に、そこそこ良い解を速く出す手法なんだ。カーナビの経路探索のイメージだよ。
選択肢1の「必ず最適解」、選択肢3の「わざと悪い解」、選択肢4の「答えを出さない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最適ではなく良い解を出す |
| 2 | ✓ | そこそこ良い解を速く出す |
| 3 | ✗ | 良い解を速く出す |
| 4 | ✗ | ちゃんと解を出す |
オリジナル問題2（近似比）
近似比に関する次の記述のうち、正しいものはどれか。
- 2-近似とは、出した解が最適の半分しか達成できないことを保証する意味だとされる
- 近似比は最適解とはなんの関係もなく、入力の大きさだけで決まる値のことである
- 2-近似とは、出した解が最適の2倍以内に収まることを保証するという意味である
- 近似比は数値では表せず、良いか悪いかを見た目で判断するだけのものとされている
解答は 3 だよ。
2-近似は「出した解が最適の2倍以内に収まる」という保証なんだ。近似比は最適の何倍かを表す目安で、小さいほど良いよ。
選択肢1の「半分しか」、選択肢2の「最適と無関係」、選択肢4の「見た目で判断」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 2倍以内であって半分ではない |
| 2 | ✗ | 最適との比で決まる |
| 3 | ✓ | 最適の2倍以内の保証 |
| 4 | ✗ | 数値で表す |
オリジナル問題3（メタヒューリスティックとの違い）
近似アルゴリズムとメタヒューリスティックの違いに関する次の記述のうち、正しいものはどれか。
- 近似アルゴリズムは近似比の保証があり、メタヒューリスティックは保証がない
- 近似アルゴリズムは保証がなく、メタヒューリスティックは必ず最適解を出すものだ
- どちらも近似比が必ず保証され、両者にはなんの違いも存在していないものとされる
- どちらも保証がなく、当てずっぽうで答えを出すだけの手法であるとされている
解答は 1 だよ。
近似アルゴリズムは近似比の保証がある、メタヒューリスティックは保証がないんだ。この「保証あり・なし」がいちばんの違いだよ。
選択肢2は保証の有無が逆。選択肢3の「違いがない」、選択肢4の「当てずっぽう」はどちらも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 近似は保証あり・メタは保証なし |
| 2 | ✗ | 保証の有無が逆 |
| 3 | ✗ | 保証の有無で違う |
| 4 | ✗ | 近似比の保証があるものもある |
まとめ
押さえどころ
- 🔴 目的 ＝ 最適が大変な問題に、そこそこ良い解を多項式時間で出す。
- 🔴 近似比 ＝ 最適の何倍かの目安。2-近似は最適の2倍以内の保証。
- 🟡 メタヒューリスティックとの違い ＝ 近似アルゴリズムは保証あり、メタヒューリスティックは保証なし。
次に学ぶ
執筆: SikakuQuest編集部