算法笔记之回溯法（2）

2021-12-21 03:09:03

着色问题

问题分析

假设地图共有7个区域，分别是A/B/C/D/E/F/G，对上面顺序进行编号，每个区域用一个结点表示，相邻的区域有连线，那么地图就转化成一个无向连接图。

算法设计

  1. 定义问题的解空间。图的m着色问题解空间形式为n元组{x1,x2,...,xi,...,xn}，每个分量取值为1,2,3,...,m，即问题的解是一个n元向量。由此可得，问题的解空间为{x1,x2,...,xi,...,xn}，其中显约束为xi=1,2,...,m。
  2. 确定解空间的组织结构：一颗满m叉树，树的深度为n。

  3. 搜索解空间

    • 约束条件：假设当前扩展结点位于解空间树的第t层，那么从第1到第t-1层的结点情况都已经确定，接下来是按照扩展结点的第一个分支进行扩展，此时需要判断是否将第t个结点着色情况。第t个结点的色号要与前t-1个结点中与其有边相连的结点颜色不同，如果有颜色相同的，则第t个结点不能用这个色号，换下一个色号尝试。
    • 限界条件：无。
    • 搜索过程：扩展结点沿着第一个分支扩展，判断约束条件，满足则进入深一层继续搜索；如果不满足，则扩展生成的结点被剪掉，换下一个色号尝试。如果所有色号都尝试完毕，该结点变成死结点，向上回溯到距离其最近的活结点，继续搜索。搜索到叶子结点时，找到一种着色方案，搜索过程直到全部活结点变成死结点为止。

解题过程

地图7个区域，3种颜色。

  1. 开始搜索第1层（t=1）。扩展A结点第一个分支，首先判断是否满足约束条件，因为之前还未着色任何结点，所以满足约束条件，扩展该分支，令1号结点着1号色，即x[1]=1，生成B。
  2. 拓展B结点（t=2）。扩展第一个分支x[2]=1，首先判断2号结点是否和前面已经确定色号的结点（1号）有边相连且色号相同，不满足约束条件，剪掉该分支，然后沿着x[2]=2扩展，2号结点和前面已经确定色号的结点（1号）有边相连，但色号不同，满足约束条件，扩展该分支，令x[2]=2。
  3. 扩展C结点（t=3）。扩展第一个分支x[3]=1，首先判断3号结点是否和前面已经确定色号的结点（1、2号）有边相连且色号相同，不满足约束条件，剪掉该分支；同理剪掉x[3]=2分支。然后沿着x[3]=3扩展，3号结点和前面已经确定色号的结点（1、2号）有边相连，但色号不同，满足约束条件，扩展该分支，令x[3]=3。生成D。
  4. 扩展D结点（t=4）。扩展第一个分支x[4]=1，首先判断4号结点是否和前面已经确定色号的结点（1、2、3号）有边相连且色号相同，不满足约束条件（4余1相连），剪掉该分支；然后令x[4]=2，符合条件，生成E。
  5. 扩展E结点（t=5）。扩展第一个分支x[5]=1，首先判断4号结点是否和前面已经确定色号的结点（1、2、3号）有边相连且色号相同，确定5与2、3、4相连但色号不同，满足约束条件，扩展该分支，生成F。
  6. 扩展F结点（t=6）。扩展第一个分支x[6]=1，同理不满足，剪掉分支；然后沿着x[6]=2扩展，6与5号有边相连但色号不同，故满足约束条件，扩展该分支，令x[6]=2，生成G。
  7. 扩展G结点（t=7）。扩展第一个分支x[7]=1，剪掉x[7]=1和x[7]=2的分支，然后令x[7]=3，符合要求，生成H。
  8. 扩展H结点（t=8）。t>n，找到一个可行解，输出该可行解{1,2,3,2,1,2,3}，回溯到最近的活结点G。
  9. 重新扩展G结点（t=7）。G已经考察完毕，成为死结点，回溯到最近的活结点F。
  10. 继续搜索，又找到第二种着色方案，输出可行解{1,3,2,3,1,3,2}。
  11. 继续搜索，又找到4个可行解。

