算法设计与分析复习--分支界限法

文章目录

  • 上一篇
  • 分支界限法性质
  • 装载问题
  • 0-1背包问题
  • 单源最短路问题
  • 最大团问题
  • 下一篇

上一篇

算法设计与分析复习–回溯法(二)

分支界限法性质

分支界限法是按广度优先策略或最小耗费优先遍历问题的解空间树。

搜索解空间:

  1. 子集树
  2. 排列树

搜索方式:广度优先遍历(队列)或最小耗费优先(堆)

方法:确定解空间,设计合适的限界函数(在拓展时删除不必要的孩子结点),组织活结点表

但是由于每一层对应的cw, rw是不同的,所以需要用一个node的数据结构存储每一个节点的

装载问题

问题描述:n个集装箱要装到2艘重量分别 c 1 c_1 c1, c 2 c_2 c2的货轮,其中集装箱 i i i的重量为 w i w_i wi器满足集装箱重量之和小于两轮船载重。

最优装载方案:将第一艘船尽可能装满,将剩余的货箱装到第二搜轮船上。

约束函数:所装货物重量小于第一艘船载重
上界函数是:已装重量+剩余重量上界

使用队列的方式

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

int a[N], n, c1, sum = 0, bw = 0;

struct node
{
    int idx; // 层数
    int cw;  // 当前层的重量
    int rw;  // 剩余的重量
};

void bfs()
{
    queue<node> q;
    q.push({0, 0, sum});

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        bw = max(bw, t.cw); // 更新最大重量

        // 左扩展
        if (t.idx < n && t.cw + a[t.idx] <= c1)
        {
            q.push({t.idx + 1, t.cw + a[t.idx], t.rw - a[t.idx]});
        }
        // 右扩展
        if (t.idx < n && t.cw + t.rw > bw)
        {
            q.push({t.idx + 1, t.cw, t.rw - a[t.idx]});
        }
    }
}

int main()
{
    scanf("%d%d", &n, &c1);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }

    bfs();
    printf("%d\n", bw);
    return 0;
}

在这里插入图片描述

利用优先级进行查找时
我们将利用当前结点的价值上界
c w + r w cw + rw cw+rw
进行堆的构造
重构堆需要

priority_queue<node, vector<node>, cmp> heap;
cmp为比较函数,不过要比较符相反

在这里插入图片描述
例如greater是返回更大的
而构造小根堆就用greater

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

int a[N], n, c1, sum = 0, bw = 0;

struct node
{
    int idx; // 层数
    int cw;  // 当前层的重量
    int rw;  // 剩余的重量
};

struct cmp
{
    bool operator ()(const node &x, const node &y) const
    {
        return (x.cw + x.cw) < (y.cw + y.rw); // 优先队列的优先级按当前上界要用更大排,这里就要是小于
    }
};


void bfs()
{
    priority_queue<node, vector<node>, cmp > heap;
    heap.push({0, 0, sum});

    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();

        bw = max(bw, t.cw); // 更新最大重量

        // 左扩展
        if (t.idx < n && t.cw + a[t.idx] <= c1)
        {
            heap.push({t.idx + 1, t.cw + a[t.idx], t.rw - a[t.idx]});
        }
        // 右扩展
        if (t.idx < n && t.cw + t.rw > bw)
        {
            heap.push({t.idx + 1, t.cw, t.rw - a[t.idx]});
        }
    }
}

int main()
{
    scanf("%d%d", &n, &c1);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }

    bfs();
    printf("%d\n", bw);
    return 0;
}

在这里插入图片描述


由于优先队列的方式更难一些所以后面实现都是优先队列的方式

0-1背包问题

求法与装载问题一样,不如说装载问题特化成了0-1背包问题

但是在右剪枝的求法上和回溯法一样
但是bound函数用法不同了,bound就是求上界的函数,并且求得是当前结点的上界

左剪枝:不超过背包容量
右剪枝:cv + rv >= bv
rv是利用贪心背包的方式求得的

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<double, double> PDD;

const int N = 110;

int n, c;
vector<PDD> ob;
double bv = 0, sv = 0; // 将bv, sv初始化为0

struct node
{
    int idx;
    double cw;
    double cv;
    double ub;
    bool operator< (const node &x) const
    {
        return ub < x.ub;//利用ub堆排序
    }
};

