搜索算法之深度优先、广度优先、约束条件、限界函数及相应算法

常见的搜索算法可以结合枚举策略和剪枝策略：

枚举策略    剪枝策略
深度优先    约束条件
广度优先    限界函数

其中，枚举策略有且仅有一种（或是深度优先，或是广度优先），剪枝策略则可以是约束条件、限界函数之一或两者兼而有之或两者都不考虑，然后就有了经典的枚举法（蛮力法）、回溯法、加限界的回溯法、分支限界法。

限界函数和约束条件的目标：

约束条件，是为了去掉不可行解，从而进行剪枝。

限界函数，是为了去掉非最优解（依然是可行解），从而剪枝。如果题目需要求多个可行解，那么就不可能使用限界函数。

明确了这两个目标，就能够更加针对性选择了：

Let us consider below 0/1 Knapsack problem.

下面让我们考虑0/1背包问题。

Given two integer arrays val[0…n-1] and wt[0…n-1] that represent values and weights associated with n items respectively. Find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to Knapsack capacity W.

给定两个整数数组val[0…n-1]和wt[0…n-1]，分别表示与n个项相关联的值和权重。找出val[]的最大值子集，使该子集的权重之和小于或等于背包容量W。

Let us explore all approaches for this problem.

让我们探讨解决这个问题的所有方法。

1. A Greedy approach is to pick the items in decreasing order of value per unit weight. The Greedy approach works only for fractional knapsack problem and may not produce correct result for 0/1 knapsack.

1 一种贪婪的方法是按每单位重量值的降序选取项目。贪心方法只适用于分数背包问题，对于0/1背包问题可能无法得到正确的结果。

0/1背包问题：我们有一堆物品S={a1,a2,…,an}，每个物品ai都有一个重量wi和一个价值vi。现在有一个背包，这个背包的容量为W，现在要将这些物品在不超越背包容量的情况下选择性地放入背包，使得背包里面物品的价值最大，物品不能只选取其中一部份，必须选择全部，或不选！（放与不放到背包里，采用二进制表示，1表示放入背包，0表示不放入背包。）

分数背包问题：这个问题和上面的问题比较类似，唯一不同的就是该问题里面的物品可以进行分割，便可以只选取1个物品ai的一部份。

2. We can use Dynamic Programming (DP) for 0/1 Knapsack problem. In DP, we use a 2D table of size n * W. The DP Solution doesn’t work if item weights are not integers.

2 我们可以用动态规划（DP）求解0/1背包问题。在DP中，我们使用大小为n * w的2D表。如果项目权重不是整数，DP解决方案就不起作用。

3. Since DP solution doesn’t alway work, a solution is to use Brute Force. With n items, there are 2^n solutions to be generated, check each to see if they satisfy the constraint, save maximum solution that satisfies constraint. This solution can be expressed as tree.

3 由于DP解决方案并不总是有效的，一个解决方案是使用暴力。对于n个项目，将生成2^n个解，检查每个解是否满足约束，保存满足约束的最大解。这个解可以表示为树。

示例代码：

#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
#define DIM 5

void possible_solution(int arr[DIM]){
    for(int i=0;i<DIM;i++)  // n=4,有2^4-1种解法
        if(arr[i]!=1)
        {
            arr[i]=1;
            return;	// 从遇到的第一位开始，若是0，将其变成1，然后结束循环，得到一种解法
        }
        else
            arr[i]=0;
        return;		// 从第一位开始，若是1，将其变成0，然后继续循环，若再循环的时候遇到0，
					// 则将其变为1，结束循环。得到另一种解法。 
}

int main()
{
    int count=0;
    double weight[DIM]={2,3.14,1.98,5,3};
    double  value[DIM]={40,50,100,95,30};
    int x[DIM]={0};
    int y[DIM]={0};
    double weightLimit=10;
	double maxv = 0;
    for(int j=1;j<=pow(2,DIM);j++)
    {
        possible_solution(x);
        count++;
        int i;
        for(i=0;i<DIM;i++)
            cout<<x[i]<<" ";
        cout<<endl;
		double tw = 0, tv = 0;
        for(i=0;i<DIM;i++)
            tw+=x[i]*weight[i];
        for(i=0;i<DIM;i++)
            tv+=x[i]*value[i];
        if(tw <= weightLimit && tv>maxv)
		{
            maxv=tv;
			for(i=0;i<DIM;i++)
				y[i]=x[i];
        }
    }
    cout<<"共有"<<count<<"种解法."<<endl;
    printf("其中0-1背包问题的最优解为：y = ");
	for(int i=0;i<DIM;i++)
		printf("%d ",y[i]);
	printf("\n");
    printf("总价值为：%f",maxv);
    while(1);
}
/*
1 0 0 0 0
0 1 0 0 0
1 1 0 0 0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 0
1 1 1 0 0
0 0 0 1 0
1 0 0 1 0
0 1 0 1 0
1 1 0 1 0
0 0 1 1 0
1 0 1 1 0
0 1 1 1 0
1 1 1 1 0
0 0 0 0 1
1 0 0 0 1
0 1 0 0 1
1 1 0 0 1
0 0 1 0 1
1 0 1 0 1
0 1 1 0 1
1 1 1 0 1
0 0 0 1 1
1 0 0 1 1
0 1 0 1 1
1 1 0 1 1
0 0 1 1 1
1 0 1 1 1
0 1 1 1 1
1 1 1 1 1
0 0 0 0 0
共有32种解法.
其中0-1背包问题的最优解为：y = 1 0 1 1 0
总价值为：235.000000
*/

