动态规划、回溯搜索、分治算法、分支限界算法

vlambda
2020-01-09

动态规划、回溯搜索、分治算法、分支限界算法

数学建模指南

1.热爱建模

2.好好生活

3.特别的人关注数学建模

4.你好，建模人

This browser does not support music or audio playback. Please play it in WeChat or another browser.

——

动态规划、回溯搜索、分治算法、分支限界算法

作为常用的四类算法，他们之间也有着紧密的联系：

分治法和动态规划法：二者都要求原问题具有最优子结构性质，都将原问题分成若干个子问题，然后将子问题的解合并，形成原问题的解。

回溯法和分支限界法：一种在问题的解空间树上搜索问题解的算法。

现在我来给大家仔细介绍它们吧！

动态规划

动态规划(dynamic programming)是运筹学的一个分支，它把多阶段过程转化为一系列单阶段问题逐个求解是求解决策过程(decision process)最优化的数学方法。

基本思想：动态规划算法通常用于求解具有某种最优性质的问题。与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，但分冶法得到的子问题过多，而动态规划能保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，这也是其一大优势。

基本定理和基本方程

基本定理通常略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。

根据基本定理的推论可以得到动态规划的基本方程：

\begin{cases}f_k(x_k)=opt\left\{\varphi(v_k(x_k,u_k),f_{k+1}(x_{k+1}))\right\},x_{k+1}=T_k(x_k,u_k),k=1,2,\cdots,n \\ f_{n+1}(x_{n+1})=\delta(x_{n+1})\end{cases}(1)

基本方程在动态规划中起着更为本质的作用。

回溯算法

概念:回溯算法实际上一个类似枚举的搜索尝试过程，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。可以理解为：

回溯法是一种选优搜索法，按选优条件向前搜索而满足回溯条件的某个状态的点称为“回溯点”。

它适用于解一些组合数较大的问题，有着可见回溯法有“通用解题方法”的美称。

基本思想

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

1、针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。

2、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。

3、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

4、确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

——回溯算法解决问题的一般步骤

分支限界法

分枝界限法能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。 ——概念

基

本

思

想

对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。