6

ノードが「開始」としてマークされ、別のノードが「目標」としてマークされている有限の無向グラフがあります。

エージェントは最初に開始ノードに配置され、グラフ内をランダムにナビゲートします。つまり、各ステップで、隣接ノードをランダムに均一に選択して移動します。ゴールノードに到達すると停止します。

私は、ノードごとに、エージェントが開始から目標まで移動しているときにエージェントがノードにアクセスする確率を示すアルゴリズムを探しています。ありがとうございました。

4

1 に答える 1

12

グラフでよくあることですが、問題を説明する適切な方法を知っているだけです。

グラフを記述する 1 つの方法は、隣接行列として使用することです。グラフ G = (V, E) が |V| の場合 ノード (|V| は頂点の数)、この行列は |V| になります。x |V|。頂点のペアの間にエッジが存在する場合は、隣接行列の項目を 1 に設定し、存在しない場合は 0 に設定します。

これの自然な拡張は、加重グラフです。ここでは、0 または 1 ではなく、隣接行列に重みの概念があります。

あなたが説明している場合、重みがあるノードから別のノードに遷移する確率である重み付きグラフがあります。このタイプの行列には特別な名前があり、確率行列です。マトリックスをどのように配置したかに応じて、このマトリックスには、合計が 1 になる行または列があり、それぞれ左右の確率行列になります。

確率行列とグラフの間の 1 つのリンクは、マルコフ連鎖です。マルコフ連鎖の文献では、重要なのは遷移行列 (1 つの時間ステップ後の遷移確率に等しい重みを持つ隣接行列) です。遷移行列をPとしましょう。

k タイムステップ後にある状態から別の状態に遷移する確率を計算すると、P ^k で与えられます。既知のソース状態 i がある場合、 P ^kの i 番目の行は、他の状態に遷移する確率を示します。これにより、短期的に特定の状態になる確率の推定値が得られます

ソースグラフによっては、 P ^k が定常状態分布に達する場合があります。つまり、kの値に対してP ^k = P ^(k+1) になります。これにより、長期的に特定の状態になる確率の推定値が得られます

余談ですが、これを行う前に、グラフを見て、ある時点で特定の状態になる確率についていくつかのことを言うことができるはずです.

  1. グラフに互いに素なコンポーネントがある場合、開始時とは異なるコンポーネントに含まれる確率はゼロです。
  2. 吸収している状態がグラフにある場合、つまり、いったん入力した状態 (または状態のグループ) が避けられない場合は、それを考慮する必要があります。これは、グラフがツリー状である場合に発生する可能性があります。
于 2013-03-20T13:00:05.437 に答える