2、回溯

定义

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试中寻找问题的解，当发现不能满足条件时，就“回溯”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法” 的美称。

步骤

（1）针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解；
（2）确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
基本思想：从一条路往前走，能进则进，不能进则退回来，回一条路再走。

实现

回溯的实现方法一般有两种：递归和递推（迭代）
（1）递归
思路简单，设计容易，但效率较低：

//针对N叉树的递归回溯方法  
void backtrack (int t)  
{  
    if (t>n) output(x); //叶子节点，输出结果，x是可行解  
    else  
       for i = 1 to k//当前节点的所有子节点  
        {  
            x[t]=value(i); //每个子节点的值赋值给x  
            //满足约束条件和限界条件  
          if (constraint(t)&&bound(t))   
                backtrack(t+1);  //递归下一层  
        }  
}  

（2）递推
算法设计较复杂，但效率较高：

//针对N叉树的迭代回溯方法  
void iterativeBacktrack ()  
{  
    int t=1;  
    while (t>0) {  
        if(ExistSubNode(t)) //当前节点的存在子节点  
        {  
            for i = 1 to k  //遍历当前节点的所有子节点  
            {  
                x[t]=value(i);//每个子节点的值赋值给x  
                if (constraint(t)&&bound(t))//满足约束条件和限界条件   
                {  
                    //solution表示在节点t处得到了一个解  
                    if (solution(t)) output(x);//得到问题的一个可行解，输出  
                    else t++;//没有得到解，继续向下搜索  
                }  
            }  
        }  
        else //不存在子节点，返回上一层  
        {  
            t--;  
        }  
    }  
}  

识别回溯

一般回溯的问题有三种：

• 有没有解
• 求所有解（个数或具体信息）
• 求最优解

而对于每种问题有不同的模板
第一种：有没有解

bool solve(Node n){
    if n is a leaf node{
        if the leaf is a goal node , return true;
        else return false;
    }
    else{
        for each child c of n{
            if solve(c) succeeds,return true;
        }
        return false;
    }
}

第二种：求全部解

void solve(Node n){
    if n is a leaf node{
        if the leaf is a goal node,count++,return;
    else return;
    }
    else{
        for each child c of n{
            solve(c);
        }
    }
}

第三种：求最优解

void solve(Node n){
    if n is a leaf node{
        if the leaf is a goal node,update best result,return;
        else return;
    }
    else{
        for each child c of n{
            solve(c);
        }
    }
}

实例一：八皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后（棋子），使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
第一种：有没有解

#include <iostream>
using namespace std;

class ChessBoard{
public:
    ChessBoard();
    ChessBoard(int);
    void findSolution();
private:
    const bool available;
    const int squares,norm;//棋盘边长、设定一个右斜线相加的常数
    bool *column,*leftDiagonal,*rightDiagonal;//定义列、左斜线与右斜线
    int *positionInRow,howMany;//定义行及方法的数量
    char m[10][10];//记录棋盘格
    void putQueen(int);//放置皇后
    void printBoard();//打印输出
    void initBoard();//初始化棋盘
    void Delete();//释放内存
};

ChessBoard::ChessBoard():available(true),squares(8),norm(squares-1){
    initBoard();
}

ChessBoard::ChessBoard(int n):available(true),squares(n),norm(squares-1){
    initBoard()
}

void ChessBoard::initBoard(){
    register int i;//将i寄存，使计算更快
    column = new int[squares];
    positionInRow = new int[squares];
    leftDiagonal = new bool[squares*2-1];//左斜线的数目
    rightDiagonal = new bool[squares*2-1];//右斜线的数目
    for(int i = 0;i < squares;i ++)
        positionInRow[i] = -1;//存储列数
    for(int i = 0;i < squares;i ++)
        column[i] = available;
    for (i = 0; i < squares * 2 - 1; i++)
        leftDiagonal[i] = rightDiagonal[i] = available;
    howMany = 0;
}
void ChessBoard::printBoard() {
    howMany++;//
    cout << howMany << " way is:" << endl;
    //为棋盘格赋值为1
    for (int i = 0;i != squares;i++) {
        for (int j = 0;j != squares;j++)
            m[i][j] = '1';
    }
    //将皇后的位置在棋盘格上用'*'标志出来
    for (int row = 0;row != squares;row++)
        m[row][positionInRow[row]] = '*';
    //打印棋盘格
    for (int i = 0;i != squares;i++) {
        for (int j = 0;j != squares;j++)
            cout << m[i][j];
        cout << endl;
    }
    cout << endl;
}
void ChessBoard::putQueen(int row) {
    for (int col = 0; col < squares; col++) {
        if (column[col] == available &&
            leftDiagonal[row + col] == available &&
            rightDiagonal[row - col + norm] == available)
        {
            positionInRow[row] = col;
            column[col] = !available;
            leftDiagonal[row + col] = !available;
            rightDiagonal[row - col + norm] = !available;
            if (row < squares - 1)
                putQueen(row + 1);
            else printBoard();
            column[col] = available;
            leftDiagonal[row + col] = available;
            rightDiagonal[row - col + norm] = available;
        }
    }
}
void ChessBoard::Delete() {
    delete[]column;
    delete[]positionInRow;
    delete[]leftDiagonal;
    delete[]rightDiagonal;
}
void ChessBoard::findSolutions() {
    putQueen(0);
    cout << howMany << " solutions found.\n";
    Delete();
}
int main() {
    ChessBoard board(7);
    board.findSolutions();
    while (true)
    {

    }
    return 0;
}

实例二：背包问题

给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

#include <stdio.h>

#define N 3 //物品的数量
#define C 16;//背包的容量

int w[N]={10,8,5};//每个物品的重量
int v[N]={5,4,1};//每个物品的价值
int x[N]={0,0,0};//代表是否放入背包

int curW=0;//当前背包中物品总重量
int curV=0;//当前背包中物品总价值

int BestV=0;//当前的最大价值
int BestX[N];//最优路径选择

void backTrack(int t){
    //叶子节点，一条路径一条路径的遍历
    if(t>N-1){
        //找到一个更优的解
        if(curV>BestV){
            BestV=CurV;
            for(int i=0;i<N;++i) BestX[i]=x[i];    
        }
    }
    else{
        //主要在此处实现回溯，递归到下一个节点时，价值和重量加；回溯之后，价值和重量减。
        if((CurV+w[t])<=C){
            CurW+=w[t];
            CurV+=v[t];
            backTrack(t+1);
            CurW-=w[t];
            CurV-=v[t];
        }
    } 
}

//主函数
int main(int argc,char* argv[]){
    backTrack(0);
    cout << "最优解：" << BestV << endl;
    for(int i=0;i<N;i++){
        cout << "路径：" << BestX[i]);
    }
    return 0;
}