信息扩散模型贪心算法_迪杰斯特拉算法的本质是贪心还是动态规划

⑴ 迪杰斯特拉算法的本质是贪心还是动态规划

贪心是一种特殊的动态规划，动态规划的本质是独立的子问题，而贪心则是每次可以找到最优的独立子问题。
贪心和动归不是互斥的，而是包含的，贪心更快，但约束更强，适应范围更小。
动归和bfs的关系也是一样的。

展开一点讲，在求解最优化问题时，有多个解。而求解的过程类似一个树，我们称之为求解树。

一般的求解树真的是一棵树，所以我们只能用bfs来搜索，顶多剪枝。

有些特殊的求解树，中间很多结点是重合的，结点个数比所有搜索分支的个数少很多个数量级。这类问题较特殊，我们可以保存中间的搜索过程。而记忆化搜索和动态规划本质上就是一个东西，快就快在可以不用重复计算很多中间结果（所谓的最优子问题）。

还有一些特殊的求解树，更特殊，它们不止有很多重复结点，而且每次选择分支的时候，我们可以证明只要选择一个分支，这个分支的解就一定比其他选择更优。这类问题就是贪心了，

所以bfs，dp，贪心三个方法都是解决最优化问题的方法，根据问题的不同，约束越大的问题可以用越快的方法，越慢的方法可以解决的问题越普适。

动态规划的状态转移函数，可以抽象成这样一种函数：

f(x)=g(f(x1), f(x2), f(x3), ... f(xn))

其中f就是我们说的独立问题，每个f都有一个唯一值，也就是没有后效性。

贪心也是这个函数，但可以证明：

f(xi) >= f(x1|x2|...|xn)

那么我们就不用再去计算除了f(xi)以外的任何子状态了，所以就更快

而标准的bfs，虽然也有

f(x)=g(f(x1), f(x2), f(x3), ... f(xn))

但是因为对于任意的f(x)，它的子问题f(xi)的输入状态xi都不同（换一种思路也可以说f(xi)在不同的路径下值都不同，本质上是我们怎么定义xi，到底是狭义的参数还是广义的状态），所以无法使用内存去换取时间，就只能去遍历所有状态了。

热点内容

阿里云不就是服务器商吗发布：2025-09-13 01:24:42 浏览：292

对局服务器延迟是什么原因发布：2025-09-13 01:19:31 浏览：185

phpp2p技术发布：2025-09-13 01:16:09 浏览：762

A4插页袋文件夹是什么发布：2025-09-13 00:55:21 浏览：640

模板建站配云服务器商家发布：2025-09-13 00:40:11 浏览：704

华为手机加密工具发布：2025-09-13 00:25:17 浏览：677

java开发转android 发布：2025-09-13 00:24:17 浏览：192

阿古斯服务器怎么样了发布：2025-09-13 00:23:39 浏览：605

阿里云服务器充值发布：2025-09-13 00:15:18 浏览：587

雷电同步文件夹发布：2025-09-13 00:14:21 浏览：978

服务器按钮是什么意思发布：2025-09-13 00:10:44 浏览：811

单片机控制灯光设计发布：2025-09-12 23:51:42 浏览：141

剧本杀怎么app好用发布：2025-09-12 23:42:35 浏览：264

app上不去网怎么设置发布：2025-09-12 23:17:52 浏览：220

phpjava运行效率发布：2025-09-12 23:11:45 浏览：248

php查询数据库条数发布：2025-09-12 23:03:06 浏览：41

程序员一族发布：2025-09-12 23:02:53 浏览：932

绍兴程序员兼职在哪里接发布：2025-09-12 22:50:19 浏览：675

身为程序员是什么体验发布：2025-09-12 22:48:34 浏览：561

51单片机应用从零开始pdf 发布：2025-09-12 22:31:58 浏览：589

信息扩散模型贪心算法