算法分析与设计课程复习之回溯法

一、基本思想

1.解空间

设问题的解向量为X=(x1,x2,…,xn) ，xi的取值范围为有穷集Si 。把xi的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解。

2.状态空间树

问题解空间的树形式表示

• 活结点: 如果已生成一个结点而它的儿子结点还没有全部生成，则这个结点叫做活结点；当前正在生成其儿子结点的活结点叫E-结点(正在扩展的结点)。
• 死结点:不再进一步扩展或者其儿子结点已经全部生成的生成结点是死结点。

二、定义

回溯法（backtracking）是一种系统地搜索问题解的方法。为实现回溯，首先需要定义一个解空间（solution space），然后以易于搜索的方式组织解空间，最后用==深度优先（DFS）==的方法搜索解空间，获得问题的解。

三、回溯法的步骤

（1）定义一个解空间，它包含问题的解
（2）用易于搜索的方式组织解空间
（3）深度优先搜索解空间，获得问题的解。

四、剪枝

为了使搜索更加有效，我们常常在搜索过程中加一些判断以决定搜索是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约束的子树；其二是用限界函数剪去不能得到最优解的子树。这两种函数统称为剪枝函数。

五、经典问题

1.着色问题

给出一个无向图G=(V,E)，需要用三种颜色之一为v中的每个顶点着色，三种颜色分别为1,2和3，使得没有两个邻接的顶点有同样的颜色。

#include <iostream>
#include <algorithm>
using namespace std;
const int N =1e2+10;
int n,m;//顶点数，可用颜色数
int st[N];//判断颜色是否使用过
int sum;//可行方案总数
int g[N][N];//图
//判断某个点的邻接点是否符合条件
bool JudgeColor(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(g[x][i]&&st[i]==st[x])//存在邻接点且邻接点颜色相同，不满足要求
        {
            return false;
            break;
        }
    }
    return true;
}
void dfs(int x)
{
    if(x>n)//当判断完所有的点后
    {
        sum++;
        return;
    }
    else
    {
        for(int i=1;i<=m;i++)//对颜色进行枚举
        {
            st[x]=i;//x的颜色为i
            if(JudgeColor(x))//x满足条件,相当于剪枝
            {
                dfs(x+1);//对下一个点进行判断
            }
            st[x]=0;//回溯
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>g[i][j];
        }
    }
    dfs(1);
    cout<<sum<<endl;
    return 0;
}

2.n-皇后问题

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n，请你输出所有的满足条件的棋子摆法。

//’Q'表示皇后
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
char g[N][N];//图
bool col[N];//判断列是否有皇后
bool dg[N];//判断对角线是否有皇后
bool udg[N];//判断反对角线是否有皇后
void dfs(int u)
{
    if(u==n)//当放下所有的皇后
    {
        for(int i=0;i<n;i++)cout<<g[i]<<endl;
        cout<<endl;
        return;
    }
    for(int i=0;i<n;i++)//对行搜索
    {
        if(!col[i]&&!dg[u-i+n]&&!udg[u+i])//此处根据直线的截距确定直线，（x，y）相当于（u，i），dg[u-i+n]中+n是保证结果是正的
        {
            g[u][i]='Q';
            col[i]=dg[u-i+n]=udg[u+i]=true;
            dfs(u+1);
            col[i]=dg[u-i+n]=udg[u+i]=false;//回溯
            g[u][i]='.';
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]='.';//初始化
        }
    }
    dfs(0);
    return 0;
}

3.求不等式的所有整数解

有关于变元x1,x2,x3…xn的不等式: k1x1+ k2x2+ k3x3+ … + knxn<= y. 其中ki, y都是正整数，求所有的非负整数解。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e2+10;
int n,y,sum;
int ans[N];
int a[N];
void dfs(int u)
{
    if(u == n)//当判断完所有的点后
    {
        for(int i=0;i<n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
        return;
    }
    int l=y/a[u];//确定u系数的最大值
    for(int i=0;i<=l;i++)
    {
        int t = i*a[u];
        if(sum+t<=y)//剪枝
        {
            sum += t;
            ans[u]=i;//确定u的系数
            dfs(u+1);//判断下一个数
            sum -= t;//回溯
        }
        else break;
    }
}
int main(){
    cin >> n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin >> y;
    dfs(0);
    return 0;
}

4.排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int path[N];//存储使用过的数字
bool cnt[N];//判断数字是否使用过
void dfs(int u)
{
    if(u==n)//当所有的数字判断完
    {
        for(int i=0;i<n;i++)
            cout<<path[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!cnt[i])//如果数字没有使用过
        {
            path[u]=i;//保存该数字
            cnt[i]=true;
            dfs(u+1);//判断下一个数字
            cnt[i]=false;//回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

5.子集合数问题

给定一个正整数集合X={x1,x2,…，xn}和一个正整数y，设计回溯算法，求集合X的一个子集Y，使得Y中元素之和等于y

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e2+10;
int n,y,sum;
int X[N],Y[N];
void dfs(int u)
{
    if(u==n)//当所有的点判断完
    {
        if(sum==y)//满足条件
        {
            for(int i=0;i<n;i++)
            {
                if(Y[i]!=0)
                {
                    cout<<Y[i]<<" ";
                }
            }
            cout<<endl;
        }
    }
    else
    {
        sum+=X[u];
        Y[u]= X[u];
        dfs(u+1);//当含u时
        sum-=X[u];//回溯
        Y[u]=0;//回溯
        dfs(u+1);//当不含u时
    }
}
int main(){
    cin >> n>>y;
    for(int i=0;i<n;i++)
        cin>>X[i];
    dfs(0);
    return 0;
}

6.哈密尔顿回路（货郎担问题）

哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e2+10;
int n;
int g[N][N];//图
int path[N];//存储路径
bool visited[N];//判断点是否访问过
void dfs(int u)
{
    if(u==n)
    {
        if(g[u][0]!=0)
        {
            cout<<"存在哈密顿回路: ";
            for(int i=0;i<n;i++)
            {
                cout<<path[i]<<" ";
            }
            cout<<endl;
        }
        else
        {
            cout<<"不存在哈密顿回路"<<endl;
        }
    }
    else
    {
        //遍历除起点外的每个点
        for(int i = 1;i<n;i++)
        {
            //如果该点没有访问过，并且有边相连
            if(!visited[i]&&g[u][i]!=0)
            {
                visited[i]=true;
                path[u]=i;
                dfs(u+1);
                visited[i]=false;//回溯
                path[u]=-1;//回溯
            }
        }
    }

}
int main()
{
    cin>>n;
    memset(path, -1, sizeof(path));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>g[i][j];
        }
    }
    path[0]=0;
    visited[n]=true;
    dfs(1);//起点已经确定，从1开始搜索
    return 0;
}

7.回溯法解决0-1背包问题

参考回溯法解决0-1背包问题