C++プログラマへの道 #17 - 探索アルゴリズム

このブログ記事では、C++で主な探索アルゴリズムを紹介します。

検索はデータ構造における最も基本的で重要な操作の1つであり、データの集合から特定のデータを見つけることを可能にします。 Googleを開いてウェブサイトを検索したり、ウェブサイトにログインしたり、購入履歴を確認したりする際には、すべての段階で検索が関わっています。これまでいくつかの検索アルゴリズムについて言及してきましたが、この記事では、配列やグラフにおける基本的な検索アルゴリズムを詳細に取り上げます。

配列の検索

配列は、データを連続的に格納する最も基本的なデータ構造であり、配列に対して最適な検索アルゴリズムを見つけることはパフォーマンス向上の鍵となります。ここでは、線形探索と二分探索という2つの検索アルゴリズムを紹介します。

線形探索

最も直感的な検索アルゴリズムは線形探索で、左端の要素から始めて、指定されたデータが見つかるまで右方向に進んでいきます。これは単純なforループとして記述でき、インデックスを1つずつ増やしながら、そのインデックスに格納されている値が指定されたデータと一致するかを確認します。（逆方向の検索も線形探索に含まれます。）線形探索の時間計算量は $O(n)$ です。

二分探索

線形探索は基本的に非常に効率的ですが、配列がソートされている場合に限り、より効率的な方法が使えます。それが二分探索です。二分探索は中央から始め、要素が指定されたデータよりも小さいか大きいかを確認します。もし要素が小さい場合、右半分が指定されたデータよりも大きいと分かっているため、探索範囲を左半分に絞ります。その逆の場合も同様です。このように探索範囲を半分ずつ削減しながら指定されたデータを見つけるまで繰り返します。

二分探索木（BST）とその派生データ構造は、要素を整理して、左部分木と右部分木が常に親ノードより小さく、または大きくなるように構成することで、二分探索を可能にします。BSTに関する記事、C++プログラマへの道 #10 - 連想コンテナで計算したように、二分探索の時間計算量は $O(log(n))$ であり、 $O(n)$ よりも優れています。木構造を使用する利点は、挿入や削除の時間計算量が配列（ $O(n)$ ）よりも良い $O(log(n))$ である点ですが、メモリ使用量が多く、メモリが連続している保証がない点が欠点です。

グラフにおける探索

グラフはノードと、他のノードを指すポインタ(エッジ)で構成されるデータ構造です。リンクリストや木構造も特定のプロパティ（階層構造や厳密な子ノード数など）を持つグラフの特別な種類です。グラフは、輸送ネットワークやソーシャルネットワーク、化学構造など、さまざまな関係を柔軟に表現できるため、グラフにおける探索は非常に重要です。

グラフにおける探索は配列の場合とは異なり、グラフには開始ノードから目的ノードまでの複数のパスや、パスが存在しない場合があります。そのため、探索の目的は、パスを見つけること、または最適なパスを見つけることになります。各ノードに複数のエッジが存在するため、アルゴリズムはどのエッジを優先的に探索するか、またはエッジを選択する戦略を決定する必要があります。本記事では、主に 深さ優先探索（Depth First Search, DFS） と 幅優先探索（Breadth First Search, BFS） という2つの戦略を紹介します。

幅優先探索

幅優先探索（BFS）は、同じレベル（開始ノードから同じ距離にあるすべてのノード）のノードをすべて調べてから、次のレベルのノードを探索します。つまり、最初に子ノードをすべてチェックし、その後に孫ノード、さらにその次のレベルのノードへと進み、目的のノードを見つけるまで続けます。このアプローチは、訪問済みのノードを適切に管理することで、有限グラフにおいて探索が必ず終了し、最短経路をたどることが保証されます。以下は、AdjacencyList におけるBFSの実装例です。

#include <queue>
#include <unordered_set>
 
using namespace std;
 
int BFS(AdjacencyList al, int start, int goal) {
    queue<int> q;
    unordered_set<int> explored;
    q.push(start);
    explored.insert(start);
    while (!q.empty()) {
        int front = q.front();
        cout << "To explore: " << front << endl;
        if (front == goal) {
            cout << "Found!" << endl;
            return 1;
        }
        for (list<int>::iterator it = al.li[front].begin(); it != al.li[front].end(); ++it) {
            int i = *it;
            if (explored.find(i) == explored.end()) {
                q.push(i);
                explored.insert(i);
            }
        }
        q.pop();
    }
    cout << "Not Found:(" << endl;
    return 0;
};
 
int main() {
    AdjacencyList al(5);
    al.addEdge(0, 1);
    al.addEdge(0, 2);
    al.addEdge(1, 3);
    al.addEdge(2, 4);
    BFS(al, 2, 6); // => Not Found:(
    BFS(al, 0, 4); // => Found!
    return 0;
}

同じレベルのノードを探索してから次のレベルに移るために、FIFO（先入れ先出し）を強制するキューを利用できます。グラフが無向またはサイクルを持つ場合は、すでに訪問したノードをすべて追跡する必要があり、これは unordered_set を使用して実現できます。すべてのノードとエッジが最悪の場合に探索されるため、時間計算量は $O(|V| + |E|)$ （ここで $V$ はノード数、 $E$ はエッジ数）です。また、キューと unordered_set の両方が最悪の場合にすべてのノードを格納する必要があるため、空間計算量は $O(V)$ です。

深さ優先探索

もう1つのアプローチとして、1つの枝を最深部に到達するまで探索する方法があります。これを深さ優先探索（DFS）と呼びます。 DFSを実行するには、キューの代わりにスタックを使用します。（AdjacencyList におけるDFSの実装は、演習問題として提示されています。） DFSの時間計算量と空間計算量はそれぞれ $O(|V| + |E|)$ と $O(V)$ ですが、DFSは一般的にBFSよりも少ない空間を使用します。 DFSでは探索中の経路上のノードのみがスタックに格納される一方で、BFSでは前のレベルにあるすべてのノードがキューに格納されるためです。ただし、DFSは探索が終了することや最短経路を保証しないため、空間に余裕がある場合は一般的にBFSが優先されます。

結論

本記事では、異なるデータ構造における探索アルゴリズムとその計算量について考察しました。また、特定のタスクに適したデータ構造を選択する重要性についても観察しました（これまでのシリーズ記事でも継続的に触れています）。例えば、バイナリ探索は高速である傾向がありますが、ソート済み配列やBST（Binary Search Tree）を維持することは計算的または空間的にコストがかかる場合があります。同様に、BFSは常に最適ではありません。DFSはスタックに格納するノードが少ないため、メモリ消費が少なくて済む場合があります。さまざまな問題に適した他のグラフ探索アルゴリズムも数多く存在するため、今後の記事でさらに詳しく探求していきます。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

Q1: AdjacencyListに対して深さ優先探索（DFS）を実行するアルゴリズムを定義してください。