縮小法

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

縮小法

前項でやった分割統治法は、大きさnの問題をaコの問題に分割しようというものでした。
それによって問題がとってもわかりやすく解けたわけですけども、ただ「分割」しているだけなので『述べサイズ(実際に解く問題の大きさ)』は変わらないということです。

縮小法というのは、問題を分割し、一部の見込みない入力を捨て去ることによって問題の述べサイズをも減少させてしまおうという方法です。

定順位要素の抽出

といってもイメージが浮かばないと思うので『与えられた実数の集合S={x_1, x_2,\cdots, x_n}の中からk番目に小さい実数を抽出』するという問題を例にとって考えてみます。

そのアルゴリズムORDER(S,k)は以下の通りです。
1.|S|<100のとき、Sの要素をソートし、k番目の要素を取り出して終了する。
2.|S|\geq 100のとき
2.1. Sの要素を5個のグループに分けて、各グループの中から順位3番目のものを取り出します。取り出したものの集合をTとおきます。
2.2. m\leftarrow ORDER(T,[n/10])
2.3. Smより小さいものの集合S_1mに等しいものの集合S_2mより大きいものの集合S_3へ分割する。
2.4. if k\geq |S_1| then y\leftarrow ORDER(S_1,k);
   else if |S_1|<k\leq |S_1|+|S_2| then y\leftarrow m;
   else y\leftarrow ORDER(S_3,k-|S_1|-|S_2|)
2.5. return y

順を追って説明していきます。
1.について。これはもともと問題が小さいなら素直にソートして頑張ってね、という意味です。
2.以降は問題が大きい場合の方法について考えます。
2.1について、まずSを5人グループに分けます。そしてその5人グループの中で成績順に分けて、一番平凡な奴を各グループから持ってきます。この平凡組をTと言います。
2.2について、平凡組の人数はn/5なので、中央値はその半分、[n/10]番目の実数になります。ということでこの平凡組の中の平凡という超平凡野郎をmとして再帰的に取り出してきます。
2.3についてはそのままですね。超平凡野郎がおそらく平均点に近いので、それより低い人と高い人に分けます。

これで入力が分割できました。
例えばk=250(つまり250番目に低い奴を取ってこいという問題)で、|S_1|=300だったとしたら、絶対S_1に目的のやつがいるはずですね。
ですのでこの集合だけをまた再帰的に調べていこうというわけです。これが2.4のやっていることです。

このアルゴリズムは「余計なことをしない」という方法が上手くいっているのでO(n)のアルゴリズムになっています。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。
最終更新:2012年10月24日 09:56
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。