动态规划与贪心法的对比分析

Comparative analysis of dynamic programming and greedy

动态规划与贪心法是算法设计中比较重要的方法,它们都是采用分治思想把大问题分小,在降低成本的基础上达到最优;这两种方法有许多相似的地方,容易使人混淆;以求解最小生成树的Prim算法和多段图的最短路径问题为例,通过详细对比分析,指出动态规划与贪心法的差异性,帮助人们理解掌握二者之间的差别。

Dynamic programming and greedy algorithm design is more important methods, which are based on the ideological divide and conquer the big issue in small, optimal at reduced cost basis.These two methods are similar in many places, people are likely to be confused. In this paper, to solve the minimum spanning tree algorithm and Prim multistage shortest path graph, for example, Detailed comparative analysis, dynamic programming and greedy pointed out the difference, to help people understand and grasp the difference between the two.