Pythonで最大の成功確率を持つパスを見つけるプログラムの実装方法

問題の概要

n 個のノード(ノードには 0 から順に番号が振られています)からなる無向重み付きグラフを考えます。このグラフは辺リスト(edge list)として入力され、各辺 e には「その辺を通過する際の成功確率」probability[e] が割り当てられています。さらに、開始ノード(start)と終了ノード(end)も与えられます。

求めたいのは、start から end へ移動するときに成功確率が最大となる経路であり、答えとしてその成功確率を返します。経路がひとつも存在しない場合は 0 を返してください。

たとえば、次のような入力が与えられたとします。

この場合の出力は 0.25 になります。ノード 0 からノード 2 への経路は2つあり、ひとつは確率 0.2 の直接の辺、もうひとつはノード 1 を経由する経路で、確率は 0.5 × 0.5 = 0.25 となります。後者の方が大きいため、これが答えです。

解法のアプローチ

各辺の確率を掛け合わせた値が最大になる経路を探す問題です。幅優先探索(BFS)をベースにしつつ、「各ノードに到達したときの最良の確率」を記録し、それより悪い候補を枝刈りすることで効率よく解けます。

具体的には、以下の手順に従います。

• g := 与えられた辺リストから隣接リスト形式のグラフを作成し、確率値を重みとして格納する

• q := キュー(deque)データ構造を用意する

• (start, 1) を q に挿入する(開始時点の確率は 1)

• visited := 各ノードの最良確率を記録するためのマップ

• q が空でない限り、以下を繰り返す

  • (node, prob) := q の先頭要素を取り出して削除する

  • もし visited[node] > prob なら、より良い確率で既に訪問済みなので次の反復へ進む

  • そうでなければ、visited[node] := prob と更新する

  • g[node] 内の各隣接ノード adj とその確率 nextProb について、visited[adj] < prob × nextProb であれば、(adj, prob × nextProb) を q の末尾に挿入する

• 最後に visited[end] を返す

この手法のポイントは、確率の積を最大化するという点にあります。通常の最短経路問題が距離の和を最小化するのに対し、ここでは積を最大化するため、重みにマイナス対数を取ればダイクストラ法としても解くことができます。ただし、上記の BFS + 枝刈りの実装でも十分に動作します。

実装例

以下の実装を見ると、理解がさらに深まるでしょう。

from collections import defaultdict, deque
def solve(edges, probability, start, end):
    g = defaultdict(list)
    for i in range(len(edges)):
        src, dst = edges[i][0], edges[i][1]
        prob = probability[i]
        g[src].append((dst, prob))
        g[dst].append((src, prob))
    q = deque()
    q.append((start, 1))
    visited = defaultdict(int)
    while q:
        node, prob = q.popleft()
        if visited[node] > prob:
            continue
        else:
            visited[node] = prob
        for adj, nextProb in g[node]:
            if visited[adj] < prob * nextProb:
                q.append((adj, prob * nextProb))
    return visited[end]
edges = [[0,1],[1,2],[0,2]]
probability = [0.5,0.5,0.2]
start = 0
end = 2
print(solve(edges, probability, start, end))

入力

[[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2

出力

0.25

まとめ

このアルゴリズムの計算量は、最悪の場合 O(V × E) 程度になります(同じノードが複数回キューに入る可能性があるため)。優先度付きキュー(ヒープ)を使って常に現時点で最良の確率を持つノードから処理するようにすれば、ダイクストラ法と同様の O(E log V) まで改善できます。確率の掛け算で経路を評価するこの考え方は、ネットワークの信頼性解析や推薦システムなど、さまざまな分野で応用できる有用なテクニックです。