2分图匹配算法
定义

- 节点u直接无边,v之间无边,边只存在uv之间。
- 判断方法:BFS染色法,全部染色后,相邻边不同色
无权二部图中的最大匹配
- 最大匹配即每一个都匹配上min(u, v)。
- 贪心算法可能导致,有些节点未匹配上
- 可以添加起始节点以及终止节点,使用网络流算法进行求解。

有权二部图中的最大匹配Maximum-Weight Bipartite Matching
- 每一条边都有权重,最大匹配追求的是整体的权重和最大。(整体收益最大)
- 最大匹配可以转化为最小匹配算法。即把权重*-1, 最小匹配的结果就是最大匹配的结果。
- 匈牙利算法可以解决最小匹配问题,但是u和v的节点数量需要保持一致,算法复杂度为O(n^3),暴力为O(n!)
匈牙利算法
-
构建u*u矩阵,没有边的为0
-
每一行减去每一行的最小值

-
每一列减去每一列的最小值

-
使用最小的线覆盖所有的0。如果线的数量小于u的数量,则剩下的继续找最小元素,然后递减,节点处加上该元素;如果数量相同,则优先找唯一有0的点进行匹配。




-
最大匹配结果可能不止1中,如5,2,3和5, 0, 5都是15。


- 如果uv节点不一致,可以通过补几个虚拟节点,权重设置为0,使得uv节点数量一致,那就可以用匈牙利算法求解了。
稳定婚配算法
- 一种特殊的2分图匹配问题
- 边由权重变成了顺序,而且是双向的
- 可以用gale-shapely算法求解
- 时间复杂度为O(n^2)
代码实现
- 通过找增广路径的方式进行求解
- 非匹配点出发,到非匹配点截至,中间为非匹配与匹配交替出现,然后变换状态即可。
- KM算法是加了权重的匈牙利算法,先把左边赋值最大权重,然后如果冲突,左边-detla, 右边+detla的操作,再通过增广路径求解。detla为lx+ly-weight
https://blog.csdn.net/sidnee/article/details/106298615
https://blog.csdn.net/qq_37457202/article/details/80161274
参考:
https://www.bilibili.com/video/BV1G54y157HA/?spm_id_from=333.788&vd_source=d141bc07699831d8053b781fd6944d5f
相关文章:
2分图匹配算法
定义 节点u直接无边,v之间无边,边只存在uv之间。判断方法:BFS染色法,全部染色后,相邻边不同色 无权二部图中的最大匹配 最大匹配即每一个都匹配上min(u, v)。贪心算法可能导致&…...
[EndNote学习笔记] 导出库中文献的作者、标题、年份到Excel
菜单栏Edit中,选择 Output Styles 在默认的 Annotated上进行修改,在Bibliography栏下的Templates中修改想要导出的格式 其中,每个粗体标题表示,针对不同的文献类型,设置相应的导出格式。一般为Journal Article&…...
SQL Sever 基础知识 - 数据查询
SQL Sever 基础知识 - 一、查询数据 一、查询数据第1节 基本 SQL Server 语句SELECT第2节 SELECT语句示例2.1 SELECT - 检索表示例的某些列2.2 SELECT - 检索表的所有列2.3 SELECT - 对结果集进行筛选2.4 SELECT - 对结果集进行排序2.5 SELECT - 对结果集进行分组2.5 SELECT - …...
Vue入门——v-on标签
文章目录 规则v-on 一、案例总结 规则 v-on 作用:为html标签绑定事件语法: v-on:事件名:“函数名”简写为 事件名“函数名” 注意:函数需要定义在methods选项内部 一、案例 我们给案件绑定一个单击事件 <!DOCTYPE…...
JVM:双亲委派(未完结)
类加载 定义 一个java文件从编写代码到最终运行,必须要经历编译和类加载的过程,如下图(图源自b站视频up主“跟着Mic学架构”)。 编译就是把.java文件变成.class文件。类加载就是把.class文件加载到JVM内存中,得到一…...
Leetcode 2661. 找出叠涂元素
Leetcode 2661. 找出叠涂元素题目 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1,m * n] 内的 所有 整数。从下标 0 开始遍历 arr 中的每个下标 i ,并将包含整数 arr[i] 的 mat 单元格涂色。请你找出 a…...
vscode代码调试配置
C/C代码调试 点击 vscode左侧的 run and debug,新建launch.json 和 tasks.json,并进行配置如下 launch.json {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more informati…...
PTA 7-225 sdut-C语言实验- 冒泡排序中数据交换的次数
听说过冒泡排序么?一种很暴力的排序方法。今天我们不希望你用它来排序,而是希望你能算出从小到大冒泡排序的过程中一共进行了多少次数据交换。 输入格式: 输入数据的第一行为一个正整数 T ,表示有 T 组测试数据。 接下来T行,每行…...
新的 BLUFFS 攻击导致蓝牙连接不再私密
蓝牙是一种连接我们设备的低功耗无线技术,有一个新的漏洞需要解决。 中间的攻击者可以使用新的 BLUFFS 攻击轻松窥探您的通信。 法国研究中心 EURECOM 的研究员 Daniele Antonioli 演示了六种新颖的攻击,这些攻击被定义为 BLUFFS(蓝牙转发和…...
安全测试之推荐工具(一)
文章目录 一、前言二、Web安全(一)AppScan(推荐)(二)AWVS(推荐)(三)Burp Suite(推荐)(四)OWASP ZAP 三、主机安…...
final关键字
修饰 类,属性,方法,局部变量(包括方法参数) 类似c语言的const 使用方式: 1 不希望类被继承 用final类(类很重要,担心别人重写/修改) 2 不希望某…...
WPF MVVM模式下如何将UI窗口变量传参到Viewmodel层
WPF MVVM模式下如何将UI窗口变量传参到Viewmodel层 UI层窗口定义 //窗口中绑定ViewModel<hc:GlowWindow.DataContext><viewmodel:MainWindowViewModel /></hc:GlowWindow.DataContext>//注册初始化事件<hc:Interaction.Triggers><hc:EventTrigger…...
条款22:将成员变量声明为private
1.前言 首先,我们应该利用反证法,看看为什么成员变量不该是public,然后再了解所有反对public成员变量的论点同样适用于protected成员变量。最后得出一个结论:成员变量应该是private。 2.为什么不用public 如果成员变量不是publ…...
PTA 7-224 sdut-C语言实验-排序问题
输入10个整数,将它们从小到大排序后输出,并给出现在每个元素在原来序列中的位置。 输入格式: 输入数据有一行,包含10个整数,用空格分开。 输出格式: 输出数据有两行,第一行为排序后的序列,第二行为排序…...
【JavaScript】3.2 JavaScript性能优化
文章目录 1. 避免全局查找2. 避免不必要的属性查找3. 使用快速的JavaScript方法4. 避免不必要的DOM操作5. 使用Web Workers进行后台处理总结 性能优化是任何编程语言的重要组成部分,JavaScript也不例外。在这个章节中,我们将探讨如何优化JavaScript代码&…...
pytorch bert实现文本分类
以imdb公开数据集为例,bert模型可以在huggingface上自行挑选 1.导入必要的库 import os import torch from torch.utils.data import DataLoader, TensorDataset, random_split from transformers import BertTokenizer, BertModel, BertConfig from torch import…...
《开箱元宇宙》:Madballs 解锁炫酷新境界,人物化身系列大卖
你是否曾想过,元宇宙是如何融入世界上最具代表性的品牌和名人的战略中的?在本期的《开箱元宇宙》 系列中,我们与 Madballs 的战略顾问 Derek Roberto 一起聊聊 Madballs 如何在 90 分钟内售罄 2,000 个人物化身系列,以及是什么原…...
4K-Resolution Photo Exposure Correction at 125 FPS with ~8K Parameters
MSLTNet开源 | 4K分辨率125FPS8K的参数量,怎养才可以拒绝这样的模型呢? 错误的曝光照片的校正已经被广泛使用深度卷积神经网络或Transformer进行广泛修正。尽管这些方法具有令人鼓舞的表现,但它们通常在高分辨率照片上具有大量的参数数量和沉…...
网络初识:局域网广域网网络通信基础
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、局域网LAN是什么?二、广域网是什么:三. IP地址四.端口号五.认识协议5.1五元组 总结 前言 一、局域网LAN是什么? 局域网…...
JVM之jps虚拟机进程状态工具
jps虚拟机进程状态工具 1、jps jps:(JVM Process Status Tool),虚拟机进程状态工具,可以列出正在运行的虚拟机进程,并显示虚拟机执 行主类(Main Class,main()函数所在的类)的名称,…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
