指望逆推

2021年11月20日 阅读数:3
这篇文章主要向大家介绍指望逆推,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

疑惑了好久,可能有点思路了吧。数组

举一个常见例子:图上从s开始随机游走,求到t走过的距离指望。
首先思考顺推是否可行。
咱们用dp[x]表示由s到x的距离指望。发现这玩意压根无法转移,由于你能够随便拐弯走,最后就会发现有无数次转移到x的状况,即便几率愈来愈小。也许能够经过转移矩阵的等比求和解决,但实在太麻烦了。spa

思考逆推,用dp[x]表示由x到t的距离指望。这个是能够转移的。发现与t相邻的全部点组成了t的全部转移,必然只可以从这些点转移至t。那么这些点的dp值就能够用dp[t]转移出。一层层转移便可获得答案。
\(dp[x]=\dfrac{1}{in_x}\sum_{y}dp[y]+w(y,x)\),其中 \(in_x\) 表示 x 的入度,\((y,x)\) 为一条有向边 \(y->x\)
那么高斯消元就能够解决。递归

更加理性的思考这个过程。问题出在哪里?是dp的定义。
这里的顺推定义的是由s至x的距离指望。这种转移是不行的,由于没有规定究竟过程如何,这样的过程是无限多种的。同时,终止状态集合是不肯定的,这是肯定性计算难以接受的。
可是实际上,某些问题可使用一些奇怪的dp状态定义达到事件互斥,进而能够计算指望。事件

举个例子,无向三元环,从a开始走,b结束,那么如此dp就会发现b与c的dp值相同,但这是不可能的。走到b就结束了,而走到c还能够走。class

这由随机性自己决定。必须注意到指望研究的是相似于计数的却又带有无限限制的问题,而非通常的肯定性问题,更不具备所谓极化问题的最优子结构之说。要跳出以前的逻辑思考。搜索

而逆推定义的是由x到t的距离指望。考虑转移,对于x,咱们研究每一个多后撤一步再转移的距离指望。而这件事是能够作到的。由于无论如何,能由x到t的路径必然先由其相邻点转移到x。
这样作,起点状态是肯定的,终点集合也是肯定的,因此能够dp。循环

考虑更通常的问题。若是路径知足肯定性,即相似于DAG,这种状况的确能够经过顺推动行指望计算,须要多开一个几率数组计算每一步的指望。
仅当起点、终点与转移都肯定时,能够无脑正推指望。好比一些同层不转移的分层图。遍历

将问题抽象成状态和状态之间的转移后,求解整个状态图,要从已知的状态开始计算。实际上,起点与终点都算做“已知”,可是通常终点的信息更明确,致使逆推更加容易。集合

dp本质上依然是对状态空间的遍历,正着/倒着,循环递推仍是记忆化搜索递归,本质上都没有区别,只是在有的题目中,某一种写法更简单一些,形成了以为“必需要正/倒推”这一错觉。思考