পাইথনে মার্কভ চেইনে নির্দিষ্ট সময়ে একটি স্টেটের প্রোব্যাবিলিটি বের করুন (সেট ১)

সমস্যা বিবরণ

একটি মার্কভ চেইন গ্রাফ g দেওয়া আছে। স্টেট S-থেকে সময় t=0-এ শুরু করে সময় T-এ স্টেট F-এ পৌঁছানোর প্রোব্যাবিলিটি বের করতে হবে। মার্কভ চেইন হলো একটি র‍্যান্ডম প্রসেস যেখানে স্টেটগুলো নোড এবং এজগুলোর ওয়েট হলো ট্রানজিশন প্রোব্যাবিলিটি। প্রতিটি ট্রানজিশনে ১ ইউনিট সময় লাগে। প্রতিটি নোডের আউটগোইং এজগুলোর প্রোব্যাবিলিটি যোগফল ১।

উদাহরণস্বরূপ, N=6, S=4, F=2, T=100 হলে আউটপুট 0.28499144801478526।

সমাধানের ধাপসমূহ

1. ডিপি টেবিল table[N+1][T+1] ০.০ দিয়ে শুরু করুন।
2. table[S][0] = 1.0।
3. i = 1 থেকে T পর্যন্ত:
   • j = 1 থেকে N পর্যন্ত:
     • প্রতিটি k in G[j] (নেক্সট স্টেট, প্রোব্যাবিলিটি) এর জন্য: table[j][i] += k[1] * table[k[0]][i-1]।
4. table[F][T] রিটার্ন করুন।

পাইথন কোড উদাহরণ

def get_probability(G, N, F, S, T):
    table = [[0.0 for _ in range(T+1)] for _ 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([])  # 0-index unused
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))  # আউটপুট: 0.28499144801478526

ইনপুট

6, 4, 2, 100

আউটপুট

0.28499144801478526