We can use Backtracking to optimize the Brute Force solution. In the tree representation, we can do DFS of tree. If we reach a point where a solution no longer is feasible, there is no need to continue exploring. In the given example, backtracking would be much more effective if we had even more items or a smaller knapsack capacity.

我们可以使用回溯来优化暴力解决方案。在树表示中，我们可以做树的DFS。如果我们到了一个解决方案不再可行的地步，就没有必要继续探索。在给定的例子中，如果我们有更多的物品或更小的背包容量，回溯将更加有效。

回溯法的一般思路：

void Backtracking()
{
    If you are already at a solution, report success.
    for ( every possible choice in the current position )
    {
        1 Make that choice and take one step along the path.
        2 Use recursion to solve the problem from the new position.
        3 If the recursive call succeeds, report the success to the next higher level.
        4 If not, back out of the current choice to restore the previous state.
    }
    Report failure.
}

01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。

在搜索状态空间树时，只要左子节点是一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。

上界函数bound()：当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。　

为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。

利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量xi （即对n个物品放或不放的一种的方案）。

其中， (xi = 0 或１，xi = 0表示物体ｉ不放入背包，xi ＝1表示把物体ｉ放入背包）。

在递归函数Backtrack中，当i>n时，算法搜索至叶子结点，得到一个新的物品装包方案。此时算法适时更新当前的最优价值。

当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。

回溯法求01背包问题：

① 用约束函数在扩展结点处剪除不满足约束的子树；

② 用限界函数剪去得不到问题解或最优解的子树。

#include <iostream>
#include <stdio.h>
using namespace std;

int n;          //物品数量
double c;       //背包容量
double v[100];  //各个物品的价值　value
double w[100];  //各个物品的重量　weight
double cw = 0.0;//当前背包重量　current weight
double cp = 0.0;//当前背包中物品总价值　current value
double bestp = 0.0; //当前最优价值best price
double perp[100];   //单位物品价值(排序后) per price
int order[100];     //物品编号
int put[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据

void knapsack()             // 按单位价值排序
{
    int i,j;
    int temporder = 0;
    double temp = 0.0;
    
    for(i=1;i<=n;i++)
        perp[i]=v[i]/w[i];      //计算单位价值（单位重量的物品价值）
    for(i=1;i<=n-1;i++)
    {
        for(j=i+1;j<=n;j++)
            if(perp[i]<perp[j]) //冒泡排序perp[],order[],sortv[],sortw[]
            {
                temp = perp[i];     //冒泡对perp[]排序
                perp[i]=perp[j];
                perp[j]=temp;
                
                temporder=order[i]; //冒泡对order[]排序
                order[i]=order[j];
                order[j]=temporder;
                
                temp = v[i];        //冒泡对v[]排序
                v[i]=v[j];
                v[j]=temp;
                
                temp=w[i];          //冒泡对w[]排序
                w[i]=w[j];
                w[j]=temp;
            }
    }
}

void backtrack(int i)       //回溯函数
{   //i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品
    double bound(int i);
    if(i>n) //递归结束的判定条件
    {
        bestp = cp;
        return;
    }
    // 如若左子节点可行，则直接搜索左子树;
    // 对于右子树，先计算上界函数，以判断是否将其减去
    if(cw+w[i]<=c)  // 将物品i放入背包，搜索左子树
    {
        cw+=w[i];   // 同步更新当前背包的重量
        cp+=v[i];   // 同步更新当前背包的总价值
        put[i]=1;
        backtrack(i+1); // 深度搜索进入下一层
        cw-=w[i];       // 回溯复原
        cp-=v[i];       // 回溯复原
    }
    if(bound(i+1)>bestp)// 若符合条件则搜索右子树
        backtrack(i+1);
}

double bound(int i)     // 计算上界函数，功能为剪枝
{   // 判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值
    double leftw= c-cw; // 剩余背包容量
    double b = cp;      // 记录当前背包的总价值cp,最后求上界
    //以物品单位重量价值递减次序装入物品
    while(i<=n && w[i]<=leftw)
    {
        leftw-=w[i];
        b+=v[i];
        i++;
    }
    // 装满背包
    if(i<=n)
        b+=v[i]/w[i]*leftw;
    return b;// 返回计算出的上界 
}

int main()
{
    int i;
    printf("请输入物品的数量和背包的容量：");
    scanf("%d %lf",&n,&c);

    printf("请依次输入%d个物品的重量:\n",n);
    for(i=1;i<=n;i++){
        scanf("%lf",&w[i]);
        order[i]=i;
    }
    
    printf("请依次输入%d个物品的价值:\n",n);
    for(i=1;i<=n;i++){
        scanf("%lf",&v[i]);
    }
    
    knapsack();
    backtrack(1);
    
    printf("最优价值为：%lf\n",bestp);
    printf("需要装入的物品编号是：");
    for(i=1;i<=n;i++)
    {
        if(put[i]==1)
            printf("%d ",order[i]);
    }
    while(1);
    return 0;
}
/*
5
10
2
3.14
1.98
5
3
40
50
100
95
30  
*/

/*
请输入物品的数量和背包的容量：5
10
请依次输入5个物品的重量:
2
3.14
1.98
5
3
请依次输入5个物品的价值:
40
50
100
95
30
最优价值为：235.000000
需要装入的物品编号是：3 1 4
*/

The backtracking based solution works better than brute force by ignoring infeasible solutions. We can do better (than backtracking) if we know a bound on best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.

基于回溯的解决方案通过忽略不可行的解决方案比暴力解决方案效果更好。如果我们知道每个节点根上的最佳可能解子树的界，我们可以做得更好（比回溯）。如果子树中的最佳值比当前最佳值差，我们可以忽略此节点及其子树。因此，我们计算每个节点的边界（最佳解），并在探索节点之前将边界与当前最佳解进行比较。

Example bounds used in below diagram are, A down can give $315, B down can $275, C down can $225, D down can $125 and E down can $30.

下图中使用的示例边界是，A向下可以给出315美元，B向下可以给出275美元，C向下可以给出225美元，D向下可以给出125美元，E向下可以给出30美元。

Branch and bound is very useful technique for searching a solution but in worst case, we need to fully calculate the entire tree. At best, we only need to fully calculate one path through the tree and prune the rest of it.

分枝定界是搜索解的一种非常有用的技术，但在最坏的情况下，我们需要完全计算整个树。充其量，我们只需要完全计算通过树的一条路径，然后修剪其余的路径。

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. Branch and Bound solve these problems relatively quickly.

分枝定界是一种常用于求解组合优化问题的算法设计范式。这些问题的时间复杂度通常是指数级的，在最坏的情况下可能需要研究所有可能的排列。分支定界可以较快地解决这些问题。

示例代码：

/*
测试数据：
5
10
2 3.14 1.98 5 3
40 50 100 95 30
packageWeight = 10
n = 5
weight = {2,2,6,5,4}
value = {6,3,5,4,6}
*/

#include <iostream>
#include <queue>
using namespace std;

class AnswerWay
{
public:
    AnswerWay *parent;  // 指向父亲结点
    bool way;           // 是左边进入还是右边进入
};

class Node
{
public:
    operator double() const // 比较优先级
    {
        return priority;
    }
    double priority;    // 结点的优先级
    double nowValue;    // 当前结点的价值
    double nowWeight;   // 当前重量
    int level;          // 当前的层数
    AnswerWay *answer;  // 结点路径
};

class Package
{
public:
    void getMaxValue(); // 获取最大值
private:
    void addPriorityQueue(double, double, double, int, bool);// 加入优先队列
    double bound(int);  // 求出价值上界
    double maxValue();  // 背包的可容纳最大价值
    void sort();        // 对物品单位价值进行排序
    void init();        // 对package的各个属性进行初始化
    void destructor();  // 清理new产生的空间
    void getError()     // 测试错误,可删除
    {
        for(int i = 0; i <= n; i++)
            cout<<"value = "<<value[i]<<" weight = "<<weight[i]<<endl;
    }
private:
    double packageWeight;   // 背包的重量
    int n;                  // 物品的总数
    double* weight;         // 每个物品的重量
    double* value;          // 每个物品的价值
    double nowWeight;       // 背包的当前重量
    double nowValue;        // 背包的当前价值
    int level;              // 当前层次
    priority_queue<Node> prQueue;   // 优先队列
    AnswerWay *answer;  // 结点路径
    bool* bestWay;      // 最优解
};

void Package::destructor()	// 清除new产生的空间
{
    delete[] weight;
    delete[] value;
    delete[] bestWay;
}

void Package::getMaxValue()	// 获取到背包的最优值
{
    init();
    sort();
    cout<<"背包可容纳的最优值为: "<<maxValue()<<endl;   // 获取最优值
    cout<<"最优解为: "<<endl;                           // 获取最优解
    for(int i = 1; i <= n; i++)
        if(bestWay[i])
            cout<<"weight = "<<weight[i]<<" value = "<<value[i]<<endl;
    destructor();
}

double Package::maxValue()		// 计算背包的最优值
{
    double bestValue = 0;       // 当前最优值
    double priority = bound(1); // 价值上界，也就是将要加入优先队列中的优先级
    Node node = Node();         // 结点应放在外面定义
    
    while(level != (n+1))
    {
        if((nowWeight+weight[level]) <= packageWeight)
        {
            if((nowValue+value[level]) > bestValue)
                bestValue = nowValue + value[level];
            // 左儿子的价值上界是包括了该结点的
            addPriorityQueue(priority, nowValue+value[level], nowWeight+weight[level], level+1, true);
        }
        // level+1是因为这一层的物品没有放进背包，对右儿子来说，剩余价值就是从level+1开始
        priority = bound(level+1);
        if(priority >= bestValue)
            addPriorityQueue(priority, nowValue, nowWeight, level+1, false);
        
        node = prQueue.top();	// 从优先队列中获取到优先级最高的元素
        prQueue.pop();
        // 更新当前各个属性值
        nowWeight = node.nowWeight;
        nowValue = node.nowValue;
        priority = node.priority;
        answer = node.answer;
        level = node.level;
    }
    
    for(int i=n; i>0; i--)
    {
        bestWay[i] = answer->way;
        answer = answer->parent;
    }
    return bestValue;
}

void Package::sort()		// 对物品单位价值进行排序
{
    double tempUnitValue;	// 临时单位价值
    double tempValue;		// 临时价值
    double tempWeight;		// 临时重量
    
    double *unitValue = new double[n+1];	// 物品的单位价值
    unitValue[0] = 0;
    for(int i = 1; i <= n; i++)
        unitValue[i] = double(value[i])/double(weight[i]);
    for(i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            if(unitValue[i] < unitValue[j])
            {
                tempUnitValue = unitValue[i];
                unitValue[i] = unitValue[j];
                unitValue[j] = tempUnitValue;
                
                tempValue = value[i];
                value[i] = value[j];
                value[j] = tempValue;
                
                tempWeight = weight[i];
                weight[i] = weight[j];
                weight[j] = tempWeight;
            }
        }
    }
    delete[] unitValue;
}

void Package::init()	// 对package的各个属性进行初始化
{
    cout<<"请输入有多少个物品: "<<endl;
    cin>>n;
    cout<<"请输入背包的容量: "<<endl;
    cin>>packageWeight;
    weight = new double[n+1];
    weight[0] = 0;
    cout<<"请输入各个物品的重量: "<<endl;
    for(int i = 1; i <= n; i++)
        cin>>weight[i];
    value = new double[n+1];
    value[0] = 0;
    cout<<"请输入各个物品的价值: "<<endl;
    for(i = 1; i <= n; i++)
        cin>>value[i];
    nowValue = 0;
    nowWeight = 0;
    level = 1;
    answer = 0;
    bestWay = new bool[n+1];
    for(i = 0; i <= n; i++)
        bestWay[i] = false;
}

/*加入优先队列*/
void Package::addPriorityQueue(double priority, double nowValue, double nowWeight, int level, bool ch)
{
    AnswerWay *answerTemp = new AnswerWay;
    answerTemp->parent = answer;
    answerTemp->way = ch;
    
    Node node = Node();
    node.priority = priority;
    node.nowValue = nowValue;
    node.nowWeight = nowWeight;
    node.level = level;
    node.answer = answerTemp;
    prQueue.push(node);
}

/*求价值上界（从根节点的价值到当前结点的价值再加上剩余价值）函数，必须先对物品的单位价值从大到小排序*/
double Package::bound(int tempLevel)
{
    double leftPackageWeight = packageWeight - nowWeight;
    double priority = nowValue;
    while(tempLevel <= n && weight[tempLevel] <= leftPackageWeight)
    {
        leftPackageWeight -= weight[tempLevel];
        priority += value[tempLevel];
        tempLevel++;
    }
    if(tempLevel <= n)
        priority += (value[tempLevel]*0.1)/(weight[tempLevel]*0.1)*leftPackageWeight;
    return priority;
}

int main()
{
    Package package = Package();
    package.getMaxValue();
    system("pause");
    return 0;
}
/*
请输入有多少个物品:
5
请输入背包的容量:
10
请输入各个物品的重量:
2 3.14 1.98 5 3
请输入各个物品的价值:
40 50 100 95 30
背包可容纳的最优值为: 235
最优解为:
weight = 1.98 value = 100
weight = 2 value = 40
weight = 5 value = 95
*/

-End-