动态规划算法和贪心算法的区别与联系 – 电子常识

[导读]  动态规划算法和贪心算法,这两种算法都是选择性算法。。,它是从候选集合中选择适当的元素并添加。两种算法的申请表格背景非常相似。,针对具体问题,两个属性直接与算法选择相关。,最优子结构性质性质与贪婪选择性质。所谓贪婪选择性质是全局最优解。,这是贪婪的选择来实现的。。这是利用贪心算法求解最优解的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

  一、动态规划算法介绍

动态规划算法是基于分裂问题。,定义问题的状态与状态之间的关系。,这样问题就可以用递归的方式来解决。。

  1。基本思路与策略

动态规划算法的基本思想类似于划分。,它还将要解决的问题分解成若干个子问题(阶段)。,按顺序求解子阶段,前一个子问题的解,它为解决后一个子问题提供了有用的信息。。在求解任何子问题时,列出所有可能的局部解。,保留可通过DECISI实现最佳的局部解,丢弃其他局部解。依次解决每个子问题。,不可更改的的子问题是初始问题的求解。。大多数动态规划解决的问题都有重叠的子问题。,减少重复计算,每个子问题只有一个解决方案。,在二维数组中保存不同相位的不同相位。。

动态规划算法和贪心算法的区别与联系

  2。申请表格

通常有3个性质可以通过动态规划来解决。:

(1)优化原理:如果问题的最优解包含子问题,则求解。,该问题具有最优的子结构。,这是为了满足最优化原理。。

(2)无后效:更确切地说,一旦确定了某一阶段的状态。,不会受到这种状态的影响。。更确切地说,一个状态的后续过程不会影响先前的状态。,只与当前状态有关。。。

(3)存在重叠问题。:更确切地说,子问题不是独立的。,子问题可以在下一阶段的决策中使用很多次。。这个性质不是申请表格动态PR的必要条件。,但没有这种性质,动态规划算法同其他算法相比就不具备优势)

  三。算法实现

动态规划的主要困难在于理论设计。,这就是上述4个步骤的确定。,一旦设计完成,实现部分将非常简单。。用动态规划求解问题,最重要的是确定动态规划的三个要素。:

(1)问题的阶段。

(2)各阶段的状态。

(3)前一阶段与后一阶段的复发关系。。

递归关系必须从一个小问题转化为较大问题。,从这个角度,动态规划通常可以通过递归过程来实现。,再,递归可以充分利用以前的解决方案。,如此,对于大规模问题,递归有一个不可比拟的优点。,这也是动态规划算法的核心。。

确定了动态规划的三个要素。,整个求解过程就可以用一个最优决策表来描述,最优决策表是二维表。,行代表决策的阶段。,列表问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大值等。,填充过程是基于递推关系的。,从1行和1列开始。,按行或列优先顺序,依次填写表格。,不可更改的,根据整张数据,得到最优解。。

动态规划算法和贪心算法的区别与联系

  二、贪心算法简介

  贪心算法(又称贪婪算法)是指,解决问题时,目前总是做出最好的选择。。更确切地说,不要考虑整体优化。,在某种意义上,他所做的是一个局部最优解。。贪心算法不是对所有问题都能得到整体最优解,关键是贪婪策略的选择。,贪婪的选择策略必须没有后遗症。,更确切地说,前一个过程的某个状态不会影响未来。,只与当前状态有关。。。

  1。基本要素

  贪心选择

贪婪的选择意味着问题的整体最优解可以是SE。,这是贪婪的选择来实现的。。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪婪的选择是自上而下的。、迭代选择,每个贪婪的选择将问题简化成更小的子问题。。针对特定的问题,来确定它是否具有贪婪选择的性质。,我们必须证明贪婪选择的每一步最终都会得到最好的结果。。概括地说,我们首先可以证明一个问题的全局最优解。,它从贪婪的选择开始。,贪婪的选择之后。,原来的问题被减少到更小的子问题。。于是,数学归纳法证明,通过每一步贪婪的选择,不可更改的,我们可以得到一个整体最优的解决方案。。

  最优子结构性质

