n b # 算法的特性

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性：

• 有穷性。算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
• 可行性：一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合
• 输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的

分治法

分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。如果规模为n的问题可分解成k个子问题,1\<k≤n，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。

一般来说，分治算法在每一层递归上都有3个步骤。

• 分解：将原问题分解成一系列子问题。
• 求解：递归地求解各子问题。若子问题足够小则直接求解。
• 合并：将子问题的解合并成原问题的解

动态规划法

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常按照以下几个步骤进行。

贪心法

和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换而言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。

贪心法问题一般具有两个重要的性质：

• 最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或求解的关键性质
• 贪心选择性质：指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和题具有贪动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点

回溯法

有通用解题法之称，可以系统地搜索一个问题的所有解或任一解。在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。搜索至任一节点时，总是先判断该节点是否肯定不包含问题的解，如果不包含，则跳过对以该节点为根的字数的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。
可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外的分支，重复此步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层。

分支限界法

原理：在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
与回溯法的区别:
1、求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
2、以广度优先或以最小耗费(最大收益)优先的方式搜索解空间树。
从活节点表中选择下一个扩展节点的类型:
队列式(FIFO)分支限界法:按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。
优先队列式分支限界法:按照b 优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。