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

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

तो, अगर इनपुट पसंद है

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

• q :=एक कतार डेटा संरचना

• q में डालें (शुरू करें, 1)

• विज़िट किया गया :=विज़िट किए गए नोड को होल्ड करने के लिए मानचित्र

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

  • (नोड, प्रोब) :=q का पहला आइटम और इसे q से हटा दें

  • अगर विज़िट किया गया [नोड]> जांच, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • अन्यथा,

    • विज़िट किया गया [नोड] :=जांच

  • g[नोड] में प्रत्येक आसन्न नोड 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