网络优化2|最小生成树|Kruskal|Prim|Matlab

最小生成树问题

连通图 G = ( V , E ) G=(V,E) G=(V,E),若G中不含任何回路,则称G为树。
∣ V ∣ = 1 |V |=1 V=1时称之为平凡树
![[Pasted image 20240826122021.png]]

生成树

G = ( V , E ) G=(V,E) G=(V,E),若G的一个生成子图是一棵树,则称之为G的一棵生成树,或者支撑树
![[Pasted image 20240826122236.png]]

定理

任何连通图至少有一棵生成树
![[Pasted image 20240826122331.png]]

最小生成树

无向图G的所有生成树中,边的权值总和最小的称为G的最小生成树,或最短树
![[Pasted image 20240826122525.png]]

性质

假设一个图中存在最小生成树,并且该图具有n个节点,m条边,则该图的最小生成树一定含有n个节点,并且具有n-1条边

最小生成树构造方法
  1. Kruskal算法
    每次选择一条最小且不会构成回路权边直至构成一个生成树
  2. Prim算法
    从一个结点的子图开始构造生成树:
    选择连接当前子图和子图外结点的最小权边,将相应结点和边加入子图,直至将所有结点加入子图。

构造最小生成树Kruskal算法

Kruskal算法基本思想
  1. 按所有边权值排序,升序(从小到大)
  2. 按排好序的边集合,选择一条边加入生成树
    贪心准则:不会产生环路
    按耗费递增顺序考察每条边
  • 若产生环路,丢弃
  • 否则,加入
Kruskal算法示例

![[Pasted image 20240826124506.png]]

B = ( 1 1 2 2 3 4 4 5 2 3 3 4 5 5 6 6 1 2 3 5 4 3 2 1 ) B=\begin{pmatrix} 1&&1&&2&&2&&3&&4&&4&&5 \\ 2&&3&&3&&4&&5&&5&&6&&6 \\ 1&&2&&3&&5&&4&&3&&2&&1 \end{pmatrix} B= 121132233245354453462561
按权值排序
B ′ = ( 1 5 1 4 2 4 3 2 2 6 3 6 3 5 5 4 1 1 2 2 3 3 4 5 ) B'=\begin{pmatrix} 1&&5&&1&&4&&2&&4&&3&&2 \\ 2&&6&&3&&6&&3&&5&&5&&4 \\ 1&&1&&2&&2&&3&&3&&4&&5 \end{pmatrix} B= 121561132462233453354245
加入第一条边
![[Pasted image 20240826125252.png]]

加入第二条边
![[Pasted image 20240826125337.png]]

第三条边
![[Pasted image 20240826125350.png]]

加入46
![[Pasted image 20240826125413.png]]

不能加入23,和45会形成回路
![[Pasted image 20240826125448.png]]

加入35
![[Pasted image 20240826125513.png]]

Kruskal算法的Matlab实现
s = [1 1 2 2 3 4 4 5]; 
t = [2 3 3 4 5 5 6 6];
weights = [1 2 3 5 4 3 2 1]; 
G = graph(s, t, weights);
p = plot(G, 'EdgeLabel', G.Edges.Weight);
[T, pred] = minspantree(G); 
highlight(p,T)

![[Pasted image 20240826125829.png]]

构造最小生成树Prim算法

贪心准则

  • 加入后仍形成树,且耗费最小
  • 始终保持树的结构一一Kruskal算法是森林
    算法过程
  1. 从单一顶点的树T开始
  2. 不断加入耗费最小的边 ( u , v ) (u,v) (u,v),使 T ∪ { ( u , v ) } T\cup \left\{ (u,v) \right\} T{(u,v)}仍为树
  3. u , v u,v u,v中有一个已经在T中,另一个不在T中
Prim算法示例过程

![[Pasted image 20240826132918.png]]

