帰着

帰着 (reduction) はアルゴリズムを設計するときに最もよく使われるテクニックです。問題 \(X\) を問題 \(Y\) に帰着させると言った場合、それは \(Y\) を解くアルゴリズムをブラックボックス (サブルーチン) として使いながら \(X\) を解くことを意味します。帰着を考えるときに重要なのが、帰着の結果として出来上がる \(X\) を解くアルゴリズムの正しさを、ブラックボックスがどう問題 \(Y\) を解くかに依存させてはいけない点です。仮定してよいのは、ブラックボックスが \(Y\) を正しく解くということだけです。中で起こっていることは私たちには関係なく、誰か別の人の問題です。ブラックボックスが文字通り魔法によって動くと考えるとよいでしょう。

例えば前章で説明した農民の掛け算アルゴリズムは、正の整数の掛け算という問題を、足し算、mediation、パリティ検査という三つの簡単な問題に帰着させます。アルゴリズムは "正の整数" という抽象的なデータ型を今あげた三つの演算をサポートするものとして定義していますが、乗算アルゴリズムの正しさは正の整数の表現 (画線法、クレイトークン、バビロニアの六十進法、キープ、算木、ローマ数字、指、augrym stones、ゴバール数字、二進法、負の二進法、グレイコード、平衡三進法、黄金進法、 四分虚数進法) や演算の実装方法に依存していません。もちろん乗算アルゴリズムの実行時間は足し算、mediation、パリティ検査の実行時間によって変わります。しかしこれは正しさとは別の問題です。最も重要なこととして、帰着を考えておけば数字の表現を変えるだけで効率の良いアルゴリズムを得ることができます (画線法から位取り記数法に変える、のように)。

同様に Huntington-Hill のアルゴリズムは、下院議会の議席配分の問題を、 \(\textsc{Insert}\) と \(\textsc{ExtractMax}\) をサポートする優先度付きキューを管理することに帰着しています。ここで抽象データ型 "優先度付きキュー" はブラックボックスになっていて、配分アルゴリズムの正しさは優先度付きキューの特定の実装を仮定していません。もちろん、このアルゴリズムの実行時間は \(\textsc{Insert}\) と \(\textsc{ExtractMax}\) の実行時間によって変わります。しかしこれは正しさとは別の問題です。帰着が優れているのは、優先度付きキューといったデータ型の実装を効率の良いものに取り換えることで効率の良い配分アルゴリズムを得られる点です。さらに、優先度付きキューというデータ型の設計者はそのデータ型が下院議席の配分で使われることを気にせずに済みます。

アルゴリズムで使われている基本的な部品がどのように実装されているか、あるいは設計しているアルゴリズムがさらに大きな問題を解くときにどのような部品として使われるかを正確に知るのは不可能です。これは初心者にとって落ち着かないことかもしれませんが、これは避けられないばかりか、とても有用なことでもあります。アルゴリズムの中の部品がどう動くかを正確に知っているときでさえ、細部を無視することはとても有用です。