1.探索アルゴリズムとは

「探索」とは、言葉の通り、探すことです。たとえば、英和辞典で「network」の意味を調べる際、膨大な単語の中から「network」という文字を探します。この探索方法ですが、思いつくのは、辞書の先頭ページから順番に探していく方法です(線形検索といいます)。でも、あまり効率的ではありませんよね。

そこで、べつの方法を考えます。辞書はアルファベット順に並んでいるので、辞書の真ん中の単語を探します。(たとえばmeanとします)。「network」が探した単語(mean)より前か後ろかを比較します(後ろですよね)。次は、後ろの部分の真ん中の文字を探し、「network」と比較します。こうして半分にしていって検索する方法が2分検索で、検索時間は線形検索に比べて少なくなります。

探索アルゴリズムには、主に以下の3つです。
・線形探索
・2分探索
・ハッシュ表探索

順に解説します。

2.線形探索

(1)線形検索とは

線形探索は、名前をつけるほどの探索技法ではなく、単に、先頭から順に探す方法です。もし、n個から1つを探索するときに、先頭に探したい値があれば、1回で見つけることができます。しかし、最後(n番目)にあれば、全部の値と比較する必要があり、比較回数はn回です。

よって、平均比較回数は(n+1)÷2 となり、nが大きくなると、比較回数はとても大きくなります。

(2)線形検索の過去問

■H26春AP
問6 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて,与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。
 ここで,検索する従業員番号はランダムに出現し,探索は常に表の先頭から行う。また,与えられた従業員番号がこの表に存在しない確率をaとする。

H26h-問6ans






【正解】エ

■H19春SW
問13 配列上に不規則に並んだ多数のデータの中から,特定のデータを探し出すのに適したアルゴリズムはどれか。
ア 2分探索法 ウ ハッシュ法
イ 線形探索法 エ モンテカルロ法







不規則に並んだデータは、線形検索しかできません

正解:イ

3.2分探索

(1)2分探索とは

冒頭の辞書の例で説明しましたが、データが大きい順または小さい順に並んでいる場合に、それを2分した中央値と比較していくことで、目的の値を探す方法です。

 
(2)2分探索をやってみよう!!
2分探索のシンプルな例を考えましょう。
100個の要素が入っている配列Aがあったとします。
配列Aは、昇順に並んでいます。

配列A[100]={1,3,7,8,12,20,22・・・}

ここで、20という数字がどこ(何番目)にあるかを探します。
1つ1つ頭から比較していくのが逐次検索(線形検索)です。
これは、非常に時間がかかります。最大、100回比較をする必要があります。
そこで、2分探索です。
真ん中の値と比較します。
ここからは、H23秋AP午前問8を参考に進めます。

変数の説明
in:探索値(検索する値。今回は75)
sch:検索が見つかった場合の添え字(配列の何番目か)。初期値は、見つかっていないという意味で-1
left:探索する左端の添字の値。初期値は0
right:探索する右端の添字の値。初期値はn-1
center:探索する配列の中央値の添字
※中央値が小数になった場合、小数は切り上げまたは切り捨て。

■アルゴリズム
分かりやすく、
配列A[7]={1,3,7,8,12,20,22}
でやってみましょう。

①初期値のセット
・in←20 (探索する20を入れる)
・sch←-1
・left←0
・right←6

②中央値との比較・・・見つかるまでループ

・中央値をセット
center←(left + right)/2=3
・中央値と比較
 X[center]:in X[3]=8とin=20を比較
 inの方が大きいので、次は、centerとrightの中央値を取って比較する。
  X[center]<in であれば、leftにcenterの値を入れる(left←center)。このとき、centerとは一致していなかったので、center+1とする方が効率的。
 left=4
 center←(4+6)/2=5 として、再度ループ
  X[center]:in X[5]=20とin=20を比較。等しいので、もとめるschにcenterを入れる。sch←center
 
■アルゴリズム
ではこれを、nを使って作り上げます。
①初期値のセット
・in←20 (探索する20を入れる)
・sch←-1
・left←0
・right←n-1

②中央値との比較・・・見つかるまで(sch=-1のまま)ループ、または探索範囲がなくなったとき(たとえば、left>right)も実施★この部分は後で解説。

・中央値をセット
center←(left + right)/2
・中央値と比較
 X[center]:in 
search
さて、★の検索条件です。設問にもなっています。正解は、left<=rightです。ポイントは、left=rightの場合も含むということです。
どんな場合があるか、試してみましょう。
X[2]={1,3} ※X[0],X[1]
left←0
right←1
in=3
center←(0+1)/2=0.5 ・・・0とする
X[0](=1)とin(=3)を比較し、X[0]<inであるため、right=center-1=0としてループが続きます。

4.ハッシュ探索

過去問(H21春AP午後問2)では、「配列に対して,データを格納すべき位置(配列の添字)をデータのキーの値を引数とする関数(ハッシュ関数)で求めることによって,探索だけではなく追加や削除も効率よく行うのがハッシュ法である。」とあります。
aae62d2c

なんだかよく分かりませんね。
たとえば、ハッシュ関数によって、演算した結果(たとえば10で割った余り)をデータを保存する番地にしてしまうのです。
324、543、127、99、875などとデータが並んでいるとしてハッシュ値を番地にすると以下のようになります。

番地  値
3   543
4   324
5   875
7   127
9    99

今回は数字にしていますが、英単語を調べる辞書と思えばいいでしょう。543という英単語を調べたいとき、その情報がどこにあるか。543をハッシュ演算すると3になります。3番地を見ればいいと分かります。つまり、どれだけ数があっても、1回で探索できるのです。
ただ、衝突があるので、そこが注意点です。

このあとの過去問(H25春AP午前問5)に「コードから一意に決まる場所に格納した探索表」とあります。ハッシュ関数を用いて、コードから一意に決まる場所に値を格納する探索方法と考えてもいいでしょう。

ハッシュ探索の問題は以下です。

■H27秋
問5 キーが小文字のアルファベット1文字(a,b,…,zのいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファペット順にコードとして割り当てられている。
ア aとi     イ bとr     ウ cとl     エ dとx





アルファベットのASCIIコードおよび1の位の数は次のようになります。
アルファベット ASCIIコード 1の位の数
   a    97   7
   b    98   8
   c    99   9
   d    100   0
   ・・・
   i    105   5
   ・・・
   r    114   4
   ・・・
   x    120   0
ただ、ASCIIコードを覚えている人はいないことでしょう。
2つも文字がいくつ離れているのかを考えれば衝突するかがわかります。dとxは、20離れていて、ハッシュ関数は、1の位の数を用いているので、衝突することがわかります。
【正解】エ

■H27春
問5 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(r)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x  mod nはxをnで割った余りを表す。
ア a+bがnの倍数
イ a-bがnの倍数
ウ nがa+bの倍数
エ nがa-bの倍数






【正解】イ

■H26春
問19 ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。

H26h-問19






【正解】エ

■H25秋
問7 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x mod n はxをnで割った余りを表す。
ア a+bがnの倍数   ウ nがa+bの倍数
イ a-bがnの倍数    エ nがa-bの倍数





【正解】イ
 

5.探索アルゴリズムの過去問

(1)H25春AP午前問5
問5 探索表の構成法を例とともにa~cに示す。最も適した探索手法の組合せはどれか。
  ここで,探索表のコードの空欄は表の空きを示す。
H25h-問5





a:コード順に並んでいるので、2分検索が使えます
b:使用頻度順ということは、つまり、バラバラということです。よって、線形検索しか使えません。

【正解】ア

(2)H24秋FE問3
問3 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダが,nの2乗であるとは、n個のデータを処理する時間がc×nの2乗(cは定数)で抑えられることをいう。

 2分探索  線形探索 ハッシュ探索
ア log2n    n      1
イ nlog2n    n     log2n
ウ nlog2n    n2     1
工 n2乗     1    n

まず、ここでいうオーダとは探索する最大時間と考えてください。
まあ、計算する上では「最大実行回数」で考えるといいです。探索する時間=回数×1回の処理時間です。なのせ、1回の処理時間がここでいうcと考えればいいでしょう。
862492bc

問題文の最後の意味がよく分かりません。なぜnの2乗?
これもあくまでも一例です。表のnの2乗があるので、それを例にしているだけです。余談ですが、nの乗数が一番多いものに左右されますよね。
では答を考えましょう。線形探索でn個の数を順番に探していくと、運が悪いと最大n回かかります。なので、線形探索のオーダはnです。探索時間にすると、この場合はc×nになります。
ハッシュ探索は常に1です。

正解:ア