W = ( 0 1 2 ∞ ∞ ∞ 1 0 3 5 ∞ ∞ 2 3 0 ∞ 4 ∞ ∞ 5 ∞ 0 3 2 ∞ ∞ 4 3 0 1 ∞ ∞ ∞ 2 1 0 ) W=\begin{pmatrix} 0&&1&&2&&\infty&&\infty&&\infty \\ 1&&0&&3&&5&&\infty&&\infty \\ 2&&3&&0&&\infty&&4&&\infty \\ \infty&&5&&\infty&&0&&3&&2 \\ \infty&&\infty&&4&&3&&0&&1 \\ \infty&&\infty&&\infty&&2&&1&&0 \end{pmatrix} W= 0121035230450324301210
从v1开始,v2和v3选,选择权值小的那一条边,连接v1v2
![[Pasted image 20240826133434.png]]

从相邻的边开始选,v1v3,v2v3,v2v4中选,选择权值最小的边v1v3
![[Pasted image 20240826133526.png]]

从v2v4和v3v5选择权值小的边,v3v5
![[Pasted image 20240826133647.png]]

再选择v5v6
![[Pasted image 20240826133719.png]]

选择v6v4
![[Pasted image 20240826133730.png]]

Kruskal算法和Prim算法比较

![[Pasted image 20240826133825.png]]

m是边数,n是顶点

最小生成树的应用

制造系统的分组技术

![[Pasted image 20240826134117.png]]
![[Pasted image 20240826134200.png]]

设用 M i M_{i} Mi表示需由机器 i i i加工的零件集,对任意两台机器 i , j i,j i,j,定义相异度
w ( i , j ) = ∣ M i ⊕ M j ∣ M i ∪ M j w(i,j)=\frac{| M_{i}\oplus M_{j}|}{M_{i}\cup M_{j}} w(i,j)=MiMjMiMj
![[Pasted image 20240826134507.png]]

⊕ \oplus ,对称差
分子:在机器i但不在机器j上加工,或在机器j但不在机器i上加工的零件数
分母:或在机器i,或在机器j上加工的零件数
显然 0 ≤ w ≤ 1 0\le w\le 1 0w1

构造加权图

以机器为顶点,作一个完全图,每条边 ( i , j ) (i,j) (i,j)被赋予权 w ( i , j ) w(i,j) w(i,j)

原问题的转化

加权图的最小生成树是由那些相异度最小的边构成的连通图,如果希望把机器分成k个组,就继续删去最小生成树上权最大的k-1条边。于是得到k个分离的子树,每棵树的顶点集就构成各机器组。

对表1给出的数据,加权完全图的边权矩阵如下:

[1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8; 
2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;
0.5 1 0.89 0.14 1 1 1 1 1 1 0.6 2 1 1 1 1 1 1 1 1 1 0.5 0.87 0.67 0.75 0.75 1 1 1 1 1 1 1 1 0 1 1]

第一行表示每条边的起点,第二行表示每条边的终点,第三行对应每条边的相异度例如第一列1 2 0.5,就表示边12的相异度为0.5,下面我们简单说明一下计算过程:
第1台机器能加工的零件为2, 3, 7, 8, 9, 12, 13
第2台机器能加工的零件为2, 7, 8, 11, 12
两者的并集为2, 3, 7, 8, 9, 11, 12, 13,
两者的交集为2,7,8,12,
则对称差为3, 9, 11, 13,
因此边12的相异度 w ( 1 , 2 ) = w(1,2)= w(1,2)=对称差元素个数/并集元素个数=4/8=0.5

sj=[1 1 1 1 1 1  1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8; 
2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5  6 7 8 9 6 7 8 9 7 8 9 8 9 9;
0.5 1 0.89 0.14 1 1 1 1 1 1 0.62 1 1 1 1 1  1 1 1 1 0.5 0.87 0.67 0.75 0.75 1 1 1  1 1 1 1 1 0 1 1];
s = sj(1,:); 
t = sj(2,:);
weights = sj(3,:);
G = graph(s, t, weights);
[T, pred] = minspantree(G);
subplot(1, 2, 1);
plot(G, 'EdgeLabel', G.Edges.Weight); 
subplot(1, 2, 2);
plot(T, 'EdgeLabel', T.Edges.Weight);

