贪心穷举动态规划区别

- 日理万妓 2022-09-04 09:44 172阅读 0赞

我们面对的是一个求最优解或统计之类的问题，这个问题基于“我们要模拟完成一个大任务”，这个大任务可以分成若干步骤，每个步骤有若干种决策，每个步骤完成后，就到达了一个阶段性状态  
比如，你要从A地到Z地，没有直达，所以第一步需要到一个中间地点，比如H或I，第二步再前进，比如到P或Q，最后到达Z，每一步有若干决策，比如第一步你可以决定到H或I的中的某个，大致就是这样一个模型，可以自己画个地图看看  
等等，你大概发现问题了，如果第一步到H和I都可以，第二步到P和Q都可以，那我每一步只选最优，不就用贪心得到结果了吗，没错，如果你需要经历的每个阶段状态跟决策无关，那就贪心得到结果好了，理解贪心了吗：）

![8627d58b390f1450eba84dd9673a697b.png][]

然而现实情况可能是，你第一步的选择会影响后面的分支，比如你第一步可以选择到H或I，但是到了H后，你只能选择经过P或Q到Z了，而如果到了I，你只能选择R或S到Z，这样一来，即便第一步到H或I你选择了较好的一条路，也不保证最终结果最优，因为比如你选了H，那万一I-R-Z的路要比H开始到Z的路径短了更多，最优路径可能是A-I-R-Z，所以你要把这些路都尝试一遍，才知道哪个最优，理解穷举了么？：）

![aa8d3b955037ac6b302e72e0bd9507a8.png][]

OK，我们稍微改下题设，假如从I出发不是到R和S，而是到Q或R，会如何

![82ca504acdeca332abd0922f50980e18.png][]

诚然，我们可以用穷举每条路来解决这个问题，需要穷举的路径数和上面的图一样，但是，我们可以有更快的办法，你不用将A-H-Q-Z和A-I-Q-Z两条路单独计算，因为他们有状态交点，结合第一张图的思想，可以敏锐地感觉到，我们只需要计算到每个有共同状态的位置求各阶段的最优，最后每阶段选最优组合贪心组合起来就行，因为各阶段完成的状态点是大家都有的嘛，因此，咱们先计算A-H-Q和A-I-Q，选个最好的，然后跟Q到Z中最好的拼起来，就是最优了，没必要把所有路径都搞一遍（虽然图里面Q到Z直达，但你可以发挥想象力，将其想象成各种分支的一条复杂道路），这样一来就把一个x^(a+b+c+...)的计算次数降低为x^a+x^b+x^c...，其中x代表每次的决策次数（简单点假设每次决策次数都一样），abc代表每个阶段的步骤数

因此，我们可以从A开始，向Z进行BFS，并对BFS中每个点保存最优状态，如果有不同的路径BFS到了同一个点，留最好的一条就行，比如上面这个，你的算法可能先从A-H-Q搜到了Q这个位置，之后从A-I-Q又到了这里，留最好的一条，最后一轮从PQR三个点到Z，就结束了，相对第二章图要少一次运算

如果你理解了，恭喜你已经能有效解决很多需要DP的问题了，同时还学会了解图论的单源最短路径问题呢

最后用经典的0-1背包问题做个例子，巩固一下吧，这个任务是，我们从N个物品选若干塞到可以承受最大重量W的包包里面，要价值最大，因此就可以将任务分成N个步骤，每个步骤面对第i号物品，决策有两条：选，还是放弃，这里的状态，就是影响之后步骤决策的因素，在这里，就是“背包的剩余空间”

比如，物品的重量是1,2,3,4,5,6，W=12，从头决策，0表示放弃，1表示选，BFS三次后有8种状态：  
000 剩12  
001 剩9  
……（略）  
110 剩9  
……（略）  
前三次步骤后，001和110到达了同样的状态，都是剩余可装重量9的东西，这样在剩下的决策中，这俩分支走的路都是一样的，跟你之前是选了001还是110没有任何关系（无后效性），因此只要看001价值大，还是110价值大就可以了，8个状态减少为7个，继续BFS下去，每一轮都合并同样状态，完成后，从最后一轮的所有状态中，找到价值最大的就ok了

由于状态最多有W+1个，进行N轮，因此复杂度O(NW)，书上说的状态迁移方程的办法其实跟这个过程很类似，不过对于有些题目，比起BFS+状态合并，状态方程的分析可以做更好的优化，如引入单调队列什么的，但BFS+状态合并可以让你得到一个没有追求极限但是也比较快的解决方案了，结合具体问题有时候更适合，比如根据问题的实际需求，搜索可以限界剪枝减少工作量，我在工作中就用过，替换了同事从wiki抄的DP算法，效率能提升一些

作者：冒泡  
链接：https://www.zhihu.com/question/39948290/answer/83942329  
来源：知乎  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[8627d58b390f1450eba84dd9673a697b.png]: /images/20220829/dc16fb2c9e984e368273dd5e137c5f50.png
[aa8d3b955037ac6b302e72e0bd9507a8.png]: /images/20220829/1b2462bfee644660924bc693a395e977.png
[82ca504acdeca332abd0922f50980e18.png]: /images/20220829/5b817bf7fc1f4d4aba80aa3a95f87d22.png