わかりやすく 近似アルゴリズム とは

完璧はいったん置いておく

難しい問題があります。完璧な答えを見つけるにはすべての場合を調べなければならず、その数はとほうもありません。
最後まで行けば、たしかにいちばんよい答えは出ます。でも、それはいつ終わるのでしょうか。
押して数えてみましょう。

完璧な答えを最後まで調べるとこうなります。（場合の数がふくらんで時間が爆発 → 終わりが見えない）

数があまりにも速くふくらみます。少し増えるだけで、調べることが何倍にもなります。
だから完璧な答えを最後まで待つのは、現実的でないこともあります。だからといって、手をこまねいているわけにもいきません。

十分によい答えを、速く

ここで一つの考えがあります。必ずしも最高でなくてもかまわないとしたら、どうでしょう。
完璧をねらうかわりに、さっと「そこそこよい答え」を出してみるのです。貪欲でやったように、目の前のよいものをてきぱき選んでいきながら。

速いざっくりした答え vs 完璧な答え。（ざっくりした答えはあっという間 · 差はわずか）

ざっくりした答えはあっという間に出たのに、完璧な答えとあまり差がありません。
少し足りないけれど、十分使えます。多くの場合、これで十分です。

どれくらいよいかを保証する

でも、一つ心配があります。「そこそこよい答え」を信じてよいのでしょうか。もしとても悪い答えだったらどうしましょう。
そこで賢い方法は、約束もいっしょに出します。「この答えは、最高よりそれほど悪くはならない」という約束です。

最適の1.5倍以内を保証します。（どんな答えが出てもこの線の内側 → 最悪がふさがれている）

これが本当にすばらしいところです。「最適の1.5倍以内」のように線を引いておけば、答えがどんなに悪くても、その線を越えられません。
完璧ではなくても、どれだけ足りなくなりうるかを私たちは正確に知っています。ばくぜんとした推測とはまったく違います。

正確さと時間を交換する

結局、これはてんびんです。時間を多く使えば答えはより正確になり、時間を節約すれば答えは少し粗くなります。
どちらがよいとは一概に言えません。急ぐなら速いほう、精密さが必要なら正確なほうです。
ボタンで時間を増やしたり減らしたりして、二つのあいだを選んでみましょう。

時間を多く使えばより正確に、少なく使えばより粗く。（どこで止めるかは私たちが選ぶ）

このてんびんは、アルゴリズム全体を貫く心です。速い道と正確な道、簡単な道と念入りな道。
私たちは毎回、何を手放して何を得るかを選んできました。よい方法を知るとは、このてんびんをうまく読むことです。

ここまで来た道

長い道を歩いてきました。順番どおりに解くことから始めて、並べ、探し、コストを測り、分け、つなぎ、選びました。
本当に難しい問題があることも、それでも十分によい答えがあることも見ました。
押して、その道を一度に振り返りましょう。

この領域がくれた四つのものを順にまとめます。（よい方法 · 速さ · 戦略 · 限界を知って折り合う）

すべての問題を完璧に解くことはできません。でも、それは無力だという意味ではありません。
速い方法と賢い戦略を使い、限界を知って上手に折り合えば、難しい問題を前にしても使える答えを手にできます。
それが、アルゴリズムが私たちにくれる力です。