![[Pasted image 20240826140129.png]]

要分为三组,去掉两条最大的边
去掉1和0.87
![[Pasted image 20240826140157.png]]

机器的分组
3,9
1,2,5
4,6,7,8

机器分组的目的是减少零件跨组加工的情况
相异度 = 1,表示两个机器加工的零件是完全不同的,因此不会出现跨机器加工的情况,这两台机器可以分到不同的组。
相异度w = 0,表示两台机器加工零件完全相同,因此应该分到一个组里才能保证不会出现跨组加工现象。
相异度w越小,二者在一组里的可能性越大,因此可以达到我们对机器分组的目的。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue3+Ts封装input组件时遇到的问题

使用input事件监听输入框变化时,如果当前使用的输入法是中文,他也会触发input事件,正常来说,中文没有输入完毕是不用触发事件的。 控制台打印时发现: 那么我们应该怎么去规避这件事呢? 其实input还有几个事…

echarts地图-单独给香港和澳门画引导线

因为香港特别行政区和澳门特别行政区的名字特别长又需要显示全名 所以显示在地图上会挤在一起,所以根据天地图的坐标来加了两个引导线(echarts5以下!!!) var fullName {北京: 北京市,天津: 天津市,河北: …

利用深度学习技术来实现街景图像的语义分割(街景图像语义分割)

本项目致力于利用深度学习技术来实现街景图像的语义分割。通过精确地识别和分类图像中的每个像素,该技术能够自动划分出街道、人行道、车辆、行人等各种不同的物体类别。这在智能交通系统、自动驾驶、城市规划等领域有着广泛的应用前景。 技术实现 深度学习模型&am…

从永远到永远-日语学习-て形用法及变形规律

て形用法及变形规律 0.前置知识1.常见用法1.请求某人做某事 「~てください」2.几个连续发生的动作 ~て、~て、~て3.两个动作先后发生「てから」4. 表示许可 「てもいいです」5.表示禁止 「~てはいけません」6.「&#…

IPv4和IPv6的区别是什么?什么是局域网和广域网,公网IP和私有IP?

文章目录 1.基本网络2.局域网3.广域网4.IPv4与NAT5.公网IP和私有IP6.IPv6 1.基本网络 我们都知道计算机的数据都是存在各自硬盘中的,与其他计算机之间没有人任务关系. 假设计算机A需要给计算机B发送数据,可以选择使用U盘这类移动存储数据来拷贝数据来实现数据交互,但是这样一…

Docker 部署 Kafka 可视化 Kafka-UI

前言 本文部署的Kafka-UI 是基于Docker Compose 部署 Kafka的KRaft模式,如有需要可访问下文链接 Docker Compose 部署 Kafka的KRaft模式 不用依赖 Zookeeper 此部署也适用于不是docker部署的kafka集群 1.启动 Kafka-UI 服务 1.1 kafka 来自docker安装 docker r…

swagger,Knife4j和Yapi

目录 swagger swagger的作用 swagger的使用 一.导入依赖 二.创建swagger配置类,交给SpringIoC容器管理 三.使用swagger依赖的注解来给接口层(controller)的各种方法进行注释 Api ApiOperation ApiImplicitParam ApiModel ApiModelProperty 四:…

mac苹果电脑配置Docker最新国内源

如图: 具体配置如下: {"builder": {"gc": {"defaultKeepStorage": "20GB","enabled": true}},"experimental": false,"registry-mirrors": ["https://docker.anyhub.us.kg", &…

ssrf漏洞之php-fpm未授权访问漏洞利用

目录 环境搭建 ​编辑漏洞点寻找 开始攻击 结果 环境搭建 在你的网站目录下创建一个新的php文件&#xff0c;内容如下 <?php highlight_file(__FILE__); $url $_GET[url]; $curl curl_init($url); curl_setopt($curl, CURLOPT_HEADER, 0); $responseText curl_exec…

ES6笔记总结:第四天(ES6完结)

Xmind鸟瞰图&#xff1a; 简单文字总结&#xff1a; node的模块化&#xff1a; 1.CommonJS 规范&#xff1a;Node.js 遵循 CommonJS 模块规范&#xff0c;该规范定义了如何在服务器环境中实现模块化&#xff0c;包括如何定义模块、如何引入和使用模块。 2.模块的定义&…

CISAW信息安全保障人员考试合格分数是多少?

在网络安全领域&#xff0c;众多认证证书中&#xff0c;CISAW信息安全保障人员认证备受瞩目。 随着信息安全专家的需求激增&#xff0c;国内面临着专业人才的短缺&#xff0c;越来越多人投身于CISAW认证考试。 那么&#xff0c;要通过CISAW认证需多少分数呢&#xff1f;答案是…

【知识图谱】2.知识抽取与知识存储

目录 一、知识抽取 1、实体命名识别&#xff08;Name Entity Recognition&#xff09; 2、关系抽取&#xff08;Relation Extraction&#xff09; 3、实体统一&#xff08;Entity Resolution&#xff09; 4、指代消解&#xff08;Coreference Resolution&#xff0…

【面试问题汇总】

面试问题汇总: Math.round函数:基础加0.5,向下取整 MySQL查询执行流程: 当我们执行一条SQL查询语句时,MySQL数据库会按照以下步骤进行处理: 语法解析器会对SQL语句进行解析,检查SQL语法是否正确。元数据查询器会检查查询的表和字段是否存在,以及当前用户是否具有相应…

RFID光触发标签在零售行业的深度应用

零售行业作为现代经济的重要组成部分&#xff0c;面临着诸多挑战和竞争压力&#xff0c;消费者需求的多样化、快速变化的市场趋势以及日益复杂的供应链管理&#xff0c;都对零售商提出了更高的要求&#xff0c;在这样的背景下&#xff0c;寻求创新的技术解决方案以提高运营效率…

Openstack 与 Ceph集群搭建(下): Openstack部署

文章目录 文章参考部署节点准备1. 修改Host文件与hostname名称2. 安装NTP软件3. 网卡配置信息4. 开启Docker共享挂载5. 安装python虚拟环境6. 安装kolla-ansible7. 加载Ansible galaxy requirements Openstack 安装前预配置1. 配置密码2. 配置multinode文件3. 修改全局配置文件…

在Windows上用Visual Studio编译Tesseract

Tesseract是著名的OCR&#xff08;文字识别&#xff09;开源项目。我想自己编译它的源代码。然而总体而言&#xff0c;大型开源项目在Windows上编译多少都会有些磕磕绊绊&#xff0c;如果有幸最后成功了&#xff0c;都值得写一篇文章来纪念一下。这便是本文的由来。 编译环境&…

客户端可以访问ntp时钟源,时间却一直不同步的问题

ntp时钟源通常是通过开放123 的udp端口对外提供ntp服务的&#xff0c;udp端口的访问可以通过nc -uvz xx.xx.xx.xx 123 端口进行验证&#xff0c;验证发现ntp时钟服务的123端口是开放的&#xff0c;也没有防火墙拦截123端口&#xff0c;但为什么客户端不同步ntp时钟源呢&#xf…

OpenCV杂项图像变换(1)自适应阈值处理函数adaptiveThreshold()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 函数对数组应用自适应阈值。 该函数根据以下公式将灰度图像转换为二值图像&#xff1a; 对于 THRESH_BINARY: t e x t d s t ( x , y ) { maxV…

OpenCV几何图像变换(10)透视变换函数warpPerspective()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 warpPerspective 函数使用指定的矩阵对源图像进行透视变换&#xff1a; dst ( x , y ) src ( M 11 x M 12 y M 13 M 31 x M 32 y M 33 , M…

C++笔记10•容器适配器:stackqueue priority_queue•

从C中看stack&queue&priority_queue 1.stack的介绍 官方stack实现&#xff1a; 本质是一个数组 1. stack 是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。 2. stack 是作为容器适…