algorithm - 如何找到流动网络中每个接收器的最终存储量？

Question

我有一个具有单源和多个接收器的流网络。如果我从源头流出 1 加仑的水，那么所有的水都会在节点处 split ，最终存储在不同的水槽中。这里每个边权重 c(u,v) 表示来自 u 的分水率。如何找到每个水槽最终储存的水量？

手动计算的示例:

Answer 1

这是 absorbing Markov chain 的示例.

令Q[j,i]为从第j^个非汇聚节点流入第i^个非汇聚节点的流量比例。

设R[j,i]为从第j^个非汇聚节点流入第i^个汇聚节点的流量比例。

设矩阵N=inv(I-Q)，矩阵B=N*R。

第i^个汇聚节点的最终流量由B[0,i]给出。

第一个案例的 Python 示例:

import numpy as np

# Rows are proportion of flow out of each non-sink vertex
Q = np.zeros((3,3))
Q[0,:] = 0,0.3,0.7 # Flow out of S
Q[1,:] = 0,0,0     # Flow out of a
Q[2,:] = 0,0.5,0   # Flow out of b
# Rows are flow from non-sink to sink nodes
R = np.zeros((3,2))
R[1,:] = 0.1,0.9
R[2,:] = 0,0.5 
N = np.matrix(np.identity(len(Q)) - Q).I
B = N*R
print B[0,:]

打印

[[ 0.065  0.935]]

说明

一旦我们设置了矩阵，我们就可以通过从包含 [1,0,0](代表开始时的一加仑)的行向量 v 和一个空行向量 e(代表水槽中的水量)。

在每个时间步中我们计算:

e += v * R # This works out the amount of flow that has reached the end
v = v * Q # This works out the amount of flow that is still in the network

如果我们模拟这个过程足够长的时间，我们最终会得到 v 接近 0，e 接近答案。

但是我们可以将 e 的值写为:

e = v*R + v*Q*R + v*Q*Q*R + v*Q*Q*Q*R +...
  = v * (I + Q + Q*Q + Q*Q*Q + ...) * R
  = v * inv(I-Q) * R
  = v * N * R
  = v * B
  = [1,0,0] * B
  = first row of B