পাইথন ব্যবহার করে সর্বাধিক সম্ভাব্যতার সাথে পথ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের n নোড সহ একটি অনির্দেশিত ওজনযুক্ত গ্রাফ রয়েছে (নোডগুলিকে 0 থেকে নম্বর দেওয়া হয়েছে), এই গ্রাফটি প্রান্ত তালিকা ব্যবহার করে ইনপুট হিসাবে দেওয়া হয়েছে, প্রতিটি প্রান্ত e এর জন্য, এটিতে সেই প্রান্তের সম্ভাব্যতা [e] অতিক্রম করার সাফল্যের সম্ভাবনা রয়েছে। আমাদের স্টার্ট এবং এন্ড নোডও আছে, শুরু থেকে শেষ পর্যন্ত যাওয়ার জন্য এবং সফলতার সম্ভাব্যতা ফিরিয়ে দেওয়ার জন্য আমাদের সাফল্যের সর্বাধিক সম্ভাবনা সহ পথটি খুঁজে বের করতে হবে। যদি আমরা কোন পথ খুঁজে না পাই, তাহলে 0 ফেরত দিন।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 0.24 কারণ নোড 0 থেকে 2 পর্যন্ত দুটি পাথ রয়েছে, একটি সম্ভাব্যতা 0.2 সহ, আরেকটি নোড 1 এর মাধ্যমে সম্ভাব্যতা 0.4*0.6 =0.24, এটি সর্বাধিক।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• g :=প্রদত্ত প্রান্ত তালিকা থেকে গ্রাফ তৈরি করুন এবং সম্ভাব্যতা মানটিকে ওজন হিসাবে ব্যবহার করুন

• q :=একটি কিউ ডেটা স্ট্রাকচার

• q

  -এ সন্নিবেশ (শুরু, 1)

• পরিদর্শন করা হয়েছে :=পরিদর্শন করা নোড ধরে রাখার জন্য একটি মানচিত্র

• q খালি না থাকার সময়, করুন

  • (নোড, প্রোব) :=q এর প্রথম আইটেম এবং q

    থেকে মুছে দিন

  • যদি [node]> prob পরিদর্শন করা হয়, তাহলে

    • পরবর্তী পুনরাবৃত্তির জন্য যান

  • অন্যথায়,

    • পরিদর্শন [নোড] :=সমস্যা

  • প্রতিটি সংলগ্ন নোড adj এবং সম্ভাব্যতা nextProb-এর জন্য g[node], do

    • যদি পরিদর্শন করা হয় [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