SGCライブラリ - 14
探索のアルゴリズムと技法
基本的アプローチとその評価
伊庭斉志 著
2002年4月25日 初版発行
探索とは何か?
ナップザック問題(knapsack problem)
個の物があり、各々の重さ
と価値
が決まっている。
ナップザックには重量制限
があって、これより重い荷物は詰め込めない。
このとき、価値の和が最大になるように
個の物から選んでナップザックに詰め込む方法を求めよ。
問題の分類:
- 標準形
- 考える時間は十分にある。
- 物の重さと価値はわかっている。
- 部分情報の問題
- 物の価値や重さの一部がわからない。
- 実時間対応型問題
- 考える時間が限られている。
- ノイズのある問題
- 価値や重さがはっきりわからず、誤差や変動がある。
- 環境が動的な問題
- 価値がある時点で急に変わったり、重量制限が変わる。
基本的な探索の技法
線形探索
一次元の配列:
配列の中の所定の項目(target)を探索する:
とする。
- もし
ならば
を返す。
ならば「見つからない」と返す。
とする。
- 2 へ戻る。
計算時間は である。
ハッシュ法
ハッシュ関数:キーの集合 から番地の集合
への写像
:キー
から自然数への変換関数
にすでに情報が書かれていた場合(データの衝突):
- 直接チェイニング
- その場所を2つ以上のデータが入るように拡張する。
- オープン・アドレッシング
- 同じ配列内の別の空き場所を探して、後から加えたデータを入れる。
- リハッシュ関数
データ挿入:キー
とする。
によってキー
を変換したアドレスを求める。
- もし
のアドレスの記憶場所が空なら、データを挿入して終わり。
として 2 に戻る。
データ検索:キー
とする。
によってキー
を変換したアドレスを求める。
- もし
のアドレスの記憶項目が空ならエラーとなる。
- もし
のアドレスの記憶項目のキーが
であるなら、この項目を返す。
- さもなければ、
として 2 に戻る。
ソート法
配列 の中身を小さい順に並べ直す。
バブルソート
,
とする。
ならば
と
の中身を交換する。
とする。
- もし
ならば 2 へ戻る。
,
とする。
- もし
なら終了する。
- 1 へ戻る。
最悪の場合、交換の数は のオーダーとなる。
クイックソート
配列 に対して
(
)を分割値として選び、それ以上のものとそれ以下のものに分割して並べ替える操作:
,
,
とする。
である限り、
を実行する。
である限り、
を実行する。
- もし
ならば、
と
の内容を入れ替えて
,
とする。
- もし
なら終わり、さもなければ 2 に戻る。
クイックソート関数:
,
とし、
とする。
を実行する。
ならば、
を実行する。
ならば、
を実行する。
ヒープソート
ソーティングの対象となる配列を とすると、
親ノード
子ノード
となるような2分木を作ることによってソートを行う。
をソートすることを考える。
の整数部分
とする。
- もし
であれば
とし、
とする。さもなければ
,
,
とする。
ならば
として終了。
とする。
,
とする。もし
なら 5 へ、
なら 6 へ、
なら 8 へそれぞれ進む。
- もし
なら
とする。
なら 8 へ進む。
として 4 へ進む。
として 2 へ進む。
ソート法の比較
アルゴリズム | 最良値 | 平均値 | 最悪値 | |
---|---|---|---|---|
バブルソート | 交換回数 | |
|
|
比較回数 | |
|
|
|
クイックソート | |
? | |
|
ヒープソート | ? | ? | |