|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
|
|
|
|
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，希望找到具有最优值（最大值或最小值）的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常可按照以下几个步骤进行。
|
|
|
|
|
|
|
|
|
|
（4）根据计算最优值时得到的信息，构造一个最优解。
|
|
|
|
对一个给定的问题，若其具有以下两个性质，则可以考虑用动态规划法来求解。
|
|
|
|
（1）最优子结构。如果一个问题的最优解中包含其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，表示动态规划法可能会适用，但是此时贪心策略可能也是适用的。
|
|
|
|
（2）重叠子问题。它指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说明该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法的搜索策略是，每一个活节点只有一次机会成为扩展节点。活节点一旦成为扩展节点，就一次性产生其所有儿子节点。在这些儿子节点中，那些导致不可行解或非最优解的儿子节点被舍弃，其余儿子节点被加入到活节点表中。此后，从活节点表中取下一节点成为当前扩展节点，并重复上述节点扩展过程。这个过程一直持续到找到所需的解或活节点表为空时为止。
|
|
|
|
从活节点表中选择下一扩展节点的不同方式导致不同的分支限界法。最常用的有队列式分支限界法和优先队列分支限界法。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯；扩大当前候选解的规模，以继续试探的过程称为向前试探。
|
|
|
|
应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。
|
|
|
|
确定了解空间的组织结构后，回溯法从开始节点（根节点）出发，以深度优先的方式搜索整个解空间。这个开始节点就称为一个活节点，同时也称为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活节点，并成为当前扩展节点。如果在当前扩展节点处不能再向纵深方向移动，则当前的扩展节点就成为死节点。换句话说，这个节点不再是一个活节点。此时，应往回移动（回溯）至最近的一个活节点处，并使这个活节点成为当前的扩展节点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活节点时为止。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
和动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息作出选择，而且一旦作出选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所作出的选择只是在某种意义上的局部最优。
|
|
|
|
|
|
（1）最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
|
|
|
|
（2）贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。
|
|
|
|
|
|
|
|
|
|
|
|
|
