마르코프 체인 그래프 g가 있다고 가정합니다. 우리는 시간 t =0일 때 상태 S에서 시작하면 시간 T에서 상태 F에 도달할 확률을 찾습니다. 우리가 알다시피 마르코프 체인은 다양한 상태와 한 상태를 다른 상태로 이동할 확률로 구성된 무작위 프로세스입니다. 이것은 유향 그래프로 나타낼 수 있습니다. 노드는 상태이고 에지는 한 노드에서 다른 노드로 이동할 확률이 있습니다. 한 상태에서 다른 상태로 이동하는 데 단위 시간이 걸립니다. 나가는 가장자리의 확률의 합은 모든 노드에 대해 하나입니다.
따라서 입력이 N =6, S =4, F =2, T =100인 경우 출력은 0.28499144801478526
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
table :=크기가 (N+1)x(T+1)이고 0.0으로 채워진 행렬
-
테이블[S, 0] :=1.0
-
범위 1에서 T까지의 i에 대해 수행
-
범위 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