Beta在线匹配

发布时间：2019-08-01 19:01

【摘要】：二部图的在线匹配问题最早由Karp等人在1990年提出,该问题在近年得到了广泛的关注,在日常生活中有大量的应用.本文引入了Beta分布作为二部图节点间的邻接关系的统计先验,提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量,设计了在线匹配算法BetaOM,并证明了该算法的正确性.本文把BetaOM分别应用于基于人造数据和真实数据的在线匹配问题,实验的结果显示该算法优于经典的Greedy算法和Ranking算法.
[Abstract]:The online matching problem of bipartite graph was first put forward by Karp et al in 1990. This problem has been widely concerned in recent years and has a lot of applications in daily life. In this paper, Beta distribution is introduced as the statistical priori of the adjacent relationship between bipartite graph nodes, and the criterion of maximizing the reserved matching ability of nodes is proposed as the evaluation measure of online matching strategy. The online matching algorithm BetaOM, is designed and the correctness of the algorithm is proved. In this paper, BetaOM is applied to the online matching problem based on artificial data and real data, respectively. the experimental results show that the algorithm is superior to the classical Greedy algorithm and Ranking algorithm.
【作者单位】： 华南理工大学经济与贸易学院;广州番禺职业技术学院信息工程学院;
【基金】：国家自然科学基金(No.71572058) 广东省公益研究与能力建设专项资金(No.2015A030402003) 广东省哲学社科基金(No.GD15CGL05) 广东省自然科学基金(No.2015A030313807) 中央高校基本科研业务费(No.2015QNXM20,No.2015ZZ057)
【分类号】：O213.9

【相似文献】

相关期刊论文 前10条

1 冯文丽,原军;一类度极大的非哈密尔顿简单平衡二部图[J];华北工学院学报;2003年05期

2 王秀英,刘春峰;关于二部图是可迹的一个注记[J];吉林师范大学学报(自然科学版);2005年03期

3 卞秋香;孙志人;;二部图的四圈覆盖[J];江苏科技大学学报(自然科学版);2005年06期

4 刘春峰;佟绍成;;关于二部图圈的一个结果[J];科学技术与工程;2007年08期

5 王洪伟;;二部图匹配强迫数的谱[J];山东大学学报(理学版);2009年12期

6 闵安共;;二部图的两个判定方法及性质[J];廊坊师范学院学报(自然科学版);2010年01期

7 乔诚;王勤;;导出匹配可扩二部图度和条件的改进[J];中国计量学院学报;2010年01期

8 张国志;王世英;;饱和二部图[J];晋中学院学报;2010年03期

9 王文虎;杨雨;;二部图的所有极大匹配[J];电脑开发与应用;2011年08期

10 宋晓奎;李秀平;;二部图的匹配的简单应用[J];邢台学院学报;2012年04期

相关会议论文 前2条

1 常迎香;;一类无完美匹配的二部图[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 李小强;张宁;;基于邻接矩阵的二部图的判定方法[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

相关博士学位论文 前8条

1 成晓燕;关于一类代数二部图的研究[D];扬州大学;2015年

2 孙静;二部图参数与圈型结构研究[D];华中师范大学;2014年

3 王洪伟;二部图的匹配强迫数[D];兰州大学;2008年

4 边红;图中的若干极值问题[D];厦门大学;2008年

5 马丽;素数幂与2倍素数幂阶局部本原图[D];云南大学;2012年

6 叶萌;图张开及其在互极大图与互极大理想图中的应用[D];上海交通大学;2013年

7 刘赛华;若干图类的κ-共振问题的研究[D];兰州大学;2010年

8 吕华众;图的条件匹配排除问题的计算复杂性和平衡超立方图的若干网络性质[D];兰州大学;2013年

相关硕士学位论文 前10条

1 王玉玲;匹配的anti-Ramsey数的若干研究[D];浙江师范大学;2015年

2 郑连江;图的关联能量[D];上海大学;2015年

3 沈富强;无符号拉普拉斯特征值的界[D];上海理工大学;2013年

4 杨立保;两个二部图设计到其子图设计的变化[D];河北师范大学;2016年

5 郑延春;二部图的彩虹匹配问题[D];山东大学;2016年

6 张文琦;均衡二部图中的2-因子[D];山东理工大学;2010年

7 胡琳;二部图的列表着色问题[D];新疆大学;2004年

8 杨帆;（3，，4）-双向正则二部图的区间着色[D];华中师范大学;2008年

9 丁立佳;二部图完美匹配计数与禁位排列[D];大连交通大学;2014年

10 冯文丽;关于二部图的两个结果[D];山西大学;2005年

本文编号：2521938