C++プログラマへの道 #18

このブログ記事では、C++でダイクストラ法とA*探索を紹介します。

前回の記事では、グラフ探索に使用される2つのアルゴリズムであるBFS（幅優先探索）とDFS（深さ優先探索）について説明しました。これらのアルゴリズムは、グラフに関する事前情報がない場合でも使用できる無情報探索の例です。今回の記事では、重み付きグラフにおける無情報探索であるダイクストラ法と、グラフに関する事前知識を利用する有情報探索であるA*探索を紹介し、議論を深めていきます。

ダイクストラ法

ダイクストラ法は、重み付きグラフを対象とした無情報探索アルゴリズムで、エッジに対応する重みが設定されています。この重みは、例えば移動時間のように、あるノードから別のノードへ移動するコストを表します。このアルゴリズムは、目的地への総コストを最小化することを目指しており、他の経路よりもコストが低い場合には、より多くのステップを経由して目的地に到達することもあります。ダイクストラ法の主な戦略は、探索中にそのノードまでの最小コストを更新し続けることです。その際、最も低コストで到達可能なノードを優先的に探索します。以下は、重み値を含めるように修正した隣接行列（AdjacencyMatrix）に対するダイクストラ法の実装例です。

void Dijkstra (WeightedAdjacencyMatrix graph, int start, int end) {
    cout << "Look for path between " << start << " to " << end << endl;
    // Initial Estimate
    vector<int> estimates(graph.mat.size(), 100);
    unordered_set<int> explored;
    int current = start;
    estimates[start] = 0;
    explored.insert(start);
 
    while (current != end) {
        cout << "To Explore: " << current << endl;
        vector<int> edges = graph.mat[current];
        // Update the estimate
        for (int e = 0; e < edges.size(); e++) {
            int new_estimate = estimates[current] + edges[e];
            if (edges[e] != 0 && new_estimate < estimates[e]) {
                estimates[e] = new_estimate;
            }
        }
        // Choose the unexplored minimum from estimates and explore
        int min = 200;
        int min_id;
        for (int i = 0; i < estimates.size(); i++) {
            if (explored.find(i) == explored.end()) {
                if (estimates[i] < min) {
                    min = estimates[i];
                    min_id = i;
                }
            }
        }
        current = min_id;
        explored.insert(min_id);
    }
 
    // Computed Cost
    cout << "Min cost is " << estimates[end] << endl;
};

あまりよく分からない方は、Spanning Tree（2020）のHow Dijkstra's Algorithm Worksという動画をぜひご覧になることをお勧めします。 C++には無限大を表す値がないため、ここでは重みが0から10の範囲内であると仮定して、上限値として100を使用しています。このアルゴリズムは、いずれかのエッジが負のコストを持つ場合には機能しません。なぜなら、コストを削減する経路が存在しないことを確認するためには、全てのノードを訪問する必要があるからです。このアルゴリズムはシンプルながら、追加情報なしで重み付きグラフの目的地までの最短経路を特定することが可能です。上記のコード実装から、ダイクストラ法の時間および空間計算量はそれぞれ $O(V^2)$ と $O(V)$ であることが導き出せます。

A*探索

ダイクストラ法の問題点を挙げるとすれば、それは目的地の頂点から離れた方向にも探索が進む可能性がある点です。特に、隣接するエッジの重みが目的地方向に最小でない場合に発生します。目的地の方向に関する情報がある場合、この探索を正しい方向へ誘導することで、信頼性のある最短経路を見つけることが可能です。A*探索は、BFSやダイクストラ法を拡張したもので、グラフに関する事前知識（ヒューリスティック関数）を利用します。この関数は、目的地までの近さを測定します。通常、ヒューリスティックにはユークリッド距離やマンハッタン距離が使用され、グラフの頂点の座標を用いて計算されます。

次に探索する頂点の選択基準はダイクストラ法と同じで、最小のコスト推定値を持つものを選びます。ただし、A*探索ではコスト推定値にヒューリスティック値を加算することで、探索を正しい方向へ誘導します。

void AStarSearch (WeightedAdjacencyMatrix graph, int start, int end, vector<int> heuristics) {
    cout << "Look for path between " << start << " to " << end << endl;
    // Initial Estimate
    vector<int> estimates(graph.mat.size(), 100);
    unordered_set<int> explored;
    int current = start;
    estimates[start] = 0;
    explored.insert(start);
 
    while (current != end) {
        cout << "To Explore: " << current << endl;
        vector<int> edges = graph.mat[current];
        // Update the estimate
        for (int e = 0; e < edges.size(); e++) {
            int new_estimate = estimates[current] + edges[e];
            if (edges[e] != 0 && new_estimate < estimates[e]) {
                estimates[e] = new_estimate;
            }
        }
        // Choose the unexplored minimum from estimates and explore
        int min = 200;
        int min_id;
        for (int i = 0; i < estimates.size(); i++) {
            if (explored.find(i) == explored.end()) {
                if (estimates[i] + heuristics[i] < min) {
                    min = estimates[i] + heuristics[i];
                    min_id = i;
                }
            }
        }
        current = min_id;
        explored.insert(min_id);
    }
    // Computed Cost
    cout << "Min cost is " << estimates[end] << endl;
};
 
int main () {
    WeightedAdjacencyMatrix mat(7);
    mat.addEdge(0, 2, 3);
    mat.addEdge(0, 5, 2);
    mat.addEdge(1, 3, 1);
    mat.addEdge(1, 4, 2);
    mat.addEdge(1, 5, 6);
    mat.addEdge(1, 6, 2);
    mat.addEdge(2, 3, 4);
    mat.addEdge(2, 4, 1);
    mat.addEdge(2, 5, 2);
    mat.addEdge(4, 5, 3);
    mat.addEdge(5, 6, 5);
    int hValues[] = {4, 0, 3, 1, 2, 3, 1};
    vector<int> heuristics (hValues, hValues + sizeof(hValues) / sizeof(int)) ;
    AStarSearch(mat, 0, 1, heuristics);
    return 0;
};

このアルゴリズムを観察すると、ダイクストラ法との唯一の違いは、次に探索する頂点を選ぶ際にヒューリスティック値を加える点であることが分かります。地図ナビゲーションのようにヒューリスティック関数を利用できるケースでは、目的地の方向に近づきながら、十分な探索を行うことが可能です。最小限の変更であるため、A*探索の時間および空間計算量もダイクストラ法と同じ $O(V^2)$ と $O(V)$ ですが、適切なヒューリスティック関数がある場合には、ダイクストラ法よりも反復回数が少なくなることが多いです。

Spanning Tree. 2020. How Dijkstra's Algorithm Works. YouTube.

ダイクストラ法

A*探索

結論

クイズ

リソース

ダイクストラ法

A*探索

結論

クイズ

Q1: 始点から終点までの最短経路を特定するようにDijkstraを修正してください。

リソース