Python
 Computer >> コンピューター >  >> プログラミング >> Python

マルコフ連鎖の特定の時間における状態の確率を見つける-Pythonで1を設定

マルコフ連鎖グラフgがあるとします。時間t=0のときに状態Sから開始すると、時間Tで状態Fに到達する確率がわかります。マルコフ連鎖は、さまざまな状態と、ある状態から別の状態に移動する確率で構成されるランダムプロセスです。これは有向グラフとして表すことができます。ノードは状態であり、エッジにはあるノードから別のノードに移動する確率があります。ある状態から別の状態に移動するには、単位時間がかかります。発信エッジの確率の合計は、ノードごとに1つです。

したがって、入力がN =6、S =4、F =2、T =100の場合、出力は0.28499144801478526

になります。

これを解決するには、次の手順に従います-

  • table：=サイズ（N + 1）x（T + 1）の行列で、0.0で埋めます

  • table [S、0]：=1.0

  • 1からTの範囲のiの場合、実行します

    • 1からNの範囲のjについては、次のようにします

      • G [j]のkごとに、実行

        • table [j、i]：=table [j、i] + k [1] * table [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

  1. 無向グラフにPythonで指定されたサイズの独立集合が含まれているかどうかを確認します

    与えられた無向グラフがあるとしましょう。サイズlの独立集合が含まれているかどうかを確認する必要があります。サイズlの独立したセットがある場合は、「はい」を返します。それ以外の場合は「いいえ」を返します。 グラフ内の独立集合は、互いに直接接続されていない頂点の集合として定義されていることに注意する必要があります。 したがって、入力がL =4のような場合、 その場合、出力はyesになります これを解決するには、次の手順に従います- 関数is_valid（）を定義します。これはグラフを取ります、arr 0からarrのサイズまでの範囲のiの場合、実行します i + 1

  2. Python Regexを使用して、特定の文字列内の「1（0+）1」のすべてのパターンを検索します

    このチュートリアルでは、正規表現を使用して、文字列内の1（0 + 1）のすべての出現を検出するプログラムを作成します。 。 Pythonには、正規表現を操作するのに役立つreモジュールがあります。 1つのサンプルケースを見てみましょう。 Input: string = "Sample 1(0+)1 string with 1(0+)1 unnecessary patterns 1(0+)1" Output: Total number of pattern maches are 3 ['1(0+)1', '1(0+)1', '1(0+