bool cmp(PDD x, PDD y)
{
    return (x.second / x.first) > (y.second / y.first);//贪心排序
}

double bound(node x)
{
    double rcv = x.cv, rw = c - x.cw;
    int i = x.idx;//不同于回溯法,在输入时改变i的值,因为要计算当前结点的上界
    while (i < n && ob[i].first <= rw)
    {
        rw -= ob[i].first;
        rcv += ob[i].second;
        i++;
    }
    if (i < n)
        rcv += rw * (ob[i].second / ob[i].first);
    return rcv;
}

void bfs()
{
    priority_queue<node> heap;
    heap.push({0, 0, 0, bound({0, 0, 0, 0})}); // 初始节点的上界需要计算

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        printf("{%d, %d, %.1lf}\n", (int)t.cw, (int)t.cv, t.ub);//搜索顺序可视化

        if (t.idx == n)//到达叶子结点
        {
            if (t.cv > bv)
            {
                bv = t.cv;
            }
            continue; 
        }

        if (t.cw + ob[t.idx].first <= c) // 向左走
            heap.push({t.idx + 1, t.cw + ob[t.idx].first, t.cv + ob[t.idx].second, t.ub}); 
            
        node tmp = {t.idx + 1, t.cw, t.cv, bound({t.idx + 1, t.cw, t.cv, 0})};//需要填两次,定义临时变量
        if (bound(tmp) > bv)
            heap.push(tmp); // 向右走
    }
}

int main()
{
    scanf("%d%d", &n, &c);

    for (int i = 0; i < n; i++)
    {
        double w, v;
        scanf("%lf%lf", &w, &v);
        sv += v;
        ob.push_back({w, v});
    }

    sort(ob.begin(), ob.end(), cmp);

    bfs();
    printf("%d\n", (int)bv);

    return 0;
}

在这里插入图片描述
在这里插入图片描述

单源最短路问题

问题描述:给定一个带权有向图G = (V, E), 每条边的权值是一个正整数, 给定V中的一个顶点S,称作源点。要求:计算从源点到其他所有顶点的最短路径长度。

AcWing 850. Dijkstra求最短路 II

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int h[N], e[N], w[N], ne[N], idx = 0;
int dist[N], pre[N];
vector<int> ans;
bool st[N];
int n, m;

void add (int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void traceback(int k)
{
    if (k == 0) return;
    ans.push_back(k);
    traceback(pre[k]);
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});// first表示距离, second表示节点编号,这是因为在优先队列中是优先按元祖第一个元素进行排序

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;// ver表示节点编号

        if (st[ver])continue;
        st[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])// 因为要遍历Ver相连的所有边i所以提前将源点到ver的最短距离记作distance, 而w[i]记录的是第i个节点到j的距离(权重)i是与ver相连的边 
            // 将与ver相连的边更新为最短路径值,j是i的下一条边是一个指针关系
            {
                dist[j] = distance + w[i];
                pre[j] = ver;
                heap.push({dist[j], j});
            }

        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    else {
        traceback(n);
        reverse(ans.begin(), ans.end());
        puts("最短路径为:");
        for (auto i : ans)
            printf("%d ", i);
            puts("");
        return dist[n];
    }
}

int main ()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add (a, b, c);
    }
    printf("路径长度为:%d", dijkstra());

    return 0;
}

在这里插入图片描述

最大团问题

问题描述:给定无向图G = (V, E)。如果 U ⊆ V U\subseteq V UV, 求对任意 u , v ∈ U u, v \in U u,vU ( u , v ) ∈ E (u, v) \in E (u,v)E, 则称U是G的完全子图。
最大团就是一个图含顶点数最大的完全图,且要是这个图的子集。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 110;

int g[N][N], n, m, bn;
vector<int> ans;

struct node
{
    int idx;
    int cn;
    vector<int> x;
    int un;
    bool operator< (const node &p) const{
        return un < p.un;
    }
};

bool constrain(node c)
{
    for (int i = 0; i < c.idx - 1; i ++)//这里i不能到c.idx不然就会有它自身到自身为0会返回false,
    {
        if (c.x[i] == 1 && g[c.idx][i + 1] == 0)//x的下标是从0开始,而g[i][j]的下标是从1开始,所以要进行调整
            return false;
    }
    return true;
}

