NP困難問題への近似アルゴリズムと近似比

厳密解を諦め、保証付きで妥協する

NP困難な最適化問題は、P≠NP を前提とする限り多項式時間で厳密最適解を求める一般手法が存在しないと考えられます。そこで方針を変え、「最適ではないが、最適からどれだけ離れているかを数学的に保証した解」を多項式時間で返すのが近似アルゴリズムです。問題の難しさ自体は 計算量クラス P・NP と NP完全性 で扱った通りで、本記事はその先の「ではどう折り合うか」を担います。

ヒューリスティックとの決定的な違いは保証の有無です。焼きなましや遺伝的アルゴリズムは速くて実用的でも「最悪どれだけ悪化するか」を言えません。近似アルゴリズムは最悪ケースに対して比を約束します。

鍵は「下界（または上界）の見積もり」

近似比の証明は、ほとんどの場合最適値そのものは分からないまま行います。OPT が計算できるなら厳密に解けてしまうからです。代わりに、最小化なら「OPT はこれ以上小さくなりえない」という下界を多項式時間で計算できる量から押さえ、その下界と自分の解を比較して比を導きます。この「下界をどう取るか」が近似アルゴリズム設計の核心です。

頂点被覆 ― 極大マッチングで2近似

頂点被覆問題は、グラフのすべての辺について少なくとも一方の端点を含むような、最小サイズの頂点集合を求める問題です（判定版はNP完全）。素朴に「最も次数の高い頂点から貪欲に選ぶ」とlog因子の近似に留まりますが、マッチングを使うと定数で抑えられます。

極大マッチングによる2近似:
  C = 空集合
  while 未被覆の辺 (u,v) が残る:
      C に u と v の両方を追加
      u, v に接続する辺をすべて被覆済みにする
  return C

選んだ辺の集合は互いに端点を共有しない極大マッチング M を成します。ここで下界が効きます。M のどの辺も最低1つは端点を被覆に入れねばならず、辺同士は端点を共有しないので OPT ≥ |M|。一方アルゴリズムは各辺で2頂点を取るので |C| = 2|M|。よって |C| = 2|M| ≤ 2·OPT、すなわち2近似が保証されます。

TSP ― 三角不等式の有無で世界が変わる

巡回セールスマン問題（TSP）は条件次第で近似可能性が一変します。

一般のTSP（辺重みが任意）は、定数近似アルゴリズムが存在すれば P=NP になることが証明されており、事実上どんな定数比でも近似できません。ところが距離が三角不等式 d(a,c) ≤ d(a,b) + d(b,c) を満たす計量TSP（metric TSP）に限ると、状況は劇的に良くなります。

• 二重木法（2近似）: 最小全域木（MST）を構築し、各辺を2回辿るオイラー周遊を作り、三角不等式を使って重複頂点を飛ばしショートカットする。任意の巡回路から1辺除けば全域木になるので MST ≤ OPT、周遊は 2·MST、ショートカットは三角不等式により増えないので ALG ≤ 2·MST ≤ 2·OPT。MST の構築は 最短経路・全域木アルゴリズム と同じ貪欲の枠組みです。
• Christofides 法（1.5近似）: MST に対し、奇数次数頂点だけの最小重み完全マッチングを足してオイラーグラフ化する。マッチングのコストが 0.5·OPT 以下に抑えられることを示せ、合計で 1.5·OPT を達成。長らく計量TSPの最良の定数近似でした。

集合被覆 ― 貪欲で対数近似、そしてその限界

集合被覆問題は、全体集合 U と部分集合の族が与えられ、U を覆う最小個数の部分集合を選ぶ問題です。ここでの定石は貪欲法で、毎回「まだ覆われていない要素を最も多く新規に覆う集合」を選びます。考え方は 貪欲法と最適性の証明 と同根です。

この貪欲は H(n) ≈ ln n 近似を達成します（H は調和数、n は要素数）。証明は、各ステップで残り未被覆要素のうち少なくとも 1/OPT の割合を覆えること（最適解の集合の平均を下回らないため）を使い、未被覆数が幾何級数的に減ることから対数因子を導きます。

近似可能性による問題の階層 ― PTAS と APX

近似のしやすさで最適化問題を分類すると、難しさの地図がもう一段精密になります。

• PTAS（Polynomial-Time Approximation Scheme）: 任意の固定した ε > 0 に対し、1+ε 近似（最大化なら 1-ε）を多項式時間で返すアルゴリズム群。実行時間は固定 ε のもとで n に対し多項式ですが、1/ε が n の指数に現れてもよく（例 O(n^(1/ε))）、ε を小さくするほど急激に重くなり得ます。精度をいくらでも上げられる「最良級」の問題です。ユークリッド平面のTSPや、同一機械上のメイクスパン最小化（スケジューリング）がここに入ります。
• FPTAS（Fully PTAS）: さらに強く、実行時間が n と 1/ε の両方の多項式。ナップサックが代表例で、値を丸める動的計画法で実現します。
• APX: 何らかの定数近似比を多項式時間で達成できる問題のクラス。頂点被覆や計量TSP、MAX-3SAT などが該当します。

包含関係は FPTAS ⊆ PTAS ⊆ APX です。そして P≠NP を仮定すると、これらは真に分かれます。たとえば頂点被覆は APX に属しますが PTAS は持たない（APX困難）ことが知られ、定数 1.3606 より良い比は近似不可能と示されています。さらに上には、最大クリークのように n^(1-ε) より良くは近似できない、ほぼ近似不能な問題群があります。

設計の型として持ち帰る

近似アルゴリズムは個別の技ではなく、共通の型に還元できます。第一に「OPT に対する計算可能な下界（最小化）または上界（最大化）を見つける」、第二に「自分の解をその下界と比べて比を出す」。頂点被覆ならマッチング、TSPなら最小全域木、集合被覆なら各ステップの被覆率がその下界でした。NP困難に直面したら、厳密解の探索（分枝限定法）か、近似比つきの妥協か、入力を制限してPに落とすかを天秤にかける ―どの問題がどこまで近似できるかの地図は アルゴリズム設計パラダイムの地図 と合わせて持っておくと、判断が速くなります。