温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-12755375.html】到电脑端继续下载(重复下载不扣费)。
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。 2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。 3: 文件的所有权益归上传用户所有。 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。 5. 本站仅提供交流平台,并不能对任何下载内容负责。 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
本文(二分图带权匹配 KM算法与费用流模型建立.docx)为本站会员(乾***)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!
二分图带权匹配与最佳匹配什么是二分图的带权匹配?二分图的带权匹配就是求出一个匹配集合,使得集合中边的权值之和最大或最小。而二分图的最佳匹配则一定为完备匹配,在此基础上,才要求匹配的边权值之和最大或最小。二分图的带权匹配与最佳匹配不等价,也不互相包含。我们可以使用KM算法实现求二分图的最佳匹配。方法我不再赘述,可以参考tianyi的讲解。KM算法可以实现为O(NT)。KM算法的几种转化KM算法是求最大权完备匹配,如果要求最小权完备匹配怎么办?方法很简单,只需将所有的边权值取其相反数,求最大权完备匹配,匹配的值再取相反数即可。KM算法的运行要求是必须存在一个完备匹配,如果求一个最大权匹配(不一定完备)该如何办?依然很简单,把不存在的边权值赋为0。KM算法求得的最大权匹配是边权值和最大,如果我想要边权之积最大,又怎样转化?还是不难办到,每条边权取自然对数,然后求最大和权匹配,求得的结果a再算出eAa就是最大积匹配。至于精度问题则没有更好的办法了。求最小(大)权匹配的费用流建模方法求最小(大)权匹配,可以用最小(大)费用最大流的方法。和二分图最大匹配
Copyright © 2018-2021 Wenke99.com All rights reserved
工信部备案号:浙ICP备20026746号-2
公安局备案号:浙公网安备33038302330469号
本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。