跳到主要内容

算法设计

分治法​

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

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

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

凡是涉及到分组解决的都是分治法，例如归并排序算法完全依照上述分治算法的 3 个步骤进行。

  1. 分解：将 n 个元素分成各含 n/2 个元素的子序列。
  2. 求解：用归并排序对两个子序列递归地排序。
  3. 合并：合并两个已经排好序的子序列以得到结果。

动态规划法​

动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解决这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。

然而，不同子问题的数目常常只有多项式量级。如果 能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常按照以下几个步骤进行。

  1. 找出最优解的性质，并刻画其结构特征。
  2. 递归的定义最优解的值
  3. 以 自底向上的方式计算出最优值
  4. 根据计算最优值时得到的信息，构造出一个最优解

步骤 1~3 是动态规划算法的基本步骤。在只需要求出最优值的情形下，步骤 4 可以省略。若需要求出问题的一个最优解，则必须执行步骤 4

对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划算法来求解。

  1. 最优子结构：如果一个问题的最优解中包含了其子问题的最优，也就是说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划算法可能会适用，但是此时贪心策略可能也是适用的。
  2. 重叠子问题（不用重复计算）：重叠子问题是指用来求解原问题的递归算法可反复地求解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说明该问题包含重叠子问题。
提示

动态规划法用于求解全局最优解，分治法不用求最优

典型应用 0-1 背包问题​

有 n 个物品，第 i 个物品价值为 viv_i，重量为 wiw_i，其中 viv_i 和 wiw_i 均为非负数，背包的容量为 WW，WW 为非负数。现考虑如何选择装入背包的物品，使装入背包的物品总价值最大。

满足约束条件的任一集合（x1x_1,x2x_2,...,xnx_n） 是问题的一个可行解，问题的目标是要求问题的一个最优解。考虑一个实例，假设 n=5，W=17W=17，每个物品的价值和重量如表所示，可将物品 1、2 和 5 装入背包，背包未满，获得价值 22，此时问题解为 （1,1,0,0,1）;也可以将物品 4 和 5 装入背包，背包装满，获得价值 24 ，此时解为 (0,0,0,1,1)。

1. 刻画 0-1 背包问题的最优解的结构。​

可以将背包问题的求解过程看作是进行一系列决策的过程，即决定那些物品应该放入背包，那些物品不放入背包。如果一个问题的最优解包含了物品 n，即 xn=1x_n=1，那么其余 x1x_1,x2x_2,...,xn−1x_{n-1} 一定构成子问题 1,2,...,n-1 在容量 W−wnW-w_n 时的最优解 。如果这个 最优解不包含物品 n，即 xn=0x_n=0,那么 x1x_1,x2x_2,...,xn−1x_{n-1} 一定构成子问题 1,2,...,n-1 在容量为 W 时的最优解。

2. 递归求解最优解的值​

根据上述分析的最优解的结构递归地定义问题的最优解。设 c[i,w] 表示背包容量为 w 时 i 个物品导致的最优解的总价值，得到下式。显然，问题要求 c[n,W]

c[i,w]={0                        ,i=0orw=0c[i−1,w],  wi>Wmax{c[i−1,w−wi]+vi,c[i−1,w]},  i>0andwi≤Wc[i,w] = \begin{cases} 0\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,,i=0 \quad or \quad w=0\\ c[i-1,w],\,\,w_i > W\\ max\{c[i-1,w-w_i]+v_i,c[i-1,w]\},\,\, i>0 \quad and \quad w_i \leq W\\ \end{cases}
提示

在判断第 i 个物品能不能加入背包时，默认前 i-1 个已经达到了最优解。

使用动态规划法求解0-1背包问题的时间复杂度是 O(nW)O(nW)

贪心法​

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

提示

动态规划法从全局的角度出发，一定可以得到一个最优解；贪心法只考虑当前，只考虑局部的，可能会得出最优，也可能得不到。

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

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

典型应用：背包问题​

背包问题的定义与 0-1 背包问题类似，但是 每个物品可以部分装入背包，即在 0-1 背包问题中， xi=0x_i=0 或者 xi=1x_i=1；而在背包问题中 ，0≤xi≤10\leq x_i \leq 1

为了更好的分析此问题，考虑一个例子：n = 5，W = 100，下表给出了各个物品的重量、价值和单位重量的价值。假设物品已经按照其单位重量的价值从大到小排好序。

为了得到最优解，必须把背包放满。现在适用贪心策略求解，首先要选出度量的标准。

  1. 按最大价值先放背包的原则
  2. 按最小重量先放背包的原则
  3. 按最大单位重量价值先放背包的原则

回溯法​

有 “通用的解题法”之称，可以系统地搜索一个问题的所有解或任一解。在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间树。搜索至任一结点时，总是 先判断该节点是否肯定不包含问题的解，如果不包含，则跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。

可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外的分支，重复此步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层。

一般用于解决迷宫类的问题