void bfs()
{
    priority_queue<node> heap;
    heap.push({0, 0, {}, n});
    
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        if (t.idx == n){
            if (t.cn > bn){
                ans = t.x;
                bn = t.cn;
            }
            continue;
        }
        
        node tmp = {t.idx + 1, t.cn + 1, t.x, t.un};
        tmp.x.push_back(1);//要提前加入,否则判断是少条件
        
        if (constrain(tmp))
            heap.push(tmp);
        
        tmp = {t.idx + 1, t.cn, t.x, t.un - 1};
        tmp.x.push_back(0);
        if (tmp.un >= bn)
            heap.push(tmp);
        
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
    
    bfs();
    printf("%d\n", bn);
    for (auto val : ans) {
        printf("%d ", val);
    }
    return 0;
}

在这里插入图片描述
在这里插入图片描述

下一篇

未完待续

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/177154.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

轻量级压测工具Apache Bench实战

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…

【c++】——类和对象(下) 万字解答疑惑

作者:chlorine 专栏:c专栏 目录 &#x1f6a9;再谈构造函数 &#x1f393;构造函数体赋值 &#x1f393;初始化列表 &#x1f6a9;explicit关键字 &#x1f6a9;static成员 &#x1f393;概念 面试题&#xff1a;计算创建多少个类对象 &#x1f393;特性 【问题】(非)…

香蕉派BPI-M4 Zero单板计算机采用全志H618,板载2GRAM内存

Banana Pi BPI-M4 Zero 香蕉派 BPI-M4 Zero是BPI-M2 Zero的最新升级版本。它在性能上有很大的提高。主控芯片升级为全志科技H618 四核A53, CPU主频提升25%。内存升级为2G LPDDR4&#xff0c;板载8G eMMC存储。它支持5G WiFi 和蓝牙, USB接口也升级为type-C。 它具有与树莓派 …

内部网关协议_路由信息协议RIP_开放路径优先OSPF协议_基本知识

目录: 因特网路由选择协议概述 路由信息协议RIP 开放路径优先OSPF协议 因特网路由选择协议概述 一.路由选择分类 静态路由选择和动态路由选择 静态路由选择: 采用人工配置的方式给路由器添加网络路由、默认路由和特定主机路由等路由条目。静态路由选择简单、开销小&#…

在Spring Boot中使用ECharts绘制数据图表

使用ECharts来完成一些花里胡哨的图表吧&#xff0c;一般这种需求我们在我们的客户端不太常见&#xff0c;但是&#xff0c;我们在后端进行各种数据统计的时候就会发现ECharts的优点了&#xff0c;比如我们常常做的柱状图&#xff0c;折线图&#xff0c;雷达图等可视化形式&…

最常用的5款报表系统

在这个信息化飞速发展的时代&#xff0c;报表系统已经成为了企业管理和决策的重要工具。随着市场的需求不断增长&#xff0c;报表系统也在不断地更新和完善。如今&#xff0c;市面上有数不尽的报表系统&#xff0c;但是哪款才是最常用的呢&#xff1f;接下来&#xff0c;我们将…

CSS伪类选择器详细讲解

前言 伪类选择器在CSS中起到的作用可以说是至关重要的&#xff0c;如果CSS没有伪类选择器&#xff0c;有很多效果都要借助js来完成&#xff0c;这样不仅代码量增加&#xff0c;维护起来你难度也大。这样程序员的工作量大&#xff0c;也违背了CSS诞生的作用&#xff0c;就是提高…

STM32F103C8T6第5天:独立看门狗、窗口看门狗、dma实验

1. 独立看门狗IWDG介绍&#xff08;341.45&#xff09; 什么是看门狗&#xff1f; 在由单片机构成的微型计算机系统中&#xff0c;由于单片机的工作常常会受到来自外界电磁场的干扰&#xff0c;造成程序的跑飞&#xff0c;而陷入死循环&#xff0c;程序的正常运行被打断&#…

美国云服务器:CN2/纯国际/高防线路介绍

​  谈到国外云服务器&#xff0c;美国云服务器必有一席之地。但是&#xff0c;一般来说使用美国云服务器&#xff0c;线路质量是一个重要的考虑因素。如果线路选择不合理&#xff0c;就有可能造成速度减慢或者安全隐患问题产生。本文将介绍美国云服务器的CN2/纯国际/高防三种…

