参考教材：《算法设计与应用》 汪荣贵 杨娟 薛丽霞 机械工业出版社

第2章 算法设计的基本策略

2.1 蛮力与贪心

2.1.1 蛮力法

蛮力法也称为穷举法，基本思路是以扫描的模式依次处理问题域中的所有元素，并将所有可能的问题枚举出来，进而实现对问题的求解。

两个基本步骤：

  • 找到枚举范围。分析问题，找到所涉及的每一种情况。
  • 找到约束条件。解析约束条件，并用逻辑表达式表示。

2.1.1 贪心法

通过每一步中间结果的局部最优获得最终结果的全局最优。

2.1.3 应用实例

1、狱吏问题

某王国对囚犯进行大赦,让一狱吏n次通过一排锁着的n间牢房,每通过一次按所定规则转动门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后,门锁开着的,牢房中的犯人放出,否则犯人不得获释.转动门锁的规则是这样的,第一次通过牢房,要转动每一把门锁,即把全部锁打开；第二次通过牢房时,从第二间开始转动,每隔一间转动一次；第k次通过牢房,从第k间开始转动,每隔k-1 间转动一次；问通过n次后,那些牢房的锁仍然是打开的?

  1. //狱吏问题算法
  2. //用数组模拟n个锁的状态，1-锁上，0-打开
  3. //锁的一次变化函数为：a[i]=1-a[i] 
  5. //输入：锁状态为上锁的牢房个数n。
  6. //输出：锁状态为打开的牢房号k。 
  8. #include<iostream>
  9. using namespace std;
  11. int main(){
  12.     int n;
  13.     cin>>n;
  14.     int a[n];
  15.     for(int k=1;k<=n;k++)        //初始化锁
  16.         a[k]=1;
  17.     for(int k=1;k<=n;k++){
  18.         for(int j=k;j<=n;j=j+k){
  19.             a[k]=1-a[k];
  20.         }
  21.     } 
  23.     for(int k=1;k<n;k++){
  24. //        cout<<a[k]<<"\t";
  25.         if(a[k]==0)
  26.             cout<<k<<"\t";
  27.     }
  29.     return 0;
  30. }

2、背包问题

题目：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
0-1背包问题：在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。

背包问题蛮力算法
  1. //背包问题蛮力算法
  2. //给定三个重量为{7，3，4}，价值为{42，12，40}，以及一个容量为10的背包
  3. //最佳结果为{1，2} 
  5. //输入：背包容量c，物品种类n，物品重量w，物品价值v
  6. //输出：达到价值最大值的物品种类
  8. #include <iostream>
  9. #include <cmath>
  10. #include <string.h>
  12. int main(int argc, char* argv[]){
  13.     int c=10,n=3,w[3]={7,3,4},v[3]={42,12,40},res[3];
  14.     //indices用于输出价值最大值物品种类
  15.     bool indices[100]={0};
  16.     //n中物品的子集个数为2^n次方
  17.     int setCount=(int)pow(2.0,n);
  18.     int tmp,index=0;
  19.     int weight=0,value=0,max=0;
  20.     //二进制枚举法求价值最大值
  21.     for(int i=1;i<setCount;i++){
  22.         tmp=i;
  23.         index=0;
  24.         value=0;
  25.         weight=0;
  26.         //indices数组清零
  27.         memset(indices,0,n);
  28.         //整数转为二进制
  29.         while(tmp>0){
  30.             if(tmp%2){
  31.                 indices[index]=1;
  32.                 weight+=w[index];
  33.                 value+=v[index];
  34.                 if(weight>c){
  35.                     break;
  36.                 }
  37.             }
  38.             index++;
  39.             tmp/=2;
  40.         } 
  41.         if(weight<c&&value>max){
  42.             max=value;
  43.             for(int k=0;k<n;k++){
  44.                 res[k]=indices[k];
  45.             }
  46.         }
  48.     } 
  49.     std::cout<<max<<std::endl;
  51.     for(int k=0;k<n;k++){
  52.         std::cout<<res[k];
  53.     }
  54.     return 0;
  55. }

2.2 递归与分治

递归的基本思想

把一个问题归结为一个或多个规模更小的问题，然后用同样的方法解规模更小的子问题，要求子问题与原问题保持同一类型以保证可用同样方法求解，如此下去，知道子问题的规模小到可以直接求解为止。

分治的基本思想

将一个难以解决的大问题，分割成一些与原问题相同的，规模较小的子问题，以便分而治之，然后递归地解决子问题，最后把子问题的解组合成原问题的解。

