问一个关于Graph的算法题

题目大意是，给你如下图所示的undirected graph，从0出发，假设朝各个方向走的概率相等，并且可以返回（如走四步：0-1-3-1-0），累计每一步所经过的node的值（即求和），问你走5步之后总和的期望是多少？如果是走50步？1000步？

楼主本来想用DFS来做，但是步数多了用递归就解不出来了。而且楼主也不知道怎样算这个和，不太可能把所有路径列出来再取平均吧？
求助求助。。。谢谢

我觉得可以用DP来做。从N0出发经过K步之后到达点集S{s1, s2...sk}的平均和，等价于从点集S{s1, s2,...sk}出发经过K步到达N0的平均和。如果用f(N0, K)代表这个平均和，n(N0)代表N0结点的邻居，则有转移方程：

f(N0, K) = sum{ f(Ni, K-1) for Ni in n(N0) } / #n(N0)

定义一个K * #Nodes维度的数组dp，dp[k-1]代表f(Ni, k)，然后先dfs或者bfs看每一层需要访问的结点，在另一个数组上mark一下。
然后从第0层开始算下去，把marked的结点的平均和求出来。

想了一下这个模型随着步数逐渐增加到无穷大的情况，更符合在 Graph 上做 random walk，也就是 Markov Chain 模型。随着 random walk 长度的增加，这个 Markov Chain 的矩阵表示形式会逐渐趋近于它的 stationary distribution，即 random walk 在每一个状态上停留的期望时间。

对于 Graph，Markov Chain random walk 的 normalization factor  = 2 * E ，在这个图中就是 2 * 8 = 16. 其中每一个状态的 stationary distribution 值等于其 degree / normalization factor，对于 "3" 来讲，degree = 2，期望用时为 1/8 ; 对于 "1" 来讲，degree = 3 ，期望用时为 3 / 16, etc.

因此当步数足够大的时候，可以直接用每个 node (状态) 的 stationary distribution 表示这个节点在整个 walk 过程中的 weight，节点值为 cost，期望值是可以直接用解析式表达出来的~

http://research.microsoft.com/en-us/um/people/peres/markovmixing.pdf 这个 paper 里的 1.4 和 1.5 ~

mnmunknown 发表于 2016-7-17 21:27
想了一下这个模型随着步数逐渐增加到无穷大的情况，更符合在 Graph 上做 random walk，也就是 Markov Chain ...

层主的理论功夫好扎实！！

mnmunknown 发表于 2016-7-17 21:27
想了一下这个模型随着步数逐渐增加到无穷大的情况，更符合在 Graph 上做 random walk，也就是 Markov Chain ...

好厉害。发现我的随机过程都丢给老师了。。。

desperatelife 发表于 2016-7-17 22:04
层主的理论功夫好扎实！！

过奖~ 我们学校理论课老师脑洞都很大就是了。。

mnmunknown 发表于 2016-7-17 21:27
想了一下这个模型随着步数逐渐增加到无穷大的情况，更符合在 Graph 上做 random walk，也就是 Markov Chain ...

感谢！看了之后觉得收获很大！那如果只是有限步数的情况，是不是就用不到markov chain了？

mnmunknown 发表于 2016-7-17 21:27
想了一下这个模型随着步数逐渐增加到无穷大的情况，更符合在 Graph 上做 random walk，也就是 Markov Chain ...

觉得这个题似乎比较像是问精确解。

就是求转移矩阵T的n次方，n是步数。转移矩阵T[i,j]就是从 i -> j的条件概率。
pow(T, n)的做法类似pow(int, int)，可以利用n的二进制压缩到log n次矩阵乘法。

如果要进一步加速可以把T对角化成T = R*D*inv(R) 从而pow(T, n) = R* pow(D, n) * inv(R).
pow(D, n)只需要对对角阵D对角线上的每个element d求pow(d, n)就可以得到。不过如果走到这里也太数学题了。

hxtang 发表于 2016-7-18 03:43
觉得这个题似乎比较像是问精确解。

就是求转移矩阵T的n+1次方，n是步数。转移矩阵[j]就是从 i -> j的 ...

完全同意~ 对于指定步数 n 的话，就要求转移矩阵的 n 次方，可以通过对角化加速运算。单就这个问题来讲， Markov Chain mixing on graph 确实是最贴近原题描述的模型，不过想到这就不太像面试时候会碰到的东西，而是比较偏理论的算法老师在课上会讲的了。。

mnmunknown 发表于 2016-7-18 04:04
完全同意~ 对于指定步数 n 的话，就要求转移矩阵的 n 次方，可以通过对角化加速运算。单就这个问题来讲， ...

补充一下对角化也不一定必然是好的。如果node超多导致T超大，但n不大，对角化、求矩阵n次方都很痛苦（因为矩阵不再dense了）。这时候老老实实用一个for loop做Sparse matrix multiply vector才是正解。
所以理想情况下可能需要问图的规模、稀疏度、还有n的范围来确定怎么做是最优的。

general面试估计有个formulation加一个基本的实现就行了吧。稀疏矩阵什么的。估计就是如果双方都懂，那么可以讲一下加点印象分（个人觉得如果对方没有相关背景还是不讲为好...）。