একটি মার্কভ চেইনে একটি নির্দিষ্ট সময়ে একটি রাষ্ট্রের সম্ভাব্যতা খুঁজুন - পাইথনে 1 সেট করুন

ধরুন আমাদের একটি মার্কভ চেইন গ্রাফ আছে; আমরা যদি সময় টি =0 অবস্থায় রাজ্য S থেকে শুরু করি তাহলে T সময়ে F রাজ্যে পৌঁছানোর সম্ভাবনা খুঁজে পাব। যেমনটি আমরা জানি একটি মার্কভ চেইন হল একটি এলোমেলো প্রক্রিয়া যা বিভিন্ন রাজ্যের সমন্বয়ে গঠিত এবং এক রাজ্যে অন্য রাজ্যে যাওয়ার সম্ভাবনা। এটি একটি নির্দেশিত গ্রাফ হিসাবে উপস্থাপন করা যেতে পারে; নোডগুলি হল রাজ্য এবং প্রান্তগুলির একটি নোড থেকে অন্য নোডে যাওয়ার সম্ভাবনা রয়েছে। এক রাজ্য থেকে অন্য রাজ্যে যেতে একক সময় লাগে। বহির্গামী প্রান্তগুলির সম্ভাব্যতার সমষ্টি প্রতিটি নোডের জন্য একটি৷

সুতরাং, যদি ইনপুট হয় N =6, S =4, F =2, T =100, তাহলে আউটপুট হবে 0.28499144801478526

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

• টেবিল :=আকারের একটি ম্যাট্রিক্স (N+1)x(T+1) এবং 0.0 দিয়ে পূরণ করুন

• টেবিল[S, 0] :=1.0

• 1 থেকে T রেঞ্জের জন্য, করুন

  • 1 থেকে N রেঞ্জে j এর জন্য, করুন

    • G[j]-এ প্রতিটি k-এর জন্য করুন

      • টেবিল[j, i] :=টেবিল[j, i] + k[1] * টেবিল[k[0], i - 1]

• রিটার্ন টেবিল[F, T]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def get_probability(G, N, F, S, T):
   table = [[0.0 for j in range(T+1)] for i in range(N+1)]
   table[S][0] = 1.0
   for i in range(1, T+1):
      for j in range(1, N +1):
         for k in G[j]:
            table[j][i] += k[1] * table[k[0]][i - 1]
   return table[F][T];
graph = []
graph.append([])
graph.append([(2, 0.09)])
graph.append([(1, 0.23),(6, 0.62)])
graph.append([(2, 0.06)])
graph.append([(1, 0.77),(3, 0.63)])
graph.append([(4, 0.65),(6, 0.38)])
graph.append([(2, 0.85),(3, 0.37), (4, 0.35), (5, 1.0)])
N = 6
S, F, T = 4, 2, 100
print(get_probability(graph, N, F, S, T))

ইনপুট

6, 4, 2, 100

আউটপুট

0.28499144801478526