0009算法笔记——【动态规划】动态规划与斐波那契数列问题,最短路径问题分析报告.docx

1、动态规划算法： ? ? ? ?动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。? ? ? ? ? ? ?基本思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。 ? ? ? ?与分治法区别：动态规划算法与分治法类似，都使用了将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解出来的各个子问题的性质不同。分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子问题。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题)，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。? ? ? ? ? ?相关术语： ? ? ? (1)阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同，描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。 ? ? ? (2)状态：状态表示每个阶段开始面临的自然状况或客观条件，也称为不可控因素。过程的状态通常可以用一个或一组数来描述,称为状态变量。一般状态是离散的,但有时为了方便也将状态取成连续的。? ? ? ? (3)无后效性：状态具有下面的性质,如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路,所通过的点,的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。 ? ? ? (4)决策：一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多间题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。? ? ? ? (5)策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。 ? ? ? (6)最优性原理: 作为整个过程的最优策略,它满足,相对前面决策所形成的状态而言,余下的子策略必然构成―最优子策略。 ? ? ??问题特征： ? ? ? (1)最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 ? ? ? (2)重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。 ? ? ??算法步骤： ? ? ??(1)分析最优值的结构，刻画其结构特征； ? ? ? (2)递归地定义最优值； ? ? ? (3)按自底向上或自顶向下记忆化的方式计算最优 ? ? ?2、斐波那契数列(Fibonacci polynomial) ? ? ?计算斐波那契数列(Fibonacci polynomial)的一个最基础的算法是，直接按照定义计算： [cpp]?view plain?copy 1. //3m1?未优化斐波那契数列计算?? 2. #include?stdafx.h?? 3. #includeiostream??? 4. ?? 5. using?namespace?std;??? 6. ?? 7. void?input(int?n);?? 8. int?fib(int?n);?? 9. ?? 10. int?main()?? 11. {?? 12. ????int?n;?? 13.