一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 591|回复: 9
收起左侧

[树/链表/图] 问一个关于Graph的算法题

[复制链接] |试试Instant~ |关注本帖
星落西徐 发表于 2016-7-17 12:41:04 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 星落西徐 于 2016-7-17 12:42 编辑

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

graph

graph


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

musteryu 发表于 2016-7-17 15:50:29 | 显示全部楼层
本帖最后由 musteryu 于 2016-7-17 18:18 编辑

我觉得可以用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的结点的平均和求出来。
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-7-17 21:27:40 | 显示全部楼层
想了一下这个模型随着步数逐渐增加到无穷大的情况,更符合在 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 ~
回复 支持 反对

使用道具 举报

desperatelife 发表于 2016-7-17 22:04:12 | 显示全部楼层
mnmunknown 发表于 2016-7-17 21:27
想了一下这个模型随着步数逐渐增加到无穷大的情况,更符合在 Graph 上做 random walk,也就是 Markov Chain ...

层主的理论功夫好扎实!!
回复 支持 反对

使用道具 举报

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

好厉害。发现我的随机过程都丢给老师了。。。
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-7-18 01:54:21 | 显示全部楼层
desperatelife 发表于 2016-7-17 22:04
层主的理论功夫好扎实!!

过奖~ 我们学校理论课老师脑洞都很大就是了。。
回复 支持 反对

使用道具 举报

 楼主| 星落西徐 发表于 2016-7-18 02:52:57 | 显示全部楼层
mnmunknown 发表于 2016-7-17 21:27
想了一下这个模型随着步数逐渐增加到无穷大的情况,更符合在 Graph 上做 random walk,也就是 Markov Chain ...

感谢!看了之后觉得收获很大!那如果只是有限步数的情况,是不是就用不到markov chain了?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-18 03:43:47 | 显示全部楼层
本帖最后由 hxtang 于 2016-7-18 04:42 编辑
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)就可以得到。不过如果走到这里也太数学题了。
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-7-18 04:04:04 | 显示全部楼层
hxtang 发表于 2016-7-18 03:43
觉得这个题似乎比较像是问精确解。

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

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

使用道具 举报

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

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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 04:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表