程序员经验分享-hwhale

算法笔记：KM算法（Kuhn-Munkres Algorithm）

2023-05-16

带权二分图的最优匹配问题

算法笔记：匈牙利算法_UQI-LIUWJ的博客-CSDN博客

  •  匈牙利算法的一个问题是，找到的匹配不一定是最优匹配
    • 因为算法将每个匹配对象的地位视为相同的，在这个前提下求解最大匹配
  • 而很多时候，二部图连边是带权重的，在这个基础上的匹配才更贴近真实情况

1 KM算法举例

二部图的每条关系之间加入了权重

1.1 具体步骤

  • 首先对每个顶点赋值，称为顶标，将左边的顶点赋值为与其相连的边的最大权重，右边的顶点赋值为0。
  • 然后开始匹配
    • 匹配的原则是：
      • 只和权重与左边分数（顶标）相同（或比顶标大）的边进行匹配（边权重=左+右）
      • 若找不到边匹配，对此条路径的所有左边顶点的顶标减d，所有右边顶点的顶标加d。参数d我们在这里取值为0.1。

  • 对于左1，与顶标分值相同的边先标蓝。

  •  然后是左2，与顶标分值相同的边标蓝

     

  • 然后是左3，发现与右1已经与左1配对。
    • 首先想到让左3更换匹配对象
      • 然而根据匹配原则，只有权值大于等于0.9+0=0.9（左顶标加右顶标）的边能满足要求。于是左3无法换边。
    • 那左1能不能换边呢？
      • 对于左1来说，只有权值大于等于0.8+0=0.8的边能满足要求，无法换边。
      • 此时根据KM算法，应对所有冲突的边的顶点做加减操作，令左边顶点值减0.1，右边顶点值加0.1。

      •  再进行匹配操作，发现左3多了一条可匹配的边，因为此时左3对右2的匹配要求只需权重大于等于0.8+0即可，所以左3与右2匹配！

        •  

  • 最后进行左4的匹配，由于左4唯一的匹配对象右3已被左2匹配，发生冲突。进行一轮加减d操作，再匹配，左四还是匹配失败。两轮以后左4期望值降为0，放弃匹配左4。 

参考内容：带你入门多目标跟踪（三）匈牙利算法&KM算法 - 知乎 (zhihu.com)

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法笔记：KM算法（Kuhn-Munkres Algorithm） 的相关文章

  • PCL学习笔记——合并点云

    合并点云分为两种类型 xff1a 第一种是两个点云数据集的字段类型和维度相同 xff0c 合并之后点云只是点的数量增加了 xff1b 第二种是两个点云数据集的字段类型或维度不同 xff0c 但是点的数量相同 xff0c 合并之后相当于扩展了

  • 云服务器的图形界面的安装和远程连接xfce4 + VNC

    对于阿里和腾讯的云服务器学生价真的很优惠 xff0c 但是对于凑热闹买的我还是个小白 xff0c 我想装一个图形界面 xff08 特别是最近在用腾讯的CVM做HIT操作系统的实验 xff0c 其中有个软件必须要显示图形界面 xff09 较为

  • 【ROS学习】-tf学习(tf_monitor、tf_echo、static_transform_publisher、view_frames)

    写在前面 本文的内容主要来自 ros wiki 上的教程 xff1a http wiki ros org tf 简短总结 xff1a tf monitor 将当前的坐标系转换关系打印到终端控制台 tf echo lt source fram

  • Ubuntu使用WPS打开文档出现缺失字体情况解决方法

    一 问题描述 Ubuntu 通过官网下载deb安装 WPS 之后 xff0c 打开文档出现字体缺失的问题 xff1a 二 解决方法 下载缺失的字体 xff0c 百度网盘下载链接 xff08 TODO xff09 xff0c 然后解压 xff

  • PendSV中断服务函数

    之前在系统滴答定时器中断服务函数中调用API函数xPortSysTickHandler xff09 xff0c xPortSysTickHandler xff09 函数中通过向中断和状态寄存器的bit28写入1来启动PendSV中断 xff

  • 基于sumo和车牌识别数据的城市仿真

    前言 最近希望能仿真出一个城市的交通状态 xff0c 也就是知道在不同的需求加载下城市宏观交通状态的变化情况 xff0c 同时 xff0c 因为我手头有车牌识别数据 xff0c 因此需求将来自于车牌识别数据 但是仿真过后发现 xff0c 并

  • Linux:mkdir命令详解(-p,--verbose,-v,--version,-m,-Z,--context)

    Content 1 mkdir是什么2 mkdir使用2 1 version2 2 verbose v2 3 p parents 2 4 m mode 61 MODE2 5 Z2 6 context 61 CTX 2 6 1 单纯 cont

  • Python使用阿里云发送短信的两种方式

    参考文档https help aliyun com document detail 215764 html 安装依赖包 pip install alibabacloud tea openapi pip install alibabaclou

  • 手机投屏到电脑(以win10系统为例)

    总目录 文章目录 总目录前言一 电脑设置1 安装无线显示器2 完成投影偏好设置3 启动连接应用 二 手机设置三 优缺点分析总结 前言 手机投屏到电脑个人实操记录 一 电脑设置 1 安装无线显示器 首先win 43 i 进入设置 xff0c

  • 关于 nginx 配置ssl 无法访问，解决过程

    1 单独访问 以IP 43 端口的形式访问或 接口查看是否通 这是验证自己的服务或接口没有问题 2 单独以最简单的形式启动nginx 记住是最简单 xff0c 没有多余配置 xff0c 都是默认的 这是验证nginx启动没有问题 3 检查端

  • 1、FreeRTOS使用，Main函数中需要做的事情

    1 硬件初始化 xff08 也可以放在SystemInit中 xff09 时钟初始化 中断优先级分组 中断优先级分配 xff08 设置 xff09 外设初始化 xff08 时钟 xff0c GPIO xff0c 配置参数 xff0c 是否使

  • ubuntu22.04系统配置（一）（后续有kali的配置）

    ubuntu22 04系统配置深度学习 xff08 一 xff09 xff08 后续有kali的配置 xff09 摘要系统下载以及U盘拷贝系统的基本配置nvidia smi 摘要 配置这个东西真的踩了好多坑 xff0c 之前一直用的Wind

  • GINet：Graph Interaction Network for Scene Parsing（ECCV 2020）详解

    论文地址 xff1a https arxiv org pdf 2009 06160 pdf 一 背景 Scene Parsing 任务属于语义分割的一个分支 xff0c 也是把每个像素点分成一个具体的语义类别 xff0c 它和常见的语义分割

  • C++ string切割，分解字符串，C 库函数 - strtok()

    声明 下面是 strtok 函数的声明 char strtok char str const char delim 参数 str 要被分解成一组小字符串的字符串 delim 包含分隔符的 C 字符串 返回值 该函数返回被分解的第一个子字符串

  • BGP详解

    BGP协议详解 BGP是一种边界网关协议 但是也属于动态路由协议 一 BGP的特征 xff08 一种外部路由协议 xff0c 用来在AS之间传递路由信息 xff0c 是一种增强版的距离矢量协议 xff09 1 可靠的路由更新机制 传输协议

  • el-input-number 如何实现默认不填充0

    只需要把数据设置未 undefined 的就可以了 lt el input number v model 61 num 64 change 61 handleChange min 61 1 max 61 10 label 61 描述文字 g

  • vue项目 el-input输入框字符限制，只显示英文及数字

    element的el input没有限制输入的内容 xff0c 想要限制输入内容就需要自己来开发 xff0c 我使用的方式是正则来判断进行再次赋值实现的 xff0c 不废话上代码 xff1b lt el input v model 61 3

  • cdn方式使用vue和element-ui进行前端开发

    安装 按照vue和element ui的官网开发指南中提供的cdn安装方式 xff0c 直接以script方式引入 要注意引入顺序 span class token comment lt 引入样式 gt span span class to

  • vue el-table 如何实现表格根据分页索引自增长

    在el table 里设置type 61 index xff0c 可以实现表格的索引自增长 xff0c 但是如果我们给表格增加了分页 xff0c 切换页面索引任然是从1 20 xff08 20是自己分页的数量 xff09 xff0c 那么想

  • Vue的计算属性和监听属性

    1 计算属性 computed 当依赖数据发生变化时 xff0c 计算属性会被重新计算 有且只有在依赖数据发生变化时它才会重新计算 xff0c 其他的数据变化对计算属性 应用场景 xff1a 数据的计算显示 v for用v if的计算 sp

随机推荐

热门标签