算法笔记之回溯法（2）

着色问题

问题分析

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

算法设计

1. 定义问题的解空间。图的m着色问题解空间形式为n元组{x₁,x₂,...,x_i,...,x_n}，每个分量取值为1,2,3,...,m，即问题的解是一个n元向量。由此可得，问题的解空间为{x₁,x₂,...,x_i,...,x_n}，其中显约束为x_i=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(nmⁿ)。
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元组：{x₁,x₂,...,x_i,...,x_n}，分量x_i表示第i个皇后放置在第i行第x_i列，x_i取值为1,2,3,...,n。显约束为不同行。

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

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

限界条件：不需要设置。

搜索过程：

从根开始，以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(nⁿ⁺¹）。
2. 空间复杂度：O(n)。