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) 有多正确，第二个点 (B) 有多正确。

假设我有一个更大的矩阵，其路线为 A->B->C->D。所以，我想知道的一些例子：

  • A 出现在 B、C 和 D 之前的可能性有多大
  • B 出现在 A 之后的可能性有多大
  • C & D 出现在 B 之后的可能性有多大

基本上，在每一点上，我都想知道前面的点出现在当前点之前的可能性，以及后面的点出现的可能性。我不需要统计上合理的东西。只是我可以用来进行相对比较的指标。有任何想法吗？

更新：我发现这个问题对每个人都没有用，但答案对我来说真的很有用，所以我试图让问题的描述更清楚，并且很快就会包括我的答案，以防它对某人有所帮助。

4

3 回答 3

0

我认为这不可能有效。如果有一种算法可以计算一个点位于错误位置的概率，您可以简单地计算出每个点的哪个位置错误最少，从而计算出正确的顺序。问题本质上与寻找最优路线相同。

次要问题是概率是什么，在这里。概率可以是100%吗？你怎么知道的？

旅行商问题很难解决的部分原因是，除了查看所有解决方案并发现它是最短的之外，没有办法知道您是否拥有最优解决方案。

于 2012-04-16T15:26:53.787 回答
0

用 -log(p) 替换概率矩阵 (p) 并在该矩阵中找到最短路径将解决您的问题。

于 2012-04-16T17:26:27.877 回答
0

经过深思熟虑，我想出了适合我需要的东西。它仍然存在相同的问题，要获得准确的答案需要检查每条可能的路线。但是，就我而言，仅检查直接路线和第一条间接路线就足以让您了解我的答案有多“正确”。

首先，我需要每个概率的置信度。这是一个单独的计算，包含在一个单独的矩阵中（将 1 到 1 映射到概率矩阵）。我只为每个概率取 1.0-confidenceInterval。

如果我有一条路线 A->B->C->D，我会计算一个点的“正确性指标”。看起来我得到了某种直接路由和第一级间接路由的平均值。

一些例子：

Denote P(A,B) as probability that A comes before B Denote C(A,B) as confidence in the probability that A comes before B Denote P`(A,C) as confidence that A comes before C based on the indirect route A->B->C

At point B, likelihood that A comes before it:

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

At point C, likelihood that A & B come before:

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

indicator = [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)]

So this gives me some sort of indicator that is always between 0 and 1, and takes the first level indirect route into account (from->indirectPoint->to). It seems to provide the rough estimation I was looking for. It is not a great answer, but it does provide some estimate and since nothing else provides anything better, it is suitable

于 2012-05-08T02:37:19.557 回答