2.2.1 递归法

直接或间接地调用自身的算法称为递归算法。

递归算法有三个基本要求：

  • 递归中每次循环都必须使问题规模变小
  • 递归操作种每相邻两步都是紧密关联的，在递归返回到上一层的操作中，前一次的输出便是后一次的输入
  • 当子问题的规模足够小时，必须能够直接求出子问题的解，也就是说必须具备结束递归的初始条件。
  1. // 阶乘问题算法
  2. // 输入： 自然数n
  3. // 输出：自然数n的阶乘
  5. #include <iostream>
  6. using namespace std; 
  8. double factorial(int n){
  9.     if(n==0) return 1;
  10.     else
  11.         return n*factorial(n-1);
  12. }
  14. int main(){
  15.     int n;
  16.     cin>>n;
  17.     cout<<factorial(n)<<endl;
  18.     return 0;
  19. }
  1. // Fibonacci数列算法
  2. // 输入： 自然数n
  3. // 输出: 第n个Fibonacci数 
  5. #include <iostream>
  6. using namespace std; 
  8. double Fibonacci(int n){
  9.     if(n==0||n==1) return 1;
  10.     else
  11.         return Fibonacci(n-1)+Fibonacci(n-2);
  12. }
  14. int main(){
  15.     int n;
  16.     cin>>n;
  17.     cout<<Fibonacci(n)<<endl;
  18.     return 0;
  19. }

2.2.2 分治法

分治法的设计思想是将一个难以解决的规模较大的问题，划分为一些容易解决的规模较小的问题，以便各个击破，分而治之。

基本步骤：

  • 将原问题分解为若干相同的子问题
  • 若子问题的国模容易解决则直接解决，否则继续分解
  • 将子问题的解合并得到原问题的解，当遇到如折半查找等某些不必求出所有子问题的解的情况，可省略合并操作。

2.3 回溯与分支界限

回溯和分治界限都是基于解空间搜索的方法。基本思路类似于蛮力法，首先对所有的解状态进行枚举，生成解空间或状态空间，然后通过在解空间中搜索获得所需要的解。这里的解空间是有结构的，解空间以空间树的结构方式存在。回溯法采用深度优先策略进行搜索，分支界限法则是以广度有限的策略机型搜索

2.3.1 回溯法

基本步骤：

  • 定义问题的解空间
  • 确定解空间结构
  • 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

    2.3.3 应用实例

    旅行售货员问题

    某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。
    image.png

    n皇后问题

    在使用回溯法求解n皇后问题是，需要定义一个数组x[n]来表示皇后的位置。其中，数组元素的下标表示皇后所在的行，数组元素的值表示皇后所在的列。在判断第n行的皇后与前n-1行的皇后是否有冲突时，使用如下两个条件：
  1. x[i]==x[n]，即两皇后处于同一列。
  2. |x[i]-x[n]|=|i-n|，即两皇后处于同一斜线上。

上述两个条件中任意一个成立，则认为第n行的皇后与前n-1行的皇后冲突。

2.4 动态规划

对于最短路线、库存管理、资源分配、设备更新、排序、装在等问题，用动态规划方法求解比用其它方法更加方便有效。

2.4.1 算法原理

将求解过程中所有子问题的解全部记录下来，无论该子问题以后是否会被其它子问题用到。可以看出，动态规划采用的是以空间换取时间的策略。

递归算法的时间复杂度呈指数变化。而是用动态规划的算法时间复杂度则是多项式数量级。因此，动态规划法大大节省了时间。

动态规划法的有效性依赖于求解问题的两个重要性质，即最优子结构性质和子问题重叠性值。

  • 最优子结构性质：如果问题最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质。最优子结构性质是动态规划求解问题的必要条件。
  • 子问题重叠性质。子问题重叠性质是指在用递归算法以自顶向下的方式对问题求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。当再次需要计算已经计算过的子问题时，无需再次计算，只需查表即可。

当确定待解决的问题可以使用动态规划算法求解时，通常按照以下几个步骤进行：

  1. 把所有最优化问题分成若干个阶段，找出最优解的性质，并刻画其结构特性。
  2. 将问题发展到各个阶段时所处的不同状态表示出来，确定各个阶段状态之间的递推（或递归）关系，并确定初始（边界）条件
  3. 应用递推（或递归）关系求解最优解。
  4. 根据计算最优解时得到的信息，构造最优解。