HNU-算法设计与分析-作业5

第五次作业【回溯算法】

在这里插入图片描述

文章目录

- 第五次作业【回溯算法】
- - <1> 算法分析题5-3 回溯法重写0-1背包
  - <2> 算法分析题5-5 旅行商问题（剪枝）
  - <3> 算法实现题5-2 最小长度电路板排列问题
  - <4> 算法实现题5-7 n色方柱问题
  - <5> 算法实现题5-13 任务分配问题

<1> 算法分析题5-3 回溯法重写0-1背包

▲问题重述

一共有N件物品，第i（i从0开始）件物品的重量为weight[i]，价值为value[i]。在总重量不超过背包承载上限maxw的情况下，求能够装入背包的最大价值是多少？并要求输出选取的物品编号。

（要求使用回溯法求解）

▲解题思路

使用回溯法。构造解空间树，从第0层到第n-1层，每层表示对于背包内某个物品的“取”或“不取”。第n层为答案层，在第n层进行判定结果是否是想要的（即能不能获得更优的解），若是就做出相应的处理。

这是一个万能的解空间树图，借来用用。

在这里插入图片描述

剪枝想法：

（1）如果在第n层之前，就出现了总和大于的maxw情况，那么此时已经超重了。之后无论是否取，都不可能再得到总和小于maxw的结果了。这种情况以及它的子树直接删去即可。

（2）如果在第n层之前，目前已有的价值，即使加上剩余可取的最大价值，也不能达到已经达到的bestv，那么之后即使全部取也不能达到bestv了。这种情况及它的子树直接删去即可。

剪枝代码可以删去，不影响结果，但会降低效率。

▲代码

// -*- coding:utf-8 -*-

// File    :   01背包问题（回溯）.cpp
// Time    :   2023/12/14
// Author  :   wolf

#include <iostream>
using namespace std;

int w[5000];
int v[5000];
bool flag[5000];
bool ans[5000];
int now_w = 0, now_v = 0;
int n, maxw, bestv = 0;
int rest_v;

void backtrace(int depth)
{
    if (depth == n) // 到达第n层：答案
    {
        if (now_v > bestv && now_w <= maxw) // 答案是需要打印的
        {
            bestv = now_v;
            for (int i = 0; i < n; i++)
            {
                ans[i] = flag[i];
            }
        }
        return;
    }
    if (depth < n && now_w > maxw)
        return; // 剪枝：此时背包已经过重
    if (now_v + rest_v <= bestv)
        return; // 剪枝：此时剩余价值即使全部拾取也无法达到最大价值
    rest_v -= v[depth];
    // 取这个物品
    now_v += v[depth];
    now_w += w[depth];
    flag[depth] = 1;
    backtrace(depth + 1);
    now_v -= v[depth];
    now_w -= w[depth];
    flag[depth] = 0;
    // 不取这个物品
    backtrace(depth + 1);
    rest_v += v[depth];
    return;
}

int main()
{
    cin >> maxw >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
        ans[i] = 0;
        flag[i] = 0;
        rest_v += v[i];
    }
    backtrace(0);
    for (int i = 0; i < n; i++)
    {
       if (ans[i])
            cout << i << " ";
    }
    cout << endl;
    cout << bestv << endl;
    return 0;
}

▲验证

洛谷P1048（https://www.luogu.com.cn/problem/P1048）

【验证时把输出最优解向量的for循环删去，题目要求不一样】

在这里插入图片描述

回溯法解决背包问题的O(2^{n)还是从数量级上显著不如动态规划的O(n}2)。

故在数据量很大的时候，不能通过测评，显示超时。

所以01背包问题还是得用动态规划解，本题只是练习一下回溯法。

<2> 算法分析题5-5 旅行商问题（剪枝）

▲题目重述

在这里插入图片描述

▲解答

在这里插入图片描述

▲代码

// -*- coding:utf-8 -*-

// File    :   5-5 旅行售货员问题.cpp
// Time    :   2023/12/30
// Author  :   wolf

#include <iostream>

using namespace std;
int const MAXINT = 99999;
int map[1000][1000];
int v, e, best_cost = MAXINT, now_cost = 0;
int now_order[1000]; // 储存当前排列解向量
int ans[1000];       // 储存结果排列解向量
int upbound;

void swap(int a, int b)
{
    int temp = now_order[a];
    now_order[a] = now_order[b];
    now_order[b] = temp;
};

void backtrack(int depth)
{
    if (depth == v - 1) // 到达答案层
    {
        if (map[now_order[depth]][now_order[0]] != -1) // 能跟第一个相连
        {
            now_cost += map[now_order[depth]][now_order[0]];
            if (now_cost < best_cost) // 更优，保存结果
            {
                best_cost = now_cost;
                for (int i = 0; i < v; i++)
                {
                    ans[i] = now_order[i];
                }
            }
            now_cost -= map[now_order[depth]][now_order[0]];
        }
    }
    else
    {
        for (int i = depth; i < v; i++) // 生成排列树当前向量中depth位置的节点编号（第depth个访问哪个节点）
        {
            if (map[now_order[depth - 1]][now_order[i]] != -1) // 前一节点到当前的这个节点有可达边
            {
                if (now_cost + map[now_order[depth - 1]][now_order[i]] <= upbound)
                // 剪枝：若当前步骤使得费用和就大于上界了，不必继续
                {
                    swap(i, depth);
                    now_cost += map[now_order[depth - 1]]
                                   [now_order[depth]];
                    backtrack(depth + 1);
                    now_cost -= map[now_order[depth - 1]]
                                   [now_order[depth]];
                    swap(i, depth);
                }
            }
        }
    }
    return;
}
int main()
{
    cin >> v >> e;
    for (int i = 0; i < v; i++)
        for (int j = 0; j < v; j++)
            map[i][j] = -1;
    for (int i = 0; i < e; i++)
    {
        int a, b, weight;
        cin >> a >> b >> weight;
        map[a][b] = weight;
        map[b][a] = weight;
    }
    // 剪枝预备：
    for (int i = 0; i < v; i++)
    {
        int i_out_max = 0; // 存储从i节点向外
        for (int j = 0; j < v; j++)
        {
            i_out_max = max(i_out_max, map[i][j]);
        }
        upbound += i_out_max;
    }

    // 指定从0号节点开始遍历
    // 反正最后每一个节点都需要遍历过
    for (int i = 0; i < v; i++)
        now_order[i] = i; // 初始按照递增顺序（初始顺序是无所谓的，只要保证都能遍历一遍就可以）
    backtrack(1);         // 0号节点已固定，搜索从1号节点开始的全排列
    cout << best_cost << endl;
    return 0;
}

▲验证

<3> 算法实现题5-2 最小长度电路板排列问题

▲问题重述

在这里插入图片描述

▲解题思路

排列树解决问题。创建以下函数/类

Board 类:
- class Board 定义了一个名为 Board 的类，用于处理电路板排列问题。
- 私有成员变量包括 n（电路板数）、m（连接块数）、x（当前解的数组）、bestx（当前最优解的数组）、bestd（当前最优密度）、low（辅助数组，存储连接块的最小高度）、high（辅助数组，存储连接块的最大高度）、B（连接块数组）。
len 函数:
- int len(int ii) 用于计算排列中的某一部分的长度，即连接块之间的最大高度差。
- 该函数首先将 low 和 high 数组初始化为合适的值，然后根据当前排列计算连接块的最小和最大高度，最后计算最大高度差并返回。
Backtrack 函数:
- void Backtrack(int i) 是一个递归函数，用于在排列树上进行回溯搜索，寻找最优解。
- 当达到排列树的终点（i == n）时，计算当前排列的长度，并更新最优解。
- 否则，对于当前位置 i，尝试选择不同的电路板进行交换，然后继续递归搜索。
ArrangeBoards 函数:
- int ArrangeBoards(int **B, int n, int m, int *bestx) 是主要的调用函数。
- 在该函数中，创建一个 Board 类的实例 X，并通过初始化设置其成员变量。
- 利用回溯算法调用 Backtrack(1) 来找到最优解。
- 返回最优解的密度。
main 函数:
- main 函数读取输入，调用 ArrangeBoards 函数来解决问题，并输出结果。
- 动态分配二维数组 B 以存储连接块信息。
- 读取输入的电路板连接信息。
- 创建数组 bestx 用于存储最优解。
- 输出最优解的密度和排列。

▲代码

// 电路板排列问题
#include <bits/stdc++.h>
using namespace std;
class Board
{
    friend int ArrangeBoards(int **, int, int, int *);

private:
    void Backtrack(int i);
    int len(int ii);
    int n,      // 电路板数
        m,      // 连接块数
        *x,     // 当前解
        *bestx, // 当前最优解
        bestd,  // 当前最优密度
        *low,   //
        *high,  //
        **B;    // 连接块数组
};
int Board::len(int ii)
{
    for (int i = 0; i <= m; i++)
    {
        high[i] = 0;
        low[i] = n + 1;
    }
    for (int i = 1; i <= ii; i++)
    {
        for (int k = 1; k <= m; k++)
        {
            if (B[x[i]][k])
            {
                if (i < low[k])
                    low[k] = i;
                if (i > high[k])
                    high[k] = i;
            }
        }
    }
    int tmp = 0;
    for (int k = 1; k <= m; k++)
    {
        if (low[k] <= n && high[k] > 0 && tmp < high[k] - low[k])
            tmp = high[k] - low[k];
    }
    return tmp;
}
void Board::Backtrack(int i) // 回溯搜索排列树
{
    if (i == n) // 到达排列树终点
    {
        int tmp = len(i);
        if (tmp < bestd)
        {
            bestd = tmp;
            for (int j = 1; j <= n; j++)
                bestx[j] = x[j];
        }
    }
    else
    {
        for (int j = i; j <= n; j++) // 选择x[j]为下一块电路板
        {
            swap(x[i], x[j]);
            int ld = len(i);
            if (ld < bestd)
                Backtrack(i + 1);
            swap(x[i], x[j]);
        }
    }
}
int ArrangeBoards(int **B, int n, int m, int *bestx)
{
    Board X;
    // 初始化X
    X.x = new int[n + 1];
    X.low = new int[m + 1];
    X.high = new int[m + 1];
    X.B = B;
    X.n = n;
    X.m = m;
    X.bestx = bestx;
    X.bestd = n + 1;
    // 初始化total和now
    for (int i = 1; i <= n; i++)
    {
        X.x[i] = i;
    }
    X.Backtrack(1);
    delete[] X.x;
    delete[] X.low;
    delete[] X.high;
    return X.bestd;
}
int main()
{
    int n, m;
    cin >> n >> m;
    int **B = new int *[n + 1];
    for (int i = 0; i <= n; i++)
        B[i] = new int[m + 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> B[i][j];
    int *bestx = new int[n + 1];
    for (int i = 1; i <= n; i++)
        bestx[i] = 0;
    int ans = ArrangeBoards(B, n, m, bestx);
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
        cout << bestx[i] << " ";
    cout << endl;
    return 0;
}

▲验证

测试案例

测试结果：

在这里插入图片描述

<4> 算法实现题5-7 n色方柱问题

▲问题重述

设有 n 个立方体，每个立方体的每一面用红、黄、蓝、绿等 n 种颜色之一染色。要把这n 个立方体叠成一个方形柱体，使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。试设计一个回溯算法，计算出 n 个立方体的一种满足要求的叠置方案。

对于给定的 n 个立方体以及每个立方体各面的颜色，计算出 n 个立方体的一种叠置方案，使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。

数据输入：

第一行有 1 个正整数 n，0< n< 27，表示给定的立方体个数和颜色数均为 n。第 2 行是 n 个大写英文字母组成的字符串。该字符串的第 k(0≤ k< n) 个字符代表第 k 种颜色。接下来的 n 行中，每行有 6 个数，表示立方体各面的颜色。立方体各面的编号如下图所示。

在这里插入图片描述

图中 F 表示前面，B 表示背面，L 表示左面，R 表示右面，T 表示顶面，D 表示底面。相应地，2 表示前面，3 表示背面，0 表示左面，1 表示右面，5 表示顶面，4 表示底面。
例如，在示例输出文件中，第3行的6个数0 2 1 3 0 0分别表示第1个立方体的左面的颜色为R, 右面的颜色为B, 前面的颜色为G, 背面的颜色为Y, 底面的颜色为R, 顶面的颜色为 R。

案例：

input
4
RGBY
0 2 1 3 0 0 
3 0 2 1 0 1
2 1 0 2 1 3
1 3 3 0 2 2 

output
RBGYRR
YRBGRG
BGRBGY
GYYRBB

▲解题思路

在下面的代码中使用注释讲解。使用回溯法的思路套用回溯法的模板，但有改动。

本题比较晦涩难懂，在理解上需要花很多时间。

关于代码部分的映射方式

在这里插入图片描述

▲代码

// -*- coding:utf-8 -*-

// File    :   5-7 n色方柱问题.cpp
// Time    :   2023/12/27
// Author  :   wolf

#include <iostream>

using namespace std;
char color[28]; // 用来储存输入的数字对应的颜色（只在输出的时候转换为字符，在做题时使用数字存储）
int box[28][6]; // box[i][j]用来储存第i个立方体各个面（即第j面）的颜色
int n;
int count = 1; //  标记这是第几个输出的；可能结果
const int place[24][6] = {
    // 转动立方体的映射函数，使用box[depth+1][j]=origin[place[method][j]]来获取第method种方法下下一层的摆放方式
    // place[i][j]为第i种转换方法下该立方体该层的第j面应该变换为place[i][j]
    {0, 1, 2, 3, 4, 5},
    {4, 5, 2, 3, 1, 0},
    {1, 0, 2, 3, 5, 4},
    {5, 4, 2, 3, 0, 1}, // 2为底面，3为顶面

    {0, 1, 3, 2, 4, 5},
    {4, 5, 3, 2, 1, 0},
    {1, 0, 3, 2, 5, 4},
    {5, 4, 3, 2, 0, 1}, // 3为底面，2为顶面

    {3, 2, 0, 1, 4, 5},
    {4, 5, 0, 1, 2, 3},
    {2, 3, 0, 1, 5, 4},
    {5, 4, 0, 1, 3, 2}, //  0为底面，1为顶面

    {3, 2, 1, 0, 4, 5},
    {4, 5, 1, 0, 2, 3},
    {2, 3, 1, 0, 5, 4},
    {5, 4, 1, 0, 3, 2}, //  1为底面，0为顶面

    {1, 0, 4, 5, 3, 2},
    {3, 2, 4, 5, 0, 1},
    {0, 1, 4, 5, 2, 3},
    {2, 3, 4, 5, 1, 0}, //  4为底面，5为顶面

    {1, 0, 5, 4, 3, 2},
    {3, 2, 5, 4, 0, 1},
    {0, 1, 5, 4, 2, 3},
    {2, 3, 5, 4, 1, 0}, //  5为底面，4为顶面
};

void backtrack(int depth)
{
    // cout << "depth=" << depth << endl;
    if (depth == n - 1) // 到达答案层
    {
        cout << "Possible Solution " << count << " : " << endl;
        count++;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                cout << color[box[i][j]] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    else
    {
        int process = depth + 1;
        int origin[6];
        // 【使用origin[]数组先保存原始情况，可以省去整体恢复原状的步骤，24次for循环每次都是新的开始】
        for (int i = 0; i < 6; i++)      // 保存待处理层初始存放的颜色
            origin[i] = box[process][i]; // origin[i]表示该层初始第i个面存放的颜色
        // cout << "origin=" << endl;
        // for (int i = 0; i < 6; i++)
        //     cout << origin[i] << " ";
        // cout << endl;
        for (int i = 0; i < 24; i++) // 列举子集树，每个立方体有24种放法,第i种方法
        {
            // cout << "method = " << i << endl;
            for (int j = 0; j < 6; j++) // 按照该种方案的映射，把处理的该层立方体先摆好
            {
                box[process][j] = origin[place[i][j]];
            }
            // 接下来看这种摆法是否可行
            int flag = 1; // 初始标记，表示可行
            // 表示遍历某个侧面时，是否出现重复颜色，used_i[j]标记第i个侧面第j号颜色是否被用过，初始清零
            int used_0[n];
            int used_1[n];
            int used_2[n];
            int used_3[n];
            for (int i = 0; i < n; i++) //
            {
                used_0[i] = 0;
                used_1[i] = 0;
                used_2[i] = 0;
                used_3[i] = 0;
            }
            for (int i = 0; i <= process; i++) // 遍历到现在所有已经放好的立方体，查看每个侧面是否有重复的颜色
            {
                used_0[box[i][0]]++;
                used_1[box[i][1]]++;
                used_2[box[i][2]]++;
                used_3[box[i][3]]++;
                if (used_0[box[i][0]] > 1 || used_1[box[i][1]] > 1 || used_2[box[i][2]] > 1 || used_3[box[i][3]] > 1)
                // 题目要求是最后摆好的整个立方体条的每个侧面都要有n种颜色
                // 但因为n个立方体摆出的，该侧面条有n种颜色，所以相当于每个立方体在该侧面的颜色都不一样
                // 即某个侧面条上每种颜色只能使用一次，这里转换了题目的条件
                // 某个侧面条上某个颜色用了不止一次，不符合条件，该方案以及该方案的子树剪掉
                {
                    flag = 0;
                    // cout << used_0[box[i][0]] << " " << used_1[box[i][1]] << " " << used_2[box[i][2]] << " " << used_3[box[i][3]] << endl;
                    break;
                }
            }
            if (flag == 1) // 目前所有已经摆好的立方体的每个侧面都没有重复的颜色，符合要求，可以继续放下一个立方体
                backtrack(depth + 1);
        }
    }
    return;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> color[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> box[i][j];
        }
    }
    cout << endl
         << "ans = " << endl;
    backtrack(-1);
    return 0;
}

▲验证

未找到在线测评，使用题目给出的案例

input
4
RGBY
0 2 1 3 0 0 
3 0 2 1 0 1
2 1 0 2 1 3
1 3 3 0 2 2

输出结果如下：

ans = 
Possible Solution 1 : 
R B G Y R R 
Y R B G R G 
B G R B G Y 
G Y Y R B B

Possible Solution 2 :
B R G Y R R
R Y B G G R
G B R B Y G
Y G Y R B B

Possible Solution 3 :
R B Y G R R
Y R G B R G
B G B R G Y
G Y R Y B B

Possible Solution 4 :
B R Y G R R
R Y G B G R
G B B R Y G
Y G R Y B B

Possible Solution 5 :
Y G R B R R
G B Y R R G
B R B G G Y
R Y G Y B B

Possible Solution 6 :
G Y R B R R
B G Y R G R
R B B G Y G
Y R G Y B B

Possible Solution 7 :
Y G B R R R
G B R Y R G
B R G B G Y
R Y Y G B B 

Possible Solution 8 :
G Y B R R R
B G R Y G R
R B G B Y G
Y R Y G B B

可见答案不唯一（显然可能），题目给定的答案在其中之一。

我们这种算法的时间复杂度O(n*24^n)，数据量大了之后可能会很慢。

<5> 算法实现题5-13 任务分配问题

▲问题重述

问题描述: 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为 cij。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。

算法设计：设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

数据输入：第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。

样例：

input
3
10 2 3
2 3 4
3 4 5

output
9

▲解题思路

假设人不动，将工作分发给不同人。

解向量x[i]为第i个人被分配第x[i]个工作，解空间树为排列树。从第0层开始，第0层就有n个节点（可以认为第-1层有一个节点），答案层在第n层（第n-1层将自己与自己交换，实际上不影响最终结果）。在第n层比较当前总费用是不是比目前保存的方案总费用更少，如果是就将这个更小的存下来，否则不做处理。

遍历完整个排列树后得到最优解。

▲代码

// -*- coding:utf-8 -*-

// File    :   5-13.cpp
// Time    :   2023/12/25
// Author  :   wolf

#include <iostream>

using namespace std;
const int MAXNUM = 9999999;
int c[21][21];
int x[21];
int nowcost = 0, mincost = MAXNUM, n;

void swap(int a, int b)
{
    int temp = x[a];
    x[a] = x[b];
    x[b] = temp;
}

void backtrack(int depth)
{
    if (depth == n) // 答案层
    {
        mincost = min(mincost, nowcost);
        // cout << nowcost << endl;
        // 不需要输出解向量，故不用保存解向量
    }
    else
    {
        for (int i = depth; i < n; i++)
        {
            // depth当前人，i为待分发物品序号，人不动，发物品
            nowcost += c[x[i]][depth];
            swap(i, depth);
            backtrack(depth + 1);
            swap(i, depth);
            nowcost -= c[x[i]][depth];
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> c[i][j];
        }
    }
    for (int i = 0; i < n; i++)
        x[i] = i;
    backtrack(0);
    cout << mincost << endl;

    return 0;
}

▲验证

测试数据可通过。