SGCライブラリ - 14

探索のアルゴリズムと技法

基本的アプローチとその評価

伊庭斉志　著

2002年4月25日　初版発行

探索とは何か？

ナップザック問題（knapsack problem）

${N}$ 個の物があり、各々の重さ ${w_i}$ と価値 ${p_i}$ が決まっている。

ナップザックには重量制限 ${W}$ があって、これより重い荷物は詰め込めない。

このとき、価値の和が最大になるように ${N}$ 個の物から選んでナップザックに詰め込む方法を求めよ。

問題の分類：

標準形
- 考える時間は十分にある。
- 物の重さと価値はわかっている。
部分情報の問題
- 物の価値や重さの一部がわからない。
実時間対応型問題
- 考える時間が限られている。
ノイズのある問題
- 価値や重さがはっきりわからず、誤差や変動がある。
環境が動的な問題
- 価値がある時点で急に変わったり、重量制限が変わる。

基本的な探索の技法

線形探索

一次元の配列： ${A[1],A[2],\dots,A[N]}$

配列の中の所定の項目（target）を探索する：

${i := 1}$ とする。
もし ${A[i] = \mathrm{target}}$ ならば ${i}$ を返す。
${i = N}$ ならば「見つからない」と返す。
${i := i + 1}$ とする。
2 へ戻る。

計算時間は ${O(N)}$ である。

ハッシュ法

ハッシュ関数：キーの集合 ${K}$ から番地の集合 ${C}$ への写像 ${H: K \to C}$

${C[0],C[1],\dots,C[N - 1]}$
${H(k) = \mathrm{ord}\,(k)\bmod N}$
${\mathrm{ord}}$ ：キー ${k}$ から自然数への変換関数

${C[H(k)]}$ にすでに情報が書かれていた場合（データの衝突）：

直接チェイニング
- その場所を２つ以上のデータが入るように拡張する。
オープン・アドレッシング
- 同じ配列内の別の空き場所を探して、後から加えたデータを入れる。
- リハッシュ関数 ${h_i}$
- ${h_0 = H(k)}$

データ挿入：キー ${k}$

${i := 0}$ とする。
${h_i}$ によってキー ${k}$ を変換したアドレスを求める。
もし ${h_i}$ のアドレスの記憶場所が空なら、データを挿入して終わり。
${i := i + 1}$ として 2 に戻る。

データ検索：キー ${k}$

${i := 0}$ とする。
${h_i}$ によってキー ${k}$ を変換したアドレスを求める。
もし ${h_i}$ のアドレスの記憶項目が空ならエラーとなる。
もし ${h_i}$ のアドレスの記憶項目のキーが ${k}$ であるなら、この項目を返す。
さもなければ、 ${i := i + 1}$ として 2 に戻る。

ソート法

配列 ${A[1],A[2],\dots,A[N]}$ の中身を小さい順に並べ直す。

バブルソート

${k := N}$ , ${J := 1}$ とする。
${A[k - 1] \gt A[k]}$ ならば ${A[k - 1]}$ と ${A[k]}$ の中身を交換する。
${k := k - 1}$ とする。
もし ${k \gt J}$ ならば 2 へ戻る。
${J := J + 1}$ , ${k := N}$ とする。
もし ${J = N}$ なら終了する。
1 へ戻る。

最悪の場合、交換の数は ${O(N^2)}$ のオーダーとなる。

クイックソート

配列 ${A[L],A[L + 1],\dots,A[R]}$ に対して ${A[k]}$ （ ${L \le k \le R}$ ）を分割値として選び、それ以上のものとそれ以下のものに分割して並べ替える操作： ${\mathrm{Part}\,(A[L],A[L + 1],\dots,A[R];k)}$

${i := L}$ , ${j := R}$ , ${x := A[k]}$ とする。
${A[i] \lt x}$ である限り、 ${i := i + 1}$ を実行する。
${A[j] \gt x}$ である限り、 ${j := j -1}$ を実行する。
もし ${i \le j}$ ならば、 ${A[i]}$ と ${A[j]}$ の内容を入れ替えて ${i := i + 1}$ , ${j := j - 1}$ とする。
もし ${i \gt j}$ なら終わり、さもなければ 2 に戻る。

クイックソート関数： ${\mathrm{Qsort}\,(l,r)}$

${i := l}$ , ${j := r}$ とし、 ${k := \lceil (l + r) / 2\rceil}$ とする。
${\mathrm{Part}\,(A[l],A[l + 1],\dots,A[r];k)}$ を実行する。
${l \lt j}$ ならば、 ${\mathrm{Qsort\,(l,j)}}$ を実行する。
${i \lt r}$ ならば、 ${\mathrm{Qsort\,(i,r)}}$ を実行する。

ヒープソート

ソーティングの対象となる配列を ${k}$ とすると、 ${k[}$ 親ノード ${] \lt k[}$ 子ノード ${]}$ となるような２分木を作ることによってソートを行う。

${k[1],k[2],\dots,k[n]}$ をソートすることを考える。

${l := \frac{n}{2}}$ の整数部分 ${+ 1}$ とする。
もし ${l \gt 1}$ であれば ${l := l - 1}$ とし、 ${z := k[l]}$ とする。さもなければ ${z := k[r]}$ , ${k[r] := k[1]}$ , ${r := r - 1}$ とする。 ${r = 1}$ ならば ${k[1] := z}$ として終了。
${j := l}$ とする。
${i := j}$ , ${j := 2j}$ とする。もし ${j \lt r}$ なら 5 へ、 ${j = r}$ なら 6 へ、 ${j \gt r}$ なら 8 へそれぞれ進む。
もし ${k[j] \lt k[j + 1]}$ なら ${j := j + 1}$ とする。
${z \ge k[j]}$ なら 8 へ進む。
${k[i] := k[j]}$ として 4 へ進む。
${k[i] := z}$ として 2 へ進む。

ソート法の比較

アルゴリズム		最良値	平均値	最悪値
バブルソート	交換回数	${\frac{N^2 - N}{2}}$	${\frac{N^2 - N}{2}}$	${\frac{N^2 - N}{2}}$
	比較回数	${0}$	${\frac{3}{4}(n^2 - n)}$	${\frac{3}{2}(n^2 - n)}$
クイックソート		${O(N\log N)}$	?	${O(N^2)}$
ヒープソート		?	?	${O(N\log N)}$