Pythonを使用して最大の確率でパスを見つけるプログラム

n個のノード（ノードには0から番号が付けられます）を持つ無向加重グラフがあるとします。このグラフは、エッジリストを使用して入力として与えられ、各エッジeについて、そのエッジ確率[e]を通過する成功の確率があります。開始ノードと終了ノードもあります。最初から最後まで成功の確率が最大のパスを見つけて、成功の確率を返す必要があります。パスが見つからない場合は、0を返します。

したがって、入力が次のような場合

ノード0から2へのパスが2つあるため、出力は0.24になります。1つは確率0.2、もう1つはノード1を経由するパスの確率は0.4 * 0.6 =0.24で、これが最大です。

これを解決するには、次の手順に従います-

• g：=与えられたエッジリストからグラフを作成し、確率値を重みとして使用します

• q：=キューのデータ構造

• （start、1）をqに挿入します

• 訪問済み：=訪問済みノードを保持するマップ

• qが空でない間、実行します

  • （node、prob）：=qの最初のアイテムで、qから削除します

  • 訪問した場合[ノード]>確率、その後

    • 次のイテレーションに行く

  • それ以外の場合

    • 訪問済み[ノード]：=確率

  • g [node]の隣接するノードadjと確率nextProbごとに、実行

    • 訪問した場合[adj]

      • qの最後に（adj、prob * nextProb）を挿入します

• 訪問した[終了]

理解を深めるために、次の実装を見てみましょう-

例

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