Dada una string de Markov G, tenemos la probabilidad de alcanzar el estado F en el tiempo t = T si comenzamos desde el estado S en el tiempo t = 0.
Una string de Markov es un proceso aleatorio que consta de varios estados y las probabilidades de moverse de un estado a otro. Podemos representarlo usando un gráfico dirigido donde los Nodes representan los estados y los bordes representan la probabilidad de pasar de un Node a otro. Se necesita una unidad de tiempo para pasar de un Node a otro. La suma de las probabilidades asociadas de los bordes salientes es una para cada Node.
Considere la string de Markov dada (G) como se muestra en la imagen a continuación:
Ejemplos :
Input : S = 1, F = 2, T = 1 Output : 0.23 We start at state 1 at t = 0, so there is a probability of 0.23 that we reach state 2 at t = 1. Input : S = 4, F = 2, T = 100 Output : 0.284992
Podemos usar la programación dinámica y la búsqueda primero en profundidad (DFS) para resolver este problema, tomando el estado y el tiempo como las dos variables DP. Podemos observar fácilmente que la probabilidad de pasar del estado A al estado B en el tiempo t es igual al producto de la probabilidad de estar en A en el tiempo t – 1 y la probabilidad asociada con el borde que conecta A y B. Por lo tanto, la probabilidad de estar en B en el tiempo t es la suma de esta cantidad para todo A adyacente a B.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Macro for vector of pair to store
// each node with edge
#define vp vector<pair<int, float> >
// Function to calculate the
// probability of reaching F
// at time T after starting
// from S
float findProbability(vector<vp>& G, int N,
int F, int S, int T)
{
// Declaring the DP table
vector<vector<float> > P(N + 1, vector<float>(T + 1, 0));
// Probability of being at S
// at t = 0 is 1.0
P[S][0] = 1.0;
// Filling the DP table
// in bottom-up manner
for (int i = 1; i <= T; ++i)
for (int j = 1; j <= N; ++j)
for (auto k : G[j])
P[j][i] += k.second * P[k.first][i - 1];
return P[F][T];
}
// Driver code
int main()
{
// Adjacency list
vector<vp> G(7);
// Building the graph
// The edges have been stored in the row
// corresponding to their end-point
G[1] = vp({ { 2, 0.09 } });
G[2] = vp({ { 1, 0.23 }, { 6, 0.62 } });
G[3] = vp({ { 2, 0.06 } });
G[4] = vp({ { 1, 0.77 }, { 3, 0.63 } });
G[5] = vp({ { 4, 0.65 }, { 6, 0.38 } });
G[6] = vp({ { 2, 0.85 }, { 3, 0.37 }, { 4, 0.35 }, { 5, 1.0 } });
// N is the number of states
int N = 6;
int S = 4, F = 2, T = 100;
cout << "The probability of reaching " << F
<< " at time " << T << " \nafter starting from "
<< S << " is " << findProbability(G, N, F, S, T);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
static class pair
{
int first;
double second;
public pair(int first, double second)
{
this.first = first;
this.second = second;
}
}
// Function to calculate the
// probability of reaching F
// at time T after starting
// from S
static float findProbability(Vector<pair>[] G,
int N, int F, int S, int T)
{
// Declaring the DP table
float[][] P = new float[N + 1][T + 1];
// Probability of being at S
// at t = 0 is 1.0
P[S][0] = (float) 1.0;
// Filling the DP table
// in bottom-up manner
for (int i = 1; i <= T; ++i)
for (int j = 1; j <= N; ++j)
for (pair k : G[j])
P[j][i] += k.second * P[k.first][i - 1];
return P[F][T];
}
// Driver code
public static void main(String[] args)
{
// Adjacency list
Vector<pair>[] G = new Vector[7];
for (int i = 0; i < 7; i++)
{
G[i] = new Vector<pair>();
}
// Building the graph
// The edges have been stored in the row
// corresponding to their end-point
G[1].add(new pair(2, 0.09));
G[2].add(new pair(1, 0.23));
G[2].add(new pair(6, 0.62));
G[3].add(new pair(2, 0.06));
G[4].add(new pair(1, 0.77));
G[4].add(new pair(3, 0.63));
G[5].add(new pair(4, 0.65));
G[5].add(new pair(6, 0.38));
G[6].add(new pair(2, 0.85));
G[6].add(new pair(3, 0.37));
G[6].add(new pair(4, 0.35));
G[6].add(new pair(5, 1.0));
// N is the number of states
int N = 6;
int S = 4, F = 2, T = 100;
System.out.print("The probability of reaching " + F +
" at time " + T + " \nafter starting from " +
S + " is "
+ findProbability(G, N, F, S, T));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach
# Macro for vector of pair to store
# each node with edge
# define vp vector<pair<int, float> >
# Function to calculate the
# probability of reaching F
# at time T after starting
# from S
def findProbability(G, N, F, S, T):
# Declaring the DP table
P = [[0 for i in range(T + 1)]
for j in range(N + 1)]
# Probability of being at S
# at t = 0 is 1.0
P[S][0] = 1.0;
# Filling the DP table
# in bottom-up manner
for i in range(1, T + 1):
for j in range(1, N + 1):
for k in G[j]:
P[j][i] += k[1] * P[k[0]][i - 1];
return P[F][T]
# Driver code
if __name__=='__main__':
# Adjacency list
G = [0 for i in range(7)]
# Building the graph
# The edges have been stored in the row
# corresponding to their end-point
G[1] = [ [ 2, 0.09 ] ]
G[2] = [ [ 1, 0.23 ], [ 6, 0.62 ] ]
G[3] = [ [ 2, 0.06 ] ]
G[4] = [ [ 1, 0.77 ], [ 3, 0.63 ] ]
G[5] = [ [ 4, 0.65 ], [ 6, 0.38 ] ]
G[6] = [ [ 2, 0.85 ], [ 3, 0.37 ],
[ 4, 0.35 ], [ 5, 1.0 ] ]
# N is the number of states
N = 6
S = 4
F = 2
T = 100
print("The probability of reaching {} at "
"time {}\nafter starting from {} is {}".format(
F, T, S, findProbability(G, N, F, S, T)))
# This code is contributed by rutvik_56
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
class pair
{
public int first;
public double second;
public pair(int first, double second)
{
this.first = first;
this.second = second;
}
}
// Function to calculate the
// probability of reaching F
// at time T after starting
// from S
static float findProbability(List<pair>[] G,
int N, int F, int S, int T)
{
// Declaring the DP table
float[,] P = new float[N + 1, T + 1];
// Probability of being at S
// at t = 0 is 1.0
P[S, 0] = (float) 1.0;
// Filling the DP table
// in bottom-up manner
for (int i = 1; i <= T; ++i)
for (int j = 1; j <= N; ++j)
foreach (pair k in G[j])
P[j, i] += (float)k.second *
P[k.first, i - 1];
return P[F, T];
}
// Driver code
public static void Main(String[] args)
{
// Adjacency list
List<pair>[] G = new List<pair>[7];
for (int i = 0; i < 7; i++)
{
G[i] = new List<pair>();
}
// Building the graph
// The edges have been stored in the row
// corresponding to their end-point
G[1].Add(new pair(2, 0.09));
G[2].Add(new pair(1, 0.23));
G[2].Add(new pair(6, 0.62));
G[3].Add(new pair(2, 0.06));
G[4].Add(new pair(1, 0.77));
G[4].Add(new pair(3, 0.63));
G[5].Add(new pair(4, 0.65));
G[5].Add(new pair(6, 0.38));
G[6].Add(new pair(2, 0.85));
G[6].Add(new pair(3, 0.37));
G[6].Add(new pair(4, 0.35));
G[6].Add(new pair(5, 1.0));
// N is the number of states
int N = 6;
int S = 4, F = 2, T = 100;
Console.Write("The probability of reaching " + F +
" at time " + T + " \nafter starting from " +
S + " is "
+ findProbability(G, N, F, S, T));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
// Function to calculate the
// probability of reaching F
// at time T after starting
// from S
function findProbability(G, N, F, S, T)
{
// Declaring the DP table
var P = Array.from(Array(N+1), ()=> Array(T+1).fill(0))
// Probability of being at S
// at t = 0 is 1.0
P[S][0] = 1.0;
// Filling the DP table
// in bottom-up manner
for (var i = 1; i <= T; ++i)
for (var j = 1; j <= N; ++j)
G[j].forEach(k => {
P[j][i] += k[1] * P[k[0]][i - 1];
});
return P[F][T];
}
// Driver code
// Adjacency list
var G = Array(7);
// Building the graph
// The edges have been stored in the row
// corresponding to their end-point
G[1] = [ [ 2, 0.09 ] ];
G[2] = [ [ 1, 0.23 ], [ 6, 0.62 ] ];
G[3] = [ [ 2, 0.06 ] ];
G[4] = [ [ 1, 0.77 ], [ 3, 0.63 ] ];
G[5] = [ [ 4, 0.65 ], [ 6, 0.38 ] ];
G[6] = [ [ 2, 0.85 ], [ 3, 0.37 ], [ 4, 0.35 ], [ 5, 1.0 ] ];
// N is the number of states
var N = 6;
var S = 4, F = 2, T = 100;
document.write( "The probability of reaching " + F
+ " at time " + T + " <br>after starting from "
+ S + " is " + findProbability(G, N, F, S, T).toFixed(8));
</script>
Producción:
The probability of reaching 2 at time 100 after starting from 4 is 0.284992
Complejidad temporal : O(N 2 * T)
Complejidad espacial : O(N * T)
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA