算法基础之分支限界法

🕗 发布于 2024-07-20 20:57 算法

本文将详细介绍分支限界法的基本原理和适用条件，并通过经典例题辅助读者理解分支限界法的思想、掌握分支限界法的使用。本文给出的例题包括：15谜问题、带时限的作业排序问题。

算法原理

分支限界法采用广度优先搜索产生状态空间树的结点，为了有效地选择下一拓展结点，以加速搜索进程，在每一活结点处计算一个函数值（限界函数），并根据这些已计算出的函数值从当前活结点表中选择一个最有利的结点作为拓展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快找出一个最优解。

根据选择下一个拓展结点的方式来组织或节点表，不同的活结点表对应不同的分支搜索方式，分为： $F I FO$ 分支限界法、 $L I FO$ 分支限界法和 $L C$ 分支限界法。

$F I FO$ 分支限界法的活结点表是先进先出队列；
$L I FO$ 分支限界法的活结点表是堆栈；
$L C$ 分支限界法的活结点表是优先权队列， $L C$ 分支限界法将选取具有最高优先级的活结点出队列，成为新的拓展结点。

15谜问题

题目描述

在一个 $4 \times 4$ 的方形棋盘上放置了 $15$ 块编了号的牌，还剩下一个空格。问题要求对于给定的一种初始排列，通过一系列的合法移动（前后左右），将给定的初始排列转换成目标排列（第一行 $1234$ ，第二行 $5678$ ，第三行第四行类推，最后是空格）。应当注意的是，并非所有可能的排列作为初始排列都能到达目标排列。编写程序对任意给定的排列，判断是否可由该排列经过一系列号牌移动到达目标排列。

输入输出

输入：初始排列（空格用 $\#$ 表示）。

输出：如果可由输入的初始排列经过一系列号牌移动到达目标排列，则输出 $TR U E$ 和状态转换过程；否则输出 $F A L SE$ 。

解题思路

由于并非所有的初始排列都能到达目标排列，故首先要做的便是判断所给初始排列能否到达目标排列。

定理：设空格所在位置为 $(i, j)$ ，空格编号为 $16$ ， $L ess (k)$ 为编号小于 $k$ 但排在 $k$ 之后的棋牌数，对于初始排列，当且仅当 $Σ L ess (k) + i + j$ 为偶数时才可到达目标排列。

使用定理可以快速判断能否由所给的初始状态到达目标状态，当不能到达时，可避免大量不必要的搜索。

如果由初始状态可到达目标状态，则采用 $L C$ 分支限界法求出状态转换过程。设代价估计函数 $c (x) = f (x) + g (x)$ ，其中， $f (x)$ 为根结点到结点 $x$ 的路径的长度， $g (x)$ 为结点 $x$ 对应排列不在其目标位置的非空白棋牌数，规定 $c (x)$ 越小，结点 $x$ 优先级越高。具体做法：

计算根结点代价并将根结点加入活结点队列（优先队列）；
从队列中取出优先级最高的结点作为当前拓展结点；
对于当前拓展结点，按“上下左右”的顺序移动空格来产生新的结点（不能往回走），对于新结点，若其代价不大于目前队列所有结点的代价的最小值，则将其加入活结点队列；
重复步骤 $2$ 和 $3$ ，直到找到一个解 $（ g (x) = 0 ）$ 或活结点队列为空。

代码实现

// 状态空间树结点
struct Node {
    // 状态
    int inf[16];
    // 空格的位置 代价 与根结点的距离
    int b, c, d;
    // 父结点
    Node *p;
};

// 代价小的优先级高
struct comp {
    bool operator()(const Node *n1, const Node *n2) {
        return n1->c > n2->c;
    }
};

// 活结点队列
priority_queue<Node *, vector<Node *>, comp> Q;
// 根结点 目标结点
Node *rt, *tar;
// 上下左右标志 空格标志
const int U = -4, B = 4, L = -1, R = 1, BLANK = 15;
// 按上下左右的顺序移动空格
const int DIR[]{U, B, L, R};

int main() {
    init();                 // 输入
    if (check(rt)) {        // 有解
        cout << "TRUE\n";
        solve();    // 求解
        show(tar);  // 输出状态变换过程
    } else cout << "FALSE";   // 无解
}

/**
 * 分支限界法求15谜移动方案
 * @return 是否存在方案
 */
int solve() {
    // 是否没有找到目标结点 当前层活结点个数  当前所有结点的代价的最小值 临时变量
    int notFd = 1, val = INT_MAX;
    // 求解
    while (!Q.empty() && notFd) {
        // 取出优先级最高的活结点
        Node *ep = Q.top();
        Q.pop();
        // 当前结点对应的状态按上下左右的顺序移动空格来拓展结点
        for (int i = 0; i < 4; ++i) {
            // 创建新结点
            Node *ch = new Node();
            ch->p = ep;
            // 如果该方向可以移动
            if (move(ep, ch, DIR[i])) {
                // 计算代价(不在目标位置的非空白棋牌数)+到根结点的距离
                ch->d = ep->d + 1;
                for (int j = ch->c = 0; j < 16; ++j)
                    ch->c += (j != ch->b && ch->inf[j] != j);
                if (ch->c == 0) {       // 到达目标状态
                    notFd = 0, tar = ch;
                    break;
                } else ch->c += ch->d;

                // 是否将拓展的结点ch加入活结点队列
                if (val >= ch->c) {
                    val = ch->c;
                    Q.push(ch);
                }
            }
        }
    }
    return !notFd;
}

/**
 * 初始化: 获取输入，根结点入队
 */
void init() {
    rt = new Node();
    rt->p = nullptr;
    string s;
    // 获取输入数据并将1~16转换为0~15
    for (int i = 0; i < 16; ++i) {
        cin >> s;
        if (s == "#")rt->inf[i] = 15, rt->b = i;
        else rt->inf[i] = stoi(s) - 1;
    }
    // 根结点加入活结点队列
    Q.push(rt);
}

/**
 * 判断当初始结点为n时是否存在解
 * @param n 结点n
 * @return 是否存在解
 */
int check(Node *n) {
    // 空格位于奇数位置则x取1，偶数则取0
    int x = (n->b / 4 + n->b % 4) & 1;
    // 统计在inf[i]后面但小于inf[i]的位置总数
    for (int i = 0; i < 16; ++i)
        for (int j = i + 1; j < 16; ++j)
            x += (n->inf[j] < n->inf[i]);
    // x为偶数，有解，否则无解
    return !(x & 1);
}

/**
 * 从状态s向dir指定的方向移动空格得到新的状态ns
 * @param s 当前状态结点
 * @param ch 新状态结点
 * @param dir 空格移动方向
 * @return 是否移动成功
 */
int move(Node *s, Node *ch, int dir) {

    int flag;   // 是否可以移动

    // 记录移动后空格位置
    ch->b = s->b + dir;

    // 判断移动是否合理
    if (s->p && ch->b == s->p->b)flag = 0;      // 防止往回走
    else if (dir == U || dir == B)
        flag = (ch->b >= 0 && ch->b < 16);
    else
        flag = (s->b / 4 == ch->b / 4);

    // 如果能移动则创建新的结点
    if (flag) {
        // 复制结点s的信息
        copy(begin(s->inf), end(s->inf), begin(ch->inf));
        // 移动空格
        ch->inf[s->b] = s->inf[ch->b];
        ch->inf[ch->b] = s->inf[s->b];
    }
    return flag;
}

/**
 * 输出状态转移过程
 * @param n 目标结点
 */
void show(Node *n) {
    if (!n)return;
    show(n->p);
    for (int i = 0; i < 16; ++i) {
        if (i == n->b)cout << "#\t";
        else cout << n->inf[i] + 1 << "\t";
        if (i % 4 == 3)cout << "\t";
    }
    cout << endl;
}

时间复杂度： $O(2^n)$ 。

空间复杂度： $O(2^n)$ 。

带时限的作业排序问题

题目描述

带时限的作业排序问题可描述为：设有 $n$ 个作业和一台处理机，每个作业所需的处理时间、要求的时限和收益可用三元组 $p_i,d_i,t_i）$ 表示， $0 \leq i < n$ ，其中，作业 $i$ 的所需时间为 $t_i$ ，如果作业 $i$ 能够在时限 $d_i$ 内完成，将可获得收益 $p_i$ ，求使得总收益最大的作业子集。

输入输出

输入：第一行输入 $n$ 的值，第二行输入 $p_i$ ，第三行输入 $d_i$ ，第四行输入 $t_i$ （作业已经按时限非减次序排列）。

输出： $x_i$ （用固定长度 $n$ 元组 $x$ 表示）。

解题思路

题目求使得总收益最大的作业子集，等价于使得损失最小的作业子集。对于结点 $x$ ，设损失的下界函数 $L (x)$ = 目前已考虑到的的作业中未选作业造成的损失， $U (x)$ = 目前未选作业造成的损失。

设 $U$ 为目前已求得的候选解的损失的估计最小值，可令 $U = min\{U(x)\}$ 。当 $L (x) > U$ 时，说明当前结点对应的候选解的损失的下界大于目前损失的最小值，可以进行剪枝，否则将结点 $x$ 加入活结点队列。当 $U (x) < U$ 时，说明当前结点对应的候选解的损失的上界小于目前损失的最小值，需要更新 $U$ 。具体做法如下（题目已说明作业已按时限非减次序排列）：

计算根结点上下界函数值并将根结点加入活结点队列（先进先出队列），根结点没有考虑任何作业，也未选择任何作业，规定根结点考虑的作业范围为 $[0, - 1]$ ；
从队列中取队头结点作为当前拓展结点，假设其考虑的作业范围为 $[0, m]$ ；
对于当前拓展结点，每将 $m$ 加 $1$ ，便产生一个新的结点，并选择作业 $m$ （已加 $1$ ）。
计算完成新结点对应的已选作业的总时间 $T$ ，记已选作业最晚截止时间为 $D$ （即 $d [m]$ ）。若 $T > D$ ，说明在规定时间内无法完成已选作业，剪枝，转至步骤 $2$ 。
计算新结点的对应的上下界函数值。若 $L (x) > U$ ，则剪枝（即不入队列），否则，将新结点加入活结点队列。若 $U (x) < U$ ，则更新 $U$ ，即令 $U = U (x)$ ；
重复步骤 $2$ 到 $5$ ，直到找到一个解或活结点队列为空。

代码实现

// 状态空间树结点
struct Node {
    // 父结点
    Node *p;
    // 选择的作业 当前已选作业所需时间总和
    int s, t;
    // ux: 上界函数，未选作业造成的损失
    // lx: 下界函数，已考虑到的的作业中未选作业造成的损失
    int ux, lx;  // 上下界
};

/**
 * N: 作业个数
 * U: 目前所有解的损失中的最小值
 */
int *p, *d, *t, N, U{0};
/**
 * rt到ans构成一个最优解
 * rt: 状态空间树根节点
 * ans: 最近使得U更新的结点
 */
Node *rt, *ans;

int main() {
    init();     // 输入数据
    solve();    // 求解
    show();     // 输出收益最大的子集
}

/**
 * 分支限界法法求解带时限的作业排序问题
 */
void solve() {
    // 活结点队列
    queue<Node *> q;

    // 状态空间树根节点入队列
    rt = new Node();
    rt->p = nullptr;
    rt->s = -1, rt->t = rt->lx = 0, rt->ux = U;
    q.push(rt);
    // 寻找最优解
    while (!q.empty()) {
        // 从队列中取出队头作为当前的拓展结点
        Node *ep = q.front();
        q.pop();
        // 生成拓展结点的子节点
        for (int i = ep->s + 1; i < N; ++i) {
            // 当前已选作业所需时间总和超过最晚时限
            if (ep->t + t[i] > d[i])continue;
            // 创建新结点
            Node *ch = new Node();
            ch->p = ep, ch->s = i, ch->t = ep->t + t[i];
            // 计算下界
            ch->lx = ep->lx;
            for (int j = ep->s + 1; j < i; ch->lx += p[j++]);
            // 如果当前结点下界比目前损失最小值大，则剪枝
            if (ch->lx > U)continue;
            // 计算上界
            ch->ux = ep->ux - p[i];
            // 如果当前结点上界比目前损失最小值小，则更新目前损失最小值为当前结点上界
            if (ch->ux < U) U = ch->ux, ans = ch;
            // 将当前结点放入活结点队列
            q.push(ch);
        }
    }
}

/**
 * 初始化N、p、d、t
 */
void init() {
    cin >> N;
    p = new int[N], d = new int[N], t = new int[N];
    // 依次输入p、d、t
    for (int i = 0; i < N; U += p[i++])cin >> p[i];
    for (int i = 0; i < N; cin >> d[i++]);
    for (int i = 0; i < N; cin >> t[i++]);
}

/**
 * 输出最优解
 */
