科技: 人物 企业 技术 IT业 TMT
科普: 自然 科学 科幻 宇宙 科学家
通信: 历史 技术 手机 词典 3G馆
索引: 分类 推荐 专题 热点 排行榜
互联网: 广告 营销 政务 游戏 google
新媒体: 社交 博客 学者 人物 传播学
新思想: 网站 新书 新知 新词 思想家
图书馆: 文化 商业 管理 经济 期刊
网络文化: 社会 红人 黑客 治理 亚文化
创业百科: VC 词典 指南 案例 创业史
前沿科技: 清洁 绿色 纳米 生物 环保
知识产权: 盗版 共享 学人 法规 著作
用户名: 密码: 注册 忘记密码?
    创建新词条
科技百科——欢迎光临全球最大的互联网博物馆
  • 人气指数: 6407 次
  • 编辑次数: 1 次 历史版本
  • 更新时间: 2009-03-18
admin
admin
发短消息
相关词条
数学
数学
数论
数论
工业设计
工业设计
智慧产业
智慧产业
符号位
符号位
算法设计与分析
算法设计与分析
银行家算法
银行家算法
比例计算法
比例计算法
关键路径
关键路径
先来先服务
先来先服务
推荐词条
希拉里二度竞选
希拉里二度竞选
《互联网百科系列》
《互联网百科系列》
《黑客百科》
《黑客百科》
《网络舆情百科》
《网络舆情百科》
《网络治理百科》
《网络治理百科》
《硅谷百科》
《硅谷百科》
桑达尔·皮查伊
桑达尔·皮查伊
阿里双十一成交额
阿里双十一成交额
王健林电商梦
王健林电商梦
陌陌IPO
陌陌IPO
最新词条

热门标签

微博侠 数字营销2011年度总结 政务微博元年 2011微博十大事件 美国十大创业孵化器 盘点美国导师型创业孵化器 盘点导师型创业孵化器 TechStars 智能电视大战前夜 竞争型国企 公益型国企 2011央视经济年度人物 Rhianna Pratchett 莱恩娜·普莱契 Zynga与Facebook关系 Zynga盈利危机 2010年手机社交游戏行业分析报告 游戏奖励 主流手机游戏公司运营表现 主流手机游戏公司运营对比数据 创建游戏原型 正反馈现象 易用性设计增强游戏体验 易用性设计 《The Sims Social》社交亮 心理生理学与游戏 Kixeye Storm8 Storm8公司 女性玩家营销策略 休闲游戏的创新性 游戏运营的数据分析 社交游戏分析学常见术语 游戏运营数据解析 iPad风行美国校园 iPad终结传统教科书 游戏平衡性 成长类型及情感元素 鸿蒙国际 云骗钱 2011年政务微博报告 《2011年政务微博报告》 方正产业图谱 方正改制考 通信企业属公益型国企 善用玩家作弊行为 手机游戏传播 每用户平均收入 ARPU值 ARPU 游戏授权三面观 游戏设计所运用的化学原理 iOS应用人性化界面设计原则 硬核游戏 硬核社交游戏 生物测量法研究玩家 全球移动用户 用户研究三部曲 Tagged转型故事 Tagged Instagram火爆的3大原因 全球第四大社交网络Badoo Badoo 2011年最迅猛的20大创业公司 病毒式传播功能支持的游戏设计 病毒式传播功能 美国社交游戏虚拟商品收益 Flipboard改变阅读 盘点10大最难iPhone游戏 移动应用设计7大主流趋势 成功的设计文件十个要点 游戏设计文件 应用内置付费功能 内置付费功能 IAP功能 IAP IAP模式 游戏易用性测试 生理心理游戏评估 游戏化游戏 全美社交游戏规模 美国社交游戏市场 全球平板电脑出货量 Facebook虚拟商品收益 Facebook全球广告营收 Facebook广告营收 失败游戏设计的数宗罪名 休闲游戏设计要点 玩游戏可提高认知能力 玩游戏与认知能力 全球游戏广告 独立开发者提高工作效率的100个要点 Facebook亚洲用户 免费游戏的10种创收模式 人类大脑可下载 2012年最值得期待的20位硅谷企业家 做空中概股的幕后黑手 做空中概股幕后黑手 苹果2013营收 Playfish社交游戏架构

  

目录

概述编辑本段回目录

 KM算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A顶点Yi的顶标为B,顶点Xi与Yj之间的边权为w【i,j】。在算法执行过程中的任一时刻,对于任一条边(i,j),A+B【j】>=w【i,j】始终成立。

 

定理及思路编辑本段回目录

KM算法的正确性基于以下定理:
  若由二分图中所有满足A+B【j】=w【i,j】的边(i,j)构成的子图(称做相等子图)有完备匹配,那么这个完备匹配就是二分图的最大权匹配。
  这个定理是显然的。因为对于二分图的任意一个匹配,如果它包含于相等子图,那么它的边权和等于所有顶点的顶标和;如果它有的边不包含于相等子图,那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。
  初始时为了使A+B【j】>=w【i,j】恒成立,令A为所有与顶点Xi关联的边的最大权,B【j】=0。如果当前的相等子图没有完备匹配,就按下面的方法修改顶标以使扩大相等子图,直到相等子图具有完备匹配为止。
  我们求当前相等子图的完备匹配失败了,是因为对于某个X顶点,我们找不到一条从它出发的交错路。这时我们获得了一棵交错树,它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d,Y顶点的顶标全都增加同一个值d,那么我们会发现:
两端都在交错树中的边(i,j),A+B【j】的值没有变化。也就是说,它原来属于相等子图,现在仍属于相等子图。
    两端都不在交错树中的边(i,j),A和B【j】都没有变化。也就是说,它原来属于(或不属于)相等子图,现在仍属于(或不属于)相等子图。
X端不在交错树中,Y端在交错树中的边(i,j),它的A+B【j】的值有所增大。它原来不属于相等子图,现在仍不属于相等子图。
    X端在交错树中,Y端不在交错树中的边(i,j),它的A+B【j】的值有所减小。也就说,它原来不属于相等子图,现在可能进入了相等子图,因而使相等子图得到了扩大。
  现在的问题就是求d值了。为了使A+B【j】>=w【i,j】始终成立,且至少有一条边进入相等子图,d应该等于min{A+B【j】-w【i,j】|Xi在交错树中,Yi不在交错树中}。
  以上就是KM算法的基本思路。但是朴素的实现方法,时间复杂度为O(n4)——需要找O(n)次增广路,每次增广最多需要修改O(n)次顶标,每次修改顶标时由于要枚举边来求d值,复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack,每次开始找增广路时初始化为无穷大。在寻找增广路的过程中,检查边(i,j)时,如果它不在相等子图中,则让slack【j】变成原值与A+B【j】-w【i,j】的较小值。这样,在修改顶标时,取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点:修改顶标后,要把所有的slack值都减去d。

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
0

标签: KM算法

收藏到: Favorites  

同义词: 暂无同义词

关于本词条的评论 (共0条)发表评论>>

对词条发表评论

评论长度最大为200个字符。