ความน่าจะเป็นสถานะ Markov Chain ที่เวลา T
กำหนด Markov Chain เป็นกราฟมีทิศทาง โหนด = สถานะ ขอบ = ความน่าจะเป็นการเปลี่ยนสถานะ (ผลรวมขอบออกจากโหนด = 1) ใช้เวลา 1 หน่วยต่อการเคลื่อนที่ หาความน่าจะเป็นไปถึงสถานะ F ที่เวลา T เริ่มจาก S ที่เวลา 0
Dynamic Programming O(N * T * E)
dp[state][time]= ความน่าจะเป็นอยู่ที่stateที่เวลาtime- Base:
dp[S][0] = 1 - Transition:
dp[v][t] = Σ dp[u][t-1] * P(u→v)สำหรับทุกขอบu→v - คำตอบ =
dp[F][T]
โค้ดตัวอย่าง Python
def get_probability(G, N, F, S, T):
dp = [[0.0]*(T+1) for _ in range(N+1)]
dp[S][0] = 1.0
for t in range(1, T+1):
for v in range(1, N+1):
for u, prob in G[v]: # G[v] = list of (neighbor, prob) entering v? ต้องตรวจสอบทิศทาง
dp[v][t] += prob * dp[u][t-1]
return dp[F][T]
# Graph representation: G[v] = list of (u, prob) where u -> v
# ตัวอย่างจากโจทย์ (อาจต้องปรับทิศทางขอบให้ถูกต้อง)
graph = [[] for _ in range(7)]
graph[1].append((2, 0.09))
graph[2].append((1, 0.23)); graph[2].append((6, 0.62))
graph[3].append((2, 0.06))
graph[4].append((1, 0.77)); graph[4].append((3, 0.63))
graph[5].append((4, 0.65)); graph[5].append((6, 0.38))
graph[6].append((2, 0.85)); graph[6].append((3, 0.37)); graph[6].append((4, 0.35)); graph[6].append((5, 1.0))
N, S, F, T = 6, 4, 2, 100
print(get_probability(graph, N, F, S, T)) # 0.28499144801478526
