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

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

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

相关文章

OLED双面显示广告机的应用场景

OLED双面显示广告机是一种创新的广告设备,它具有双面显示屏幕,可以同时向两个方向展示广告或信息。这种设备被广泛应用于各种场景,例如: 商业展示:在大型商业场所,如购物中心、百货商场等,OLED双…

WPS导出的PDF比较糊,和原始的不太一样,将带有SVG的文档输出为PDF

一、在WPS的PPT中 你直接输出PDF可能会导致一些问题(比如照片比原来糊)/ 或者你复制PPT中的图片到AI中类似的操作,得到的照片比原来糊,所以应该选择打印-->高级打印 然后再另存为PDF 最后再使用AI打开PDF文件再复制到你想用…

redis单机版本安装

redis单机版本安装 1.redis单机版源码编译安装搭建(4.0示例) redis下载地址 https://redis.io/download redis源码编译 #!/bin/sh yum install -y wget gcc gcc-c make tar openssl openssl-devel cmakecd /usr/local/src wget http://download.redis.io/releases/redis-4…

webpack优化打包速度

webpack打包速度太慢 优化 1.多线程打包 js压缩和loader 2.优化启动速度 hard-source-webpack-plugin 3.删除无用的 分析类插件 4.DllPlugin通道打包 1.webpack多线程打包 loader loader 使用 thread-loader 将他放置你要使用的loader前面就行,不过这个lorder例如s…

文章解读与仿真程序复现思路——电力系统自动化EI\CSCD\北大核心《参与电网削峰调节的电动重卡换电站调度策略》

标题"参与电网削峰调节的电动重卡换电站调度策略"表明这是一个关于电动重型卡车和电网协同运营的主题。下面对标题中的关键术语进行解读: 电动重卡: 指的是使用电力驱动而不是传统燃油的重型卡车,通常是指货运卡车。电动卡车的使用…

封装flutter webview页面

例如在flutter里面跳转百度页面 需要安装webview_flutter webview_page.dart import package:flutter/material.dart; import package:webview_flutter/webview_flutter.dart;class MyWebView extends StatefulWidget {const MyWebView({super.key, required this.webViewUrl,…

堆栈_有效括号

题比较特殊,主要在于它的所有要输入,都是左括号开头,没有右括号开头的,比如"] [",这种是不算为括号的,由于必然是对称的,若能符合,因而直接在遇到右括号时,检查…

LeetCode刷题---打家劫舍问题

顾得泉:个人主页 个人专栏:《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂,年薪百万! 一、打家劫舍 题目链接:打家劫舍 题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定…

Java实现堆

堆是一种基于完全二叉树的数据结构,它分为大根堆和小根堆。在大根堆中,每个节点的值都大于或等于其子节点的值;而在小根堆中,每个节点的值都小于或等于其子节点的值。 在Java中,我们可以使用数组来表示堆。由于完全二…

RS232串口_笔记

这里写目录标题 1、RS232串口理论起始位数据位校验位LSB & MSB示波器查看数据信号对应连接方式 1、RS232串口理论 UART(通用异步收发传输) 是一种通信协议,而 RS232 (串行通信接口)是种物理接口标准。UART 是一种用于在计算机和外部设备之间传输数据的协议&…

鸿蒙系统开发手册 - HarmonyOS内核驱动层源码分析

众所周知系统定义HarmonyOS是一款“面向未来”、面向全场景(移动办公、运动健康、社交通信、媒体娱乐等)的分布式操作系统。在传统的单设备系统能力的基础上,HarmonyOS提出了基于同一套系统能力、适配多种终端形态的分布式理念,能…

链表高频面试题

1. 两个链表第一个公共子节点 LeetCode160 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: listA [4,1,8,4,5], listB [5…

11-22 SSM3

书城分页查询 使用mybatis分页插件: 请完成登陆注册 -> 跳转到首页 解决前端上架时间点击切换 以及侧边栏点击由背景颜色的改变 完成超链接的绑定点击时间 -> jquery $(document).ready(function() { // 初始化上架时间状态为 true(上架&…

记录一次爱快路由ACL策略引起的大坑

环境: A公司和B公司采用爱快的ipsec互联 B公司同时有加密软件限制网络 问题:对方ERP无法连接我们的数据库服务器 先简单测试了下1433端口是不是通的 下面的测试结果,直接ping是通的,但是加上1433端口后就不通 排查过程&#xff1…

centos7下执行yum命令报错

前言 在Linux系统中,安装nginx时候,需要先安装环境。 Nginx是使用C语言开发,安装nginx需要先从官网上将源码下载,然后编译,编译需要gcc环境,但是在安装gcc环境的时候,执行命令报错。 yum install –y gcc-…

【开源】基于JAVA的大学计算机课程管理平台

项目编号: S 028 ,文末获取源码。 \color{red}{项目编号:S028,文末获取源码。} 项目编号:S028,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 实验课程档案模块2.2 实验资源模块2…

有什么值得推荐的node. js练手项目吗?

前言 可以参考一下下面的nodejs相关的项目,希望对你的学习有所帮助,废话少说,让我们直接进入正题 1、 NodeBB Star: 13.3k 一个基于Node.js的现代化社区论坛软件,具有快速、可扩展、易于使用和灵活的特点。它支持多种数据库&…

使用JAVA语言写一个排队叫号的小程序

以下是一个简单的排队叫号的小程序&#xff0c;使用JAVA语言实现。 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class NumberingSystem {public static void main(String[] args) {Queue<String> queue new LinkedList<…

WPF绘制进度条(弧形,圆形,异形)

前言 WPF里面圆形进度条实现还比较麻烦,主要涉及到的就是动态绘制进度条的进度需要用到简单的数学算法。其实原理比较简单,我们需要的是话两条重叠的弧线,里面的弧线要比里面的弧线要宽,这样简单的雏形就出来了。 基础写法 我们可以用Path来绘制弧线,代码如下: <Gr…

推荐几款python在线学习和电子书网站

学习python的过程中&#xff0c;虽然下载了很多的电子书&#xff0c;但是在学习过程中基本上都是通过一些在线网站或者在线电子书进行的。 下面给大家推荐几个在线学习教程网站和电子书网站。 《菜鸟教程》 一句话介绍&#xff1a;很多初学者的选择 网址&#xff1a;https:…