void show() {
    int x[N];
    while (ans != rt)x[ans->s] = 1, ans = ans->p;
cout << "(";
    for (auto &xi: x)cout << (xi == 1) << ",";
cout << "\b)";
}

时间复杂度： $O(2^n)$ 。

空间复杂度： $O(2^n)$ 。

经验总结

分支限界法实际上属于穷举法，在最坏法情况下，时间复杂度是指数阶。分支限界法的效率依赖于限界函数，若限界函数设计不当，算法与穷举搜索并无太大区别。另外，分支限界法需要维护一个活结点表（队列），并且需要存储结点相关信息，如限界值，因此需要较大的存储空间，在最坏的情况下，分支限界法的空间复杂度也是指数阶。

分支限界法类似于回溯法，但一般情况下，二者的求解目标不同。回溯法的求解目标是找出满足条件的所有解，而分支限界法的求解目标是找出满足条件的一个解或某种意义下的最优解。回溯法采用深度优先搜索，使用栈来存放结点，而分支限界法有 $F I FO$ 分支限界法、 $L I FO$ 分支限界法和 $L C$ 分支限界法。

END

文章文档：公众号 字节幺零二四 回复关键字可获取本文文档。

原文地址：https://blog.csdn.net/qq_53469830/article/details/140292591

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【4~6】概率与分布
下一篇：【Flutter】 webview_flutter避坑

[CUDA] cuda kernel开发记录
包括kernel的一些使用注意事项， launch_bound, __device__, debug排查技巧
阅读更多2024-11-16
【python】掌握 Flask：轻量级 Web 开发框架解析
路由是 Web 开发的基础，负责管理 URL 到视图函数的映射。在 Flask 中，路由定义非常简单，只需使用装饰器即可。这个代码段定义了一个路由，访问该路径时会返回 “Hello, Flask!通过
阅读更多2024-11-16
AI图片分析接口LiteAIServer摄像机实时接入分析平台未戴安全帽检测算法
随着人工智能技术的飞速发展，摄像机实时接入分析平台LiteAIServer工地未佩戴安全帽检测算法应运而生，为工地安全管理带来了革命性的变革。
阅读更多2024-11-16
2024新版pycharm如何切换anaconda虚拟环境
回归正题，导入项目后点击文件=>设置，找到解释器。不得不说这界面改的真不错，看着很舒服。另外在终端用指令切换也是可以的。添加解释器=>添加本地解释器。
阅读更多2024-11-16
计算机提示mfc140u.dll丢失的五种解决方法，了解mfc140u.dll错误的几种修复方法
当你尝试打开某些程序时，突然出现错误提示，告知你系统缺少 mfc140u.dll 文件，这可能让你感到困惑和无助。mfc140u.dll 是 Microsoft Foundation Class (M
阅读更多2024-11-16
k8s 中传递参数给docker容器
在 Kubernetes 中，可以通过多种方式将参数传递给 Dockerfile 或其运行的容器，常见的方式包括使用环境变量、命令行参数、配置文件等。
阅读更多2024-11-16
设计模式之工厂模式，但是宝可梦
作为一个细分了三个种类的设计模式，到底该如何取舍？比起直接new一个对象，使用对应模式的好处到底在哪？简单工厂模式：根据传入的参数决定产出的对象，可以隐藏一些创建的细节适用于需要根据条件创建不同对象的
阅读更多2024-11-16
【深度学习】wsl-ubuntu深度学习基本配置
这里注意一点，你换了源之后就最好不要开代理了，要不然搞不好下载失败，pip和conda都是。
阅读更多2024-11-16
nodejs和npm在gitbash中提示Not Found情况的解决办法
很多小伙伴学习了node以后，在cmd命令行中可以正常的获取node版本和npm版本，但是我们经常使用gitbash来管理git，这时候下载完gitbash后，在gitbash中输入node -v和n
阅读更多2024-11-16
判断子序列
给定一个长度为 n的整数序列 a1,a2,…,an以及一个长度为 m的整数序列 b1,b2,…,bm。请你判断 a序列是否为 b序列的子序列。子序列指序列的一部分项按原有次序排列而得的序列，例如序列
阅读更多2024-11-16

算法基础之分支限界法

算法原理

15谜问题

题目描述

输入输出

解题思路

代码实现

带时限的作业排序问题

题目描述

输入输出

解题思路

代码实现

经验总结

END

相关文章