はじめに
探索アルゴリズムとは
この記事を読んでくださっている方の中には、そもそもアルゴリズムってなんだろう？と思っている方もいると思います。
アルゴリズムとは、問題を解決するための手順・計算方法のことです。
例えば、大学受験を考えてみましょう。
大学に合格するためには勉強をしなければいけません。大学に受かるための勉強のやり方（アルゴリズム）はたくさんあります。そのアルゴリズムを教えてくれるのが学校や塾といった場所になります。
その中でも探索アルゴリズムは基本となるアルゴリズムのひとつで、データ群の中から条件に一致するデータを見つけるアルゴリズムのことを指します。
探索アルゴリズムを学ぶ意義
・処理の高速化（効率化）
データの特性に合ったアルゴリズムを実装することによって、処理速度が速くなります。
・読解しやすいコードを書ける
定式化された読解しやすいコードを書くことによって、保守性を向上させることができます。
リストの探索
線形探索
線形探索は先頭から順に、条件と照らし合わせながら調べていくアルゴリズムです。探索アルゴリズムの中で最も基本的なアルゴリズムだと言われています。
イメージ
[1,12,34,3,17,9,22]というデータ群から17を探し出す場合で説明します。
解説
1. データの先頭の要素「1」が探している「17」と同じかどうか調べる。違うので次の要素へ
2. 次の要素「12」が探している「17」と同じかどうか調べる。違うので次の要素へ
3. 次の要素「34」が探している「17」と同じかどうか調べる。違うので次の要素へ
4. 次の要素「3」が探している「17」と同じかどうか調べる。違うので次の要素へ
5. 次の要素「17」が探している「17」と同じかどうか調べる。目的のデータと合致したので探索終了。
（目的のデータが見つからない場合はリストの最後まで探索を行う。）
目的のデータある場所によって処理時間が変わってしまうため、目的のデータが最後にある場合には処理に時間がかかってしまいます。
計算量はO(N)です。
計算量
計算量(時間計算量)とは計算にかかる処理時間を表しています。アルゴリズムの性能を評価する指標の一つです。
計算量を記述するときにはオーダー記法（O記法）を使用します。
例えば、O(N)の場合は、処理時間がデータの数（N）に比例することを表します。
二分探索
整列されたデータ群を二つに分け、どちらに目的のデータがあるかを繰り返し判断していくことで探索を行うアルゴリズムです。
イメージ
[0,1,3,9,12,17,22,28,34,46]というデータ群から22を探し出す場合で説明します。
解説
（もしも、リスト内の要素がソートされていない場合はソートする）
1. まず、真ん中の要素（今回は真ん中がないため1つ左の要素）「12」と探している「22」を比較する。
（データを二つに分けて、真ん中がなかった場合は、1つ左の要素 or 1つ右の要素と目的のデータを比べる。）
2. 「22」よりも「12」の方が小さかったため「12」から左側には「22」が存在しないことがわかる。
3. 次に、右側の5つのデータの真ん中の要素「28」と探している「22」を比較する。
4. 「22」よりも「28」の方が大きかったため、「28」から右側には「22」が存在しないことがわかる。
5. 次に、残ったデータの真ん中（真ん中がないため1つ左の要素）「17」と探している「22」を比較する。目的のデータと違うの次へ
6. 残った要素「22」と探している「22」を比較する。目的のデータと合致したので探索終了。
線形探索よりも処理時間は短くなりますが、データ群が整列されている必要があるため、整列されていないデータ群で使用したい場合はソートアルゴリズムを使用してから行う必要があります。
計算量はO(logN)です。
木構造、グラフの探索
木構造やグラフといった階層のあるデータ構造では、リストでの探索とは違う方法を使います。
本記事では木構造を例として説明を行います。
木構造の要素部分をノード（節）、要素と要素のつながりをエッジ（枝）と呼びます。また、木構造の最初のノードをルートノード（根）、末端のノードはリーフノード（葉）と呼びます。
※この記事の以下では、ノードとエッジという呼称に統一します。
身近な木構造データ
Webスクレイピングを行う場合を考えてみます。
Webスクレイピングとは、ウェブサイトから必要な情報を取り出すコンピュータ技術のことです。その際、サイトのHTMLのどこに必要な情報があるのかを探索する必要があります。
HTMLではタグで文字列を挟んで、記述を行います。タグの中に複数のタグを入れることもでき、階層を持つ構造になります。
以下のHTMLのコードの一部を木構造の図として表してみます。
<html>
<head>
<title>タイトル</title>
</head>
<body>
<h1> 見出し </h1>
<p> 要素1 </p>
</body>
</html>
これを図に表すと
このように表せます。
このように、HTMLのような構造化された文書を、DOMツリーという木構造のデータとして読み込み、必要な要素を抽出するのが、スクレイピングの主なタスクになります。
深さ優先探索
グラフや木構造を探索する際に使われるアルゴリズムの一つです。
木構造のノードをそれ以上進むことができないところまで進み、探索していく方法です。
イメージ
木構造を使って説明します。
解説
1. まず、木構造のルートを探索する。目的のデータと合致しなければ次のノードへ
2. 1番左側のエッジを進み、探索を行う。目的のデータと合致しなければ次のノードへ
3. 同様にエッジを進み、探索を行う。目的のデータと合致しなければ次のノードへ。この操作をリーフノードに行き着くまで続ける。
4. リーフノードに行き着いたら、ルートノードに戻り、左から2番目のエッジを進み探索を行う。目的のデータと合致しなければ次のノードに進んでいく。リーフノードにたどり着くまで続ける。
5. 目的のデータを見つける or 全部のノードを調べ終わったら探索終了。
この場合の時間計算量はO(|E|)、空間計算量はO(|V|)です。
（|E|はグラフのエッジの数、|V|はグラフのノードの数）
空間計算量
空間計算量とは、探索を行う際に必要なメモリ量を表しています。
時間計算量同様、オーダー表記を使用して記述します。
メモリ量が小さいほど良いアルゴリズムだと言えます。
幅優先探索
グラフや木構造を探索する際に使われるアルゴリズムの一つです。
木構造のルートノード（Level1の部分）から近いレベルのノードを探索し、終わったら次のレベルの探索を行うという方法です。
イメージ
木構造を使って説明します。
解説
1. まず、木構造のルートノードを探索する。目的のデータと合致しなければ次のノードへ
2. Level2の1番左側のノードを探索し、目的のデータと合致しなければ次のノードへ
3. Level2の左から2番目のノードを探索し、目的のデータと合致しなければ次のノードへ
4. Level2の右側のノードを探索し、目的のデータと合致しなければ次のノードへ。Level2のノードは全て探索が終わったためLevel3に進む。
5. Level3の1番左側のノードを探索し、目的のデータと合致しなければ次のノードへ。レベルごとに順番に探索していく。
6. 目的のデータを見つける or 全部のノードを調べ終わったら探索終了。
時間計算量はO(|E|)、空間計算量はO(|V|)です。
まとめ
| 線形探索 | 二分探索 | 深さ優先探索 | 幅優先探索 | |
|---|---|---|---|---|
| 型 | リスト | リスト | 木構造 グラフ | 木構造 グラフ |
| 計算量 （時間計算量） | O(N) | O(logN) | O(|E|) | O(|E|) |
| 使う場面 | データ数が少ない場合 | データがソートされている場合 データ数が多い場合 | 木構造の幅が広い場合 深い部分に目的のデータがある場合 | 木構造の深さが深い場合 浅い部分に目的のデータがある場合 |
参考サイト
おわりに
今回は基本的な探索アルゴリズムの解説を行いました。
この他にもたくさんの種類のアルゴリズムが存在しているので、気になった方は調べてみると面白いかもしれません。
弊社では、経験の有無を問わず、社員やインターン生の採用を行っています。
興味のある方はこちらをご覧ください。