線形探索とはなにか？そのアルゴリズムをc++で学ぶ

線形探索とは、配列にような一列に並んだデータを先頭から一つづつ検索していくアルゴリズムのことです。

ランダムに並べられた数列から対象となる数字を検索したい場合は以下のように、
配列の先頭から最後尾まで、目的の数字を探索するプログラムを書きます。

// keyを探すプログラム
int key = 3;
int numbers[] = {2,4,6,8,1,3,5,9,7,10};
for(int i = 0;i < 10;++i){
  if(numbers[i] == key){
    return true;
  }
}

上記のプログラムでは、number[i] == keyにて、
一回のみ条件判定を行なっているように見えますが、
for文でi < 10の条件分岐を判定をしていることから、2回行なっています。
この条件判定を番兵と呼ばれる概念を使用することにより1回に減らすことができます。

番兵とは

データの終了を示すために配置される特殊なデータを指す
wikipediaより

では、データ終了を示すために配置される番兵を使って
線形探索を行なってみます。

データの終了を示すために、Keyとなる数字を配列の末尾に挿入します。 Keyを挿入しているということは、絶対にKeyは見つかります。
配列のindexが末尾まで到達していた場合Keyが見つからなかったことになるので、
この条件を使用することで、2回行われていた判定条件を一つにします。

int key = 3;
// 番兵として配列の末尾にKeyを挿入する
int numbers[] = {2,4,6,8,1,3,5,9,7,10,3};
int i = 0;
while(numbers[i] != key)i++;
// 末尾までいっていたら見つからなかったことになる
return i != 10;

上記のように番兵を使うことで条件分岐の回数を減らすことができました。
ほかの優秀なアルゴリズムがあるので、線形探索自体あまり使われませんが、
有効な考え方だと思いました。

幅優先探索のアルゴリズムをc++で学ぶ

幅優先探索のアルゴリズムを学びます。

幅優先探索はグラフで用いられるアルゴリズムで、深さ優先探索と対等してあげられることが多いようです。

深さ優先探索では、隣接するノードが見つかった場合、そのノードを探索しにいきますが、幅優先探索では、隣接ノードが見つかった場合でもそのノードを探索しにいこうとせず、他に隣接するノードがないかをチェックしにいきます。

幅優先探索のアルゴリズム図で学ぶ

幅優先探索のアルゴリズムを学んでいきましょう。
このグラフを幅優先探索にかけてみます。

 

1.ノード1をキューにいれる

1

2.ノード1を取り出して、ノード1に隣接している未訪問のノードをキューに入れます。

1 2

3.次にノード2を取り出して隣接しているノード3,4をキューにいれます。

1 2 3 4

4.つぎにノード3に隣接しているノードをチェックします。
ノード3はノード7に隣接しているので、7をキューに入れます。

1 2 3 4 7

5.次はノード4の隣接ノードを探索します、ノート2とノード5が隣接していますが、
ノード2は探索済みなので、キューには入れません。

1 2 3 4 7 5

6.以後、これを繰り返し、キューに入れた数(end)と、探索を開始する始点(head)が
一致した時点で探索終了です。

幅優先探索のアルゴリズムをc++で学ぶ

最後に、c++で書かれたプログラムを載せます。
ソースは上記のグラフを元にしたものです。

#include <queue>
using namespace std;

#define MAX 8
bool visited[MAX];

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,1,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,1,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

queue<int>q;

int main() {
    // queueに入れる
    q.push(0);
    visited[0] = true;
    
    do{
        int i = q.front();
        q.pop();
        for(int j = 0;j < MAX;++j){
            // 経路発見
            if(GRAPH[i][j] == 1 && !visited[j]){        
                printf("%d->%d ",i + 1,j + 1);
                q.push(j);
                visited[j] = true;
            }
        }
    }while(!q.empty());
}