当一个问题的最优解包含其最优解时,这个问题被称为最优子结构性质。。贪婪策略用于在每个变换中获得最佳解。。问题的最优子结构性质性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响,动态编程不是。。贪心算法对每个子问题的解决方案都做出选择,无法返回;动态规划将根据前面的选择选择当前的,回滚函数。动态规划主要申请表格于二维或三维,贪婪通常是一维问题。。

动态规划算法和贪心算法的区别与联系

  2。算法特性

贪婪算法所能解决的大多数问题通常都有FLULO。:

随着算法的发展,将收集另外两个集合。:被考虑和选举的候选人。,另一个被考虑但被抛弃的候选人。。

有一个函数来检查候选对象集合的集合是否存在。。这个函数没有考虑该解是否是最优的。。

也有一个函数来检查一组候选对象是否是FEAS。,更确切地说,可以在集合中添加更多的候选来获得这样的集合。。像以前的函数一样。,此时不考虑解的最优性。。

选择函数可以指示哪一个剩余候选是最大DES。。

  不可更改的,目标函数给出解的值。。

为了解决这个问题,我们需要找到一组候选对象来形成解决方案。,它可以优化目标函数。,贪婪算法一步一步地进行。。开头,由算法选择的候选对象集是空的。。下一步的每一步,根据选择函数,该算法从剩下的念珠菌中选择最有前景的解决方案。。如果将对象添加到集合中,则是不可行的。,于是丢弃对象,不再考虑。;抑或,将被添加到集合中。。每次都要收藏。,并检查集合是否构成解决方案。。贪婪算法是否正确工作,那么第一个解决方案通常是最好的。。

动态规划算法和贪心算法的区别与联系

  三、动态规划算法和贪心算法的区别与联系

  介绍背景:这两种算法都是选择性算法。。,它是从候选集合中选择适当的元素并添加。

  贪心算法的选择策略即贪心选择策略,根据一定的规则对候选解进行排序。,于是您可以根据订单进行选择。,在选择过程中,有必要确定电流e,它与下面的元素无关。。

动态规划的选择策略是探索性的。,每一步都是测试所有可行的解决方案并保存结果。,不可更改的,通过回溯确定最优解。,它的探索策略称为决策过程。。

  主要不同:两种算法的申请表格背景非常相似。,针对具体问题,两个属性直接与算法选择相关。,最优子结构性质性质与贪婪选择性质。

最优子结构性质性质是选择最优解的性质。,更确切地说,全面质量必须包括局优势。,不可更改的一个选择最短路线的例子已经说过了。。

当时,我们也提到了贪婪选择的本质。,满足贪心选择性质的问题可用贪心算法解决,不满足贪婪选择性质的问题只能通过。可见能用贪心算法解决的问题理论上都可以利用动态规划解决,一旦被证明贪婪,选择的性质。,用贪心算法解决问题比动态规划具有更低的时间复杂度和空间复杂度。

  贪心算法:

  1.贪心算法中,贪婪决策的每一步都不能改变。,因为贪婪策略从先前的OpTIM得到最优解。,不可更改的一个最好的解决方案没有保存下来。。

2。贪婪法的正确条件是:每一步的最优解必须包含P的最优解。。

  动态规划算法:

1。全局最优解必须包含局部最优解。,但它不一定包括第一局部最优解。,如此,我们需要记录所有最好的解决方案。

2。动态规划的关键是状态转移方程。。,更确切地说,如何从局部最优解导出全局最优解。

三。极限条件:这是最简单的。,可以直接得到局部最优解。

  所谓贪婪选择性质是全局最优解。,这是贪婪的选择来实现的。。这是利用贪心算法求解最优解的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

  在贪心算法中,贪婪决策的每一步都不能改变。,因为贪婪策略从先前的OpTIM得到最优解。,不可更改的一个最好的解决方案没有保存下来。。而且,每一步的最优解必须包含P的最优解。。

动态规划算法,全局最优解中一定包含某个局部最优解,但它不一定包括第一局部最优解。,如此,我们需要记录所有最好的解决方案。。动态规划的关键是状态转移方程。,更确切地说,如何从局部最优解导出全局最优解。。更确切地说,把一个复杂的问题分割成一个小问题。,每一个问题都能得到最好的解决方案。,并从这些最优解中得到一个更好的答案。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注