代码实现

//约束条件
bool isRight(int t)
{
    for (int j = 1; j < t; j++)
    {
        if (map[t][j])
        {
            if (x[j] == x[t])
                return false;
        }
    }
    return true;
}

//回溯方法函数
void Backtrack(int t)
{
    if (t > n)
    {
        sum++;
        cout << "第" << sum << "种方案：";
        for (int i = 1; i <= n; i++)//输出该着色方案
        {
            cout << x[i] << " ";
        }
        cout << endl;
    }
    else {
        for (int i = 1; i <= m; i++)
        {
            x[t] = i;
            if (isRight(t))
                Backtrack(t + 1);
        }
    }
}

算法复杂度分析

  1. 时间复杂度：O(nmn)。
  2. 空间复杂度：O(n)。

n皇后问题

问题介绍

在n×n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋规则，皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。现在在n*n的棋盘上放置n个皇后，使其不受攻击。

问题分析

求解策略：
以行为主导：

  • 在第1行第1列放置第一个皇后。
  • 在第2行放置第2个皇后。第2个皇后的位置不能和前面的皇后同列、同斜线，不用再判断同行了，因为每行我们本来就只放一个。
  • 在第3行放置第3个皇后。第3个皇后的位置不能和前面的皇后同列、同斜线。
  • ……
  • 在第t行放置第t个皇后。第t个皇后的位置不能和前面的皇后同列、同斜线。
  • ……
  • 在第n行放置第n个皇后。第n个皇后的位置不能和前面的皇后同列、同斜线。

算法设计

（1）定义问题的解空间。n皇后问题解的形式为n元组：{x1,x2,...,xi,...,xn}，分量xi表示第i个皇后放置在第i行第xi列，xi取值为1,2,3,...,n。显约束为不同行。

（2）解空间的组织结构：一颗m(m=n)叉树，树深度为n。

（3）搜索解空间。
约束条件：在第t行放置第t个皇后时，第t个皇后的位置不能和前t-1个皇后同列、同斜线。第i个皇后和第j个皇后不同列，即xi!=xj。

限界条件：不需要设置。

搜索过程：

从根开始，以DFS的方式进行搜索。根节点是活结点，并且是当前的扩展结点。在搜索过程中，当前的扩展结点沿纵深方向移向一个新结点，判断该新结点是否满足隐约束。如果满足，则该新结点成为活结点，并且成为当前的扩展结点，继续深一层的搜索；如果不满足，则换到该新结点的兄弟结点继续搜索；如果新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行。搜索过程直到找到问题的根结点变成死结点为止。

代码实现

bool isPlace(int t)
{
    bool place = true;
    for (int j = 1; j < t; j++)
    {
        if (x[t] == x[j] || t - j == fabs(x[t] - x[j]))//判断列、对角线是否冲突
        {
            place = false;
            break;
        }
    }
    return place;
}

void backtrack(int t)
{
    if (t > n)
    {
        countn++;
        for (int i = 1; i <= n; i++)
        {
            cout << x[i] << " ";
        }
        cout << endl;
        cout << "---------" << endl;
    }
    else
    {//分别判断n个分支，特别注意i不要定义为全局变量，否则递归调用有问题
        for (int i = 1; i <= n; i++)
        {
            x[t] = i;
            if (isPlace(t))
                backtrack(t + 1);
            //上面说的是不冲突就进行下一行搜索
        }
    }
}

