पायथन का उपयोग करके अधिकतम संभावना वाले पथ को खोजने का प्रोग्राम

मान लीजिए हमारे पास n नोड्स वाला एक अनिर्देशित भारित ग्राफ है (नोड्स 0 से क्रमांकित हैं)। यह ग्राफ एज लिस्ट के रूप में दिया गया है, प्रत्येक एज e के लिए, उस एज को पार करने की सफलता की संभावना probability[e] है। हमारे पास प्रारंभ और अंत नोड्स भी हैं, हमें प्रारंभ से अंत तक जाने के लिए अधिकतम सफलता संभावना वाले पथ को खोजना है और उसकी सफलता संभावना वापस करनी है। यदि कोई पथ नहीं मिलता है, तो 0 वापस करें।

उदाहरण के लिए, यदि इनपुट इस तरह है:

तो आउटपुट 0.24 होगा क्योंकि नोड 0 से 2 तक दो पथ हैं, एक की संभावना 0.2 है, दूसरा नोड 1 के माध्यम से है जिसकी संभावना 0.4 * 0.6 = 0.24 है, यह अधिकतम है।

हल करने के चरण

• g := दिए गए एज लिस्ट से ग्राफ बनाएं और संभावना मान को वजन के रूप में उपयोग करें

• q := एक क्यू डेटा संरचना

• (start, 1) को q में डालें

• visited := विज़िट किए गए नोड को रखने के लिए एक मैप

• जब तक q खाली नहीं है, करें

  • (node, prob) := q का पहला आइटम लें और इसे q से हटाएं

  • यदि visited[node] > prob, तो

    • अगले इटरेशन के लिए जाएं

  • अन्यथा,

    • visited[node] := prob

  • g[node] में प्रत्येक आसन्न नोड adj और संभावना nextProb के लिए, करें

    • यदि visited[adj] < prob * nextProb, तो

      • (adj, prob * nextProb) को q के अंत में डालें

• visited[end] वापस करें

उदाहरण

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