0

私は一連の確率を持つ非対称有向グラフを持っています(つまり、人がポイントAからBに、またはポイントAからCに移動する可能性など)。すべてのポイントを通るルートが与えられた場合、ルートで行われた各選択が適切な選択である可能性を計算したいと思います。

例として、2 点だけのグラフがあるとします。

//In a matrix, the probabilities might look like
//A     B
[ 0    0.9  //A
  0.1   0 ] //B

したがって、A から B に移動する確率は 0.9、B から A に移動する確率は 0.1 です。ルート A->B が与えられた場合、最初のポイント (A) と 2 番目のポイント (B) はどの程度正しいか。

A->B->C->D というルートを持つ、より大きなマトリックスがあるとします。だから、私が知りたいことのいくつかの例：

  • A が B、C、および D の前に来る可能性はどのくらいですか?
  • B が A の後に来る可能性はどのくらいですか?
  • C & D が B の後に来る可能性はどのくらいありますか?

基本的に、各ポイントで、前のポイントが現在のポイントより前に来る可能性と、次のポイントが後に来る可能性を知りたいです。統計的に正しいものは必要ありません。相対的な比較に使用できる単なる指標です。何か案は？

更新：この質問は誰にとっても役に立たないことがわかりましたが、答えは私にとって本当に役に立ちましたので、問題の説明をより明確にしようとしました。

4

3 に答える 3

0

それが効率的に可能だとは思いません。ポイントが間違った位置にある確率を計算するアルゴリズムがあれば、各ポイントのどの位置が最も間違っていなかったかを簡単に計算して、正しい順序を計算できます。問題は基本的に最適なルートを見つけることと同じです。

ここでの副次的な質問は、確率が「の」であるかどうかです。確率を100％にすることはできますか？どうやって知る？

巡回セールスマン問題が難しい理由の1つは、すべての解決策を調べてそれが最短であると判断する以外に、最適な解決策があることを知る方法がないことです。

于 2012-04-16T15:26:53.787 に答える
0

よく考えた結果、自分のニーズに合ったものを見つけました。正確な答えを得るには、考えられるすべてのルートをチェックする必要があるという同じ問題が依然としてあります。ただし、私の場合、直接ルートと最初の間接ルートを確認するだけで、私の答えがどれほど「正しい」かがわかります。

まず、各確率の信頼度が必要です。これは別の計算であり、別のマトリックスに含まれています (1 対 1 を確率マトリックスにマップします)。確率ごとに 1.0-confidenceInterval を取ります。

ルート A->B->C->D がある場合、ポイントの「正確性指標」を計算します。直接ルートと間接ルートの最初のレベルの平均を取得しているようです。

いくつかの例：

P(A,B) を A が B より前に来る確率として示す C(A,B) を A が B より前に来る確率の信頼度として示す P`(A,C) を A が C より前に来るという間接確率に基づく信頼度として示すルートA→B→C

点 B で、A がその前に来る可能性:

指標 = P(A,B)*C(A,B)/C(A,B)

点 C で、A と B が前に来る可能性:

P (A,C) = P(A,B)*P(B,C) C(A,C) = C(A,B)*C(B,C)

インジケータ = [P(A,C)*C(A,C) + P(B,C)*C(B,C) + P'(A,C)*C'(A,C)]/[C (A,C)+C(B,C)+C'(A,C)]

したがって、これにより、常に 0 と 1 の間にあるある種のインジケーターが得られ、最初のレベルの間接ルート (from->indirectPoint->to) が考慮されます。私が探していた大まかな見積もりを提供しているようです。それは素晴らしい答えではありませんが、ある程度の見積もりを提供し、他に何も提供しないため、適切です

于 2012-05-08T02:37:19.557 に答える
0

確率行列 (p) を -log(p) に置き換え、その行列で最短経路を見つけると問題が解決します。

于 2012-04-16T17:26:27.877 に答える