PHP反序列化简单使用

注&#xff1a;比较简陋&#xff0c;仅供参考。 编写PHP代码&#xff0c;实现反序列化的时候魔法函数自动调用计算器 PHP反序列化 serialize(); 将对象序列化成字符串 unserialize(); 将字符串反序列化回对象 创建类 class Stu{ public $name; public $age; public $sex; publi…

有一台电脑一部手机就可以在网上赚钱,这些项目你也可以学会

很多人都希望能够在家中或者闲暇的时候&#xff0c;能够在网上赚钱&#xff0c;而网络给了我们这样的可能。只要有一台电脑和一部手机&#xff0c;你就可以开始你的赚钱之旅。这些项目并不难&#xff0c;只要你肯学&#xff0c;就一定能够成功。 1、美工设计 这个副业主要是推荐…

python plot绘图

使用python绘制t-sne图&#xff0c;并保存 一下是一个将que_im_features向量可视化的例子&#xff1a; def emb_save(que_im_features,i):# 向量[75, 640, 11, 11], episodeimport numpy as npimport pandas as pdfrom sklearn import manifoldimport matplotlib.pyplot as p…

jmeter中调用python代码

1、安装pyinstaller pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pyinstaller 2、将py脚本打包 pyinstaller -F venv/get_image/OCR_jmeter_api.py 3、jmeter中添加OS Process Sampler并调用dist下的程序 4、执行jmeter

Jmeter 压测实战保姆级入门教程

1、Jmeter本地安装 1.1、下载安装 软件下载地址&#xff1a; https://mirrors.tuna.tsinghua.edu.cn/apache/jmeter/binaries/ 选择一个压缩包下载即可 然后解压缩后进入bin目录直接执行命令jmeter即可启动 1.2 修改语言 默认是英文的&#xff0c;修改中文&#xff0c;点击…

RubbleDB: CPU-Efficient Replication with NVMe-oF

RubbleDB: CPU-Efficient Replication with NVMe-oF 前言 这是ATC2023的文章&#xff0c;作者来自哥伦比亚大学这篇工作在LSM-tree多副本存储的场景下&#xff0c;利用NVMe-oF技术避免了LSM-tree副本上的重复合并&#xff0c;减少了CPU开销。 Introduction 为了提供高可用性…

Python 装饰器用法详解

目录 一、基本概念 二、语法形式 三、用法示例 1、用于日志记录 2、用于性能测试 3、用于事务处理 4、用于缓存结果 5、用于权限验证 总结 Python装饰器是Python中一种非常有用且强大的工具&#xff0c;它允许我们在不修改原有函数或类的基础上&#xff0c;对它们进行…

物联网AI MicroPython学习之语法 WDT看门狗外设

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; WDT 介绍 模块功能: 看门狗WDT&#xff08;WatchDog Timer&#xff09;外设驱动模块 接口说明 WDT - 构建WDT对象 函数原型&#xff1a;WDT(timeout)参数说明&#xff1a; 参数类型必选参数&#xff1f…

ultralytics yolov8 实例分割 训练自有数据集

参考: https://docs.ultralytics.com/datasets/segment/coco/ http://www.bryh.cn/a/613333.html 1、数据下载与转换yolo格式 1)数据集下载: 参考:https://universe.roboflow.com/naumov-igor-segmentation/car-segmetarion 下载的是coco格式,需要转换 2)coco2yolo t…

银行业务测试

1、商业银行四大类&#xff1a; 业务类系统、渠道类面试、MIS类系统、其他基础平台系统 2、银行系统开发流程&#xff08;UAT是行方&#xff09; 3、银行系统测试流程 4、对于不同的服务方式也不同&#xff0c;如:柜台、手机银行、网上银行&#xff0c;电话外呼&#xff0c;…

局域网共享打印机共享,简单至简至一键处理011bDll等问题

一、电脑系统是否激活&#xff08;可选&#xff09; 二、确保主客户端PC在同一局域网内&#xff08;可选&#xff09; 可以通过ping 目标地址 如ping 192.168.1.202&#xff1b;看是否可以正常通信 下面是惠普类型打印机共享问题关键&#xff08;文本记得保存&#xff09; …