法的本质

一般意义上的贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。Dijkstra算法显然是从整体最优考虑，求出的最短路径，一定是整体最优解，这是和一般意义上的贪心算法相悖的地方。而且Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在我看来，Dijkstra算法更接近动态规划。从维基百科也可以看到这样的说明：From a dynamic programming point of view, Dijkstra"s algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.

一般意义上的贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。Dijkstra算法显然是从整体最优考虑，求出的最短路径，一定是整体最优解，这是和一般意义上的贪心算法相悖的地方。而且Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在我看来，Dijkstra算法更接近动态规划。从维基百科也可以看到这样的说明：From a dynamic programming point of view, Dijkstra"s algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.

1. 贪心法（Greedy Algorithm）定义 求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择； 贪心法就是这样的算法：它在每个决策点作出在当时看来最佳的选择，即总是遵循某种规则，做出局部最优的选择，以推导出全局最优解（局部最优解->全局最优解）2. 对贪心法的深入理解 （1）原理：一种启发式策略，在每个决策点作出在当时看来最佳的选择 （2）求解最优化问题的两个关键要素：贪心选择性质+最优子结构 ①贪心选择性质：进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解； ②最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质 （3）解题关键：贪心策略的选择 贪心算法不是对所有问题都能得到整体最优解的，因此选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 （4）一般步骤： ①建立数学模型来描述最优化问题； ②把求解的最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解； ③证明做出贪心选择后： 1°原问题总是存在全局最优解，即贪心选择始终安全； 2°剩余子问题的局部最优解与贪心选择组合，即可得到原问题的全局最优解。 并完成2°3. 贪心法与动态规划 最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。