算法复杂度分析

  1. 时间复杂度：O(nn+1）。
  2. 空间复杂度：O(n)。

最优加工顺序

问题描述

现在有3个机器零件{J1,J2,J3}，在第一台机器上的加工时间分别为2、5、4，在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？

问题分析

我们通过分析可以发现，第一台机器可以连续加工，而第二台机器开始加工的时间是当前第一台机器的下线时间和第二台机器下线时间的最大值。
实际上就是找到n个机器零件的一个排列，使总的加工时间最短。

算法设计

  1. 定义问题的解空间。解的形式为n元组：{x1,x2,...,xi,...,xn}，分量xi表示第i个加工的零件号，n个零件组成的集合为S={1,2,...,n}，xi取值为S-{x1,x2,...,xi-1}。
  2. 解空间的组织形式为一颗排列数，深度为n。

  3. 搜索解空间。

    • 约束条件：无约束条件。
    • 限界条件：用f2表示当前已完成的零件在第二台机器加工结束所用的时间，用bestf表示当前找到的最优加工方案的完成时间。显然，继续向深处搜索时，f2不会减少，只会增加。因此，当f2≥bestf时，没有继续向深处搜索的必要。限界条件可以描述为：f2。f2初值为0，bestf的初值为无穷大。
  4. 搜索过程。扩展结点沿着某个分支扩展时需要判断限界条件，如果满足，则进入深一层继续搜索；如果不满足，则剪掉该分支。搜索到叶子结点的时候，即找到当前最优解。搜索直到全部活结变成死结点为止。

代码实现

1.数据结构

struct node
{
    //机器零件在第一台机器上的加工时间x和第二胎机器上的加工时间y
    int x,y;
}T[MAX];

2.按限界条件进行搜索求解：t表示当前扩展结点在第t层，f1表示当前第一台机器上加工的完成时间，f2表示当前第二台机器上加工的完成时间。如果t>n表示已经到达叶子结点，记录最优值和最优解，返回。否则，分别判断每个分支是否满足约束条件，若满足则进入下一层backtrack(t+1)；如果不满足则反操作复位，考察下一个分支（兄弟结点）。

void Backtrack(int t)
{
    if(t>n)
    {
        for(int i=1;i<=n;i++)
            bestx[i]=x[i];//记录最优队列
        bestf=f2;//更新最优值
        return ;
    }
    for(int i=t;i<=n;i++)
    {
        f1+=T[x[i].x;
        int temp=f2;
        f2=max(f1,f2)+T[x[i]].y;
        if(f2<bestf)//满足限界条件
        {
            swap(x[t],x[i]);//交换
            Backtrack(t+1);//继续搜索
            swap(x[t],x[i]);//复位，反操作
        }
        f1-=T[x[i]].x;//复位，反操作
        f2=temp;//复位，反操作
    }
}

算法复杂度分析

时间复杂度为O(nn!)≈O((n+1)!)，空间复杂度为O(n)。

算法优化改进

新的算法的时间复杂度为O(nlogn)，空间复杂度为O(n)。利用贝尔曼规则，代码如下：

#include<iostream>
#include<algorithm>
using namespace std ;
const int MX=10000+5 ;
int n;
struct node
{
    int id;
    int x,y;
}T[MX] ;
bool cmp(node a,node b)
{
    return min(b.x,a.y)>=min(b.y,a.x);//按照贝尔曼规则排序
}
int main()
{
    cout<<"请输入机器零件的个数 n:";
    cin>>n;
    cout<<"请依次输入每个机器零件在第一台机器上的加工时间x和第二台机器上的加工时间y:";
    for(int i=0;i<n;i++)
    {
        cin>>T[i].x>>T[i].y;
        T[i].id=i+1;
    }
    sort(T,T+n,cmp);   //排序
    int f1=0,f2=0;
    for(int i=0;i<n;i++)  //计算总时间
    {
       f1+=T[i].x;
       f2=max(f1,f2)+T[i].y;
     }
    cout<<"最优的机器零件加工顺序为:";
     for(int i=0;i<n;i++) //输出最优加工顺序
       cout<<T[i].id<<" ";
    cout<<endl;
    cout<<"最优的机器零件加工的时间为:";
    cout<<f2<<endl;
    return 0 ;
}
上一篇：《优化阵列信号处理》学习笔记（第四章）


下一篇：常用排序算法复杂度和稳定性总结