LAPJV算法详解(ed-程序员宅基地

技术标签: 算法  css  机器学习  

Step1:Column Reduction 列约化

(这个代码是有问题的,它是来自于Jonker-Volgenant论文里面Pascal语言代码)

         逆序获得每列的最小值,储存在v数组中,初始u数组全部置0。x、y数组分别储存的是已分配的行列。比如:第四列最小值5,位置是(2,4),所以x矩阵第二个储存4,y矩阵第四个储存x,即x[2]=4,y[4]=2。如此逐一匹配x_{24},x_{33},x_{42},x_{21},又因为第一列的最小值位置重复出现在第二行,所以导致第四列匹配x_{24}作废,所以只剩下x_{33},x_{42},x_{21}位置被指派。(其实按照Jonker-Volgenant原文的理解,指派的位置应该还是x_{24},x_{33},x_{42},虽然这里x并不是很重要。-updated 2022/4/11这句个人理解有可能是错的,读者自己去理解一下)

此时:x=[0 1 3 2],y=[2 4 3 0]。

         总结,此操作主要是:尽量给每列都指派给最小行元素,某些行可能未分配。

Step2:Reduction Transfer 约化转移

         

从未指派行中到指派行进行转移。

 指派的行有2、3、4行。比如在第二行时,i=2,j_1=x_2=1,μ=min(除去该行指派的列之外该行c和对应的v之差)(就是指除去0以外最小的差值),v_1=v_1-(\mu-u_i)=2-(0-0)=2u_2=\mu=0(图中有误),再比如在第三行j_1=x_3=3,μ=4,v_3=v_3-(\mu-u_i)=3-(4-0)=-1

Step3 Augment Reduction of Unassigned Row  未指派行约化增广(含拍卖思想)

从未指派的行(第一行)开始,选择更新后的μ(除去该行指派的列之外该行c和对应的v之差,此时初始无指派行,所以不需要排除j_1)的最小值,选出最小值后对应的j_1也确定了;在除去j_1后更新最小值,第一次最小值记为k_1,第二次记为k_2。例子中k_1=1,j_1=2;k_2=2,j_2=4

\\k_1<k_2 \,so that\, v_2=v_2-(k_2-k_1)=4-(2-1)=3 \\r=y_2=4 \\ r>0\,so that\, x_4=0,x_1=2,y_2=1,\textbf{i=4}

更新后的x=[2 1 3 0],y=[2 1 3 0]。

直到出现n维的μ有相等的值或者r=0时停止

第二次循环

其中k_1=0,j_1=1;k_2=1,j_2=2

r=y_1=2,x_2=0,x_4=1,y_1=4,i=2

更新后的x=[2 0 3 1],y=[4 1 3 0]

第三次循环

其中k_1=0,j_1=4;k_2=1,j_2=1

r=y_4=0 stop

后面的增广(基于Dijkstra算法的最短路径增广)和对偶解更新不讲了,很简单,可以参考我的另一个blog。

笔者不是数学专业出身,在这之前对这部分知识完全不懂。如果有什么问题可以在评论区交流

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42691741/article/details/120292553

智能推荐

C#整数计算的几种四舍五入方式_c# 四舍五入取整数-程序员宅基地

文章浏览阅读2.1k次。1、正常的指定小数位数的四舍五入方法:_c# 四舍五入取整数

2018 前端性能优化清单(转载)-程序员宅基地

文章浏览阅读414次。2018 前端性能优化清单转载自 https://juejin.im/post/5a966bd16fb9a0635172a50a前言:这篇文章我在掘金翻译计划中跟着一起翻译的文章(感谢掘金翻译),我翻译了第三部分,然后校对了第二部分,这篇文章对于前端性能优化的技术还是比较新颖和全面的,所以...

蓝桥杯-单片机组备赛思路与大纲_csdn15届蓝桥杯单片机国赛-程序员宅基地

文章浏览阅读1.3k次,点赞30次,收藏26次。主要是针对第15届蓝桥杯-单片机组比赛。1.赛事介绍(第14届大纲)编程题:85%(编程涉及IIC、SPI、矩阵键盘、数码管等内容)客观题:15%(客观题主要是数电、C语言程序题,较少的51单片机基础知识与开发调试知识,极少出现模电题)省赛,报名费300元,自己出(部分学校的学院会报销),赛前学院会发比赛用的开发板(因此不用自己买,部分学校不会发)。_csdn15届蓝桥杯单片机国赛

React-markdown ver.8中使用高亮插件rehype-highlight样式无效问题(babel-standalone)-程序员宅基地

文章浏览阅读29次。React-markdown中經常使用的代碼高亮插件rehype-highlight在babel-standalone環境下使用後,雖然容易看出效果,但卻無法實現代碼的不同顏色高亮,所有代碼的顏色都相同,失去了此插件最大的用途。

QRegExp-程序员宅基地

文章浏览阅读2.6k次,点赞4次,收藏15次。正则表达式正则表达式(regular expression)就是用一个“字符串”来描述一个特征,然后去验证另一个“字符串”是否符合这个特征。比如 表达式“ab+” 描述的特征是“一个 ‘a’ 和 任意个 ‘b’ ”,那么 ‘ab’, ‘abb’, ‘abbbbbbbbbb’ 都符合这个特征。正则表达式可以用来:(1)验证字符串是否符合指定特征,比如验证是否是合法的邮件地址。(2)用来查找字符串,从一个长的文本中查找符合指定特征的字符串,比查找固定字符串更加灵活方便。(3)用来替换,比普通的替换更强_qregexp

from alipay import AliPay ModuleNotFoundError: No module named ‘alipay‘_modulenotfounderror: no module named 'alipay-程序员宅基地

文章浏览阅读2.2k次。pip install aiohttp_modulenotfounderror: no module named 'alipay

随便推点

Linux IO 学习笔记(二)——文件系统读写文件的流程_文件系统是先open还是先read-程序员宅基地

文章浏览阅读8.4k次。LInux任督二脉IO课程笔记,微信公众号:Linuxer。接上篇博客,下面来说第一个问题,VFS是如果打开和读写文件的。用户读写文件的流程file-&gt;dentry-&gt;inode-&gt;iops-&gt;address_space-&gt;disk 的流程: 通过struct找到磁盘inode节点对象: 一个进程打开的文件用struct file结构表示,这是VF..._文件系统是先open还是先read

Unity3D网络之Socket聊天室初探-程序员宅基地

文章浏览阅读218次。首先创建一个服务端程序,这个程序就用VS的控制台程序做就行了。 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Text;using System.Net.Sockets; namespace SocketServer { class Program..._unitysocket聊天室收不到消息

Python实现多个视频合成视频的功能你知道吗_python合成视频-程序员宅基地

文章浏览阅读1.5k次。前言本文提供将多个视频拼接为一个视频的Python工具代码,其中有一些限制条件,下面的代码说明会提到。环境依赖ffmpeg环境安装,可以参考:windows ffmpeg安装部署本文主要使用到的不是ffmpeg,而是ffprobe也在上面这篇文章中的zip包中。ffmpy安装:pip install ffmpy -i https://pypi.douban.com/simple代码#!/user/bin/env python# coding=utf-8""_python合成视频

(一)微信小程序云开发之云数据库基础_微信小程序开发云数据库-程序员宅基地

文章浏览阅读2.2k次,点赞6次,收藏21次。  一直以来在做微信小程序时都是自己配个服务器,然后写个接口供小程序调用做数据交互的,但是现在在带非计算机专业的学生的时候这个模式就行不通了,接口根本不可能自己写,所以只能利用微信小程序提供的云数据库来实现。以前自己也一直偷懒不想去接触这个云开发,总觉得自己配服务器更自由,这次没办法,就只能去整理下,给学生提供比较有针对性的入门说明,以下的内容基本都是来自官网文档,只是做了下归纳整理。  步骤一、在”微信开发者工具”的左上方点击“云开发”后出现"云开发控制台"窗口,在该窗口中点击“数据库”,并在左侧的“_微信小程序开发云数据库

深入理解计算机系统实验日志(三)——Memory Mountain_存储器山实验-程序员宅基地

文章浏览阅读2.5k次,点赞2次,收藏15次。简介:存储器山:具有不同的时间局部性和空间局部性的程序,对存储器层次结构的利用效率是不同的。局部性较好,则能得到较快的访问速率。构造一个存储器测试程序,以不同的时间局部性和空间局部性对存储器进行访问,就能得到存储器系统在不同的局部性下的性能(即访问速率)。以控制时间局部性的变量为x轴,控制空间局部性的变量为y轴,存储器访问速率为z轴,就能得到一个三维图形,它看起来像一座有着山峰,山脊和山坡的小山,即存储器山。(参考百度百科)*本文将简单介绍如何自制存储器山并对实验结果进行详细分析。I. 制作过程(在_存储器山实验

免费DDOS攻击测试工具大合集_ddos工具csdn-程序员宅基地

文章浏览阅读1.8k次。FreeBuf微科普:DoS(Denial Of Service)攻击是指故意的攻击网络协议实现的缺陷或直接通过野蛮手段残忍地耗尽被攻击对象的资源,目的是让目标计算机或网络无法提供正常的服务或资源访问,使目标系统服务系统停止响应甚至崩溃(关于DDoS更多认识请点击这里)。然而随着网络上免费的可用DDOS工具增多,Dos攻击也日益增长,下面介绍几款Hacker常用的Dos攻击工具。_ddos工具csdn