分治 贪婪 动态规划 回溯 穷举

参考网站 : 豆瓣

分治算法 (分割統治法)

ぶんかつ　とうち　ほう

基本概念

CS中分治法是一种重要算法。即 “分而治之” , 把一个复杂问题分成两个或更多的相同或相似的子问题 , 再把子问题分成更小的子问题 , 直到最后子问题可以简单的直接求解 , 原问题的解即子问题的解的合并。

分治法是很多高效算法的基础 , 如排序算法 (快排 , 归并) , 傅里叶变换 (快速傅里叶变换)。

任何一个可用计算机求解的问题所需的计算时间都与其规模有关。
问题的规模越小 , 越容易直接求解 , 解题所需的计算时间也越少。

基本思想和策略

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1≤k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

分治法能解决的问题一般有以下特征 :

• 该问题的规模缩小到一定的程度就可以很容易地解决
• 该问题可以分解为若干个规模较小的相同问题 , 即该问题具有最优子结构性质。
• 利用该问题分解出的子问题的解可以合并为该问题的解
• 该问题所分解出的各个子问题是相互独立的 , 即子问题之间不包含公共的子子问题

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

基本步骤

分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

Divide-and-Conquer（P） 
1. if |P| ≤ n0 
2. then return（ADHOC（P）） 
3. 将P分解为较小的子问题 P1 ，P2 ，。。。，Pk 
4. for i←1 to k 
5. do yi ← Divide-and-Conquer（Pi） △ 递归解决Pi 
6. T ← MERGE（y1，y2，。。。，yk） △ 合并子问题 
7. return（T）

其中 , P表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。

ADHOC（P）是该分治法中的基本子算法，用于直接解小规模的问题P。
因此，当P的规模不超过n0时直接用算法ADHOC（P）求解。
算法MERGE（y1，y2，。。。，yk）是该分治法中的合并子算法，用于将P的子问题P1 ，P2 ，。。。，Pk的相应的解y1，y2，。。。，yk合并为P的解。

复杂度分析

一个分治法将规模为n的问题分成k个规模为 n/m 的子问题去解。
设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。
再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用 f(n) 个单位时间。

用 T(n) 表示该分治法解规模为P=n的问题所需的计算时间，则有：

通过迭代法求得方程的解：
递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。
通常假定T(n)是单调上升的，从而当 mi ≤ n ≤ mi+1时，T（mi）≤ T（n）≤ T（mi+1）。

动态规划算法

基本概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。
一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

贪心算法

Greedy Algorithm

简介

是寻找最优解问题问题的常用方法。这种方法一般将求解过程分解成若干个步骤 , 但每个步骤都应用贪心原则 , 选取当前状态下最好 / 最优的选择 (局部最有利的选择) , 并希望后面堆叠出的结果也是最好 / 最优的解。

基本步骤

1. 从某个初始解出发；
2. 采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
3. 将所有解综合起来。

一些问题

根据算法导论 , 实际上背包问题和Coin Change问题不能用贪心算法解决 , 贪心算法需要最核心的证明 : “局部最优解->全局最优解”

例 : 找零钱问题

某商店只收现金 , 钱柜里的货币只有 25分 , 10分 , 5分 和 1分 四种硬币 , 如果你是售货员并要找给客人 41分钱的硬币 , 如何安排才能使硬币个数最少 ?

按上述步骤来 :

1. 找给客人 sum_money = 41 分钱 , 能找25分则不找10分 , 先找25分钱
2. 还差 sum_money = 16 分钱 , 能找10分不找5分 , 再找10分钱。从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客 , 重复迭代 , 还差 sum_money = 6 分钱 , 找5分 , 再找1分
3. 此时41分，分成了1个25，1个10，1个5，1个1，共四枚硬币。

C语言实现

#include<iostream>
using namespace std;

#define OneCent    1
#define FiveCent    5
#define TenCent    10
#define TwentyFiveCent 25

int main()
{
    int sum_money=41;
    int num_25=0,num_10=0,num_5=0,num_1=0;

    //不断尝试每一种硬币
    while(money>=TwentyFiveCent) { num_25++; sum_money -= TwentyFiveCent; }
    while(money>=TenCent) { num_10++; sum_money -= TenCent; }
    while(money>=FiveCent)  { num_5++;  sum_money -= FiveCent; }
    while(money>=OneCent)  { num_1++;  sum_money -= OneCent; }

    //输出结果
    cout<< "25分硬币数："<<num_25<<endl;
    cout<< "10分硬币数："<<num_10<<endl;
    cout<< "5分硬币数："<<num_5<<endl;
    cout<< "1分硬币数："<<num_1<<endl;

    return 0;
}

背包最大价值问题

简介

有一个背包，最多能承载重量为C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为 1~7，重量分别是 wi=[35,30,60,50,40,10,25]，价值分别是 pi=[10,40,30,50,35,40,30]，现在从这 7 个物品中选择一个或多个装入背包，要求在物品总重量不超过 C 的前提下，所装入的物品总价值最高。

需要明确的点 :

1. 每个物品都有重量和价值
2. 每个物品都有被选中和不被选中两种状态 (flag)
3. 背包总的承重一定 , 可选物品列表已知

定义 : typedef

// typedef是类型定义的意思
typedef struct tagObject
{
    int weight;
    int price;
    int status;
}OBJECT;

//定义背包问题
typedef struct tagKnapsackProblem
{
    vector<OBJECT>objs;
    int totalC;
}KNAPSACK_PROBLEM;

这里采用定义结构体的形式，主要是可以减少代码的书写量,可以实现代码的复用性和可扩展性,简化，提高可读性。就是贪图简单方便，规避繁琐。

实例化 objects

OBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },
                    { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };

怎样选 ?

根据不同的主导 , 有三种策略 :

1. 价值主导 , 每次都选择**价值最高**的物品放入背包
2. 重量主导 , 每次都选择**重量最轻**的物品放入背包

3. 价值密度主导选择 , 每次都选择 **价值/重量** 最高的物品放入背包

   价值主导选择

   每次都选择价值最高的物品放入背包
   根据这个策略最终选择装入背包的物品编号依次是 **4、2、6、5**，此时包中物品总重量是 130，总价值是 165。

   //遍历没有被选的objs,并且选择price最大的物品,返回被选物品的编号
   int Choosefunc1(std::vector<OBJECT>& objs, int c)
   {
    int index = -1;  //-1表示背包容量已满
    int max_price = 0;
    //在objs[i].status == 0的物品里，遍历挑选objs[i].price最大的物品
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if ((objs[i].status == 0) && (objs[i].price > max_price ))
                            //objs没有被选,并且price> max_price 
        {
            max_price  = objs[i].price;
            index = i;
        }
    }
   
    return index;
   }
   

   重量主导选择

   每次都选择重量最轻(小)的物品放进背包
   根据这个策略最终选择装入背包的物品编号依次是 **6、7、2、1、5**，此时包中物品总重量是 140，总价值是 155。

   int Choosefunc2(std::vector<OBJECT>& objs, int c)
   {
    int index = -1;
    int min_weight= 10000;
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if ((objs[i].status == 0) && (objs[i].weight < min_weight))
        {
            min_weight= objs[i].weight;
            index = i;
        }
    }
   
    return index;
   }
   

   价值密度主导选择

   每次都选择 **价值/重量** 最高的物品放入背包
   物品的价值密度 si 定义为 pi/wi，这 7 件物品的价值密度分别为 si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]。根据这个策略最终选择装入背包的物品编号依次是 6、2、7、4、1，此时包中物品的总重量是 150，总价值是 170。

   int Choosefunc3(std::vector<OBJECT>& objs, int c)
   {
    int index = -1;
    double max_s = 0.0;
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if (objs[i].status == 0)
        {
            double si = objs[i].price;
            si = si / objs[i].weight;
            if (si > max_s)
            {
                max_s = si;
                index = i;
            }
        }
    }
   
    return index;
   }
   

   将物品和方法结合起来的贪心算法 **GreedyAlgo**

   void GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc)
   {
    int idx;
    int sum_weight_current = 0;
    //先选
    while ((idx = spFunc(problem->objs, problem->totalC- sum_weight_current)) != -1)
    {   //再检查，是否能装进去
        if ((sum_weight_current + problem->objs[idx].weight) <= problem->totalC)
        {
            problem->objs[idx].status = 1;//如果背包没有装满，还可以再装,标记下装进去的物品状态为1
            sum_weight_current += problem->objs[idx].weight;//把这个idx的物体的重量装进去，计算当前的重量
        }
        else
        {
            //不能选这个物品了，做个标记2后重新选剩下的
            problem->objs[idx].status = 2;
        }
    }
    PrintResult(problem->objs);//输出函数的定义，查看源代码
   }
   

   注意：这里对objs[idx].status定义了三种状态，分别是待选择为0（初始所有状态均为0），装进包里变为1，判断不符合变为2，这样最后只需要拿去状态为1的即可。

主函数部分

OBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },
                    { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };
int main()
{
    KNAPSACK_PROBLEM problem;

    problem.objs.assign(objects, objects + 7);//assign赋值，std::vector::assign
    problem.totalC = 150;

    cout << "Start to find the best way ,NOW" << endl;
    GreedyAlgo(&problem, Choosefunc3);

    system("pause");
    return 0;
}

贪心算法的缺点

但是，我们再回顾一下第一个事例问题
现在问题变了，还是需要找给顾客41分钱，现在的货币只有 25 分、20分、10 分、5 分和 1 分四种硬币；该怎么办？
按照贪心算法的三个步骤：
1.41分，局部最优化原则，先找给顾客25分；2.此时，41-25=16分，还需要找给顾客10分，然后5分，然后1分；3.最终，找给顾客一个25分，一个10分，一个5分，一个1分，共四枚硬币。
是不是觉得哪里不太对，如果给他2个20分，加一个1分，三枚硬币就可以了呢？^_^;
总结：贪心算法的优缺点
优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；
缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。