【摘要】：二部圖的在線匹配問題最早由Karp等人在1990年提出,該問題在近年得到了廣泛的關(guān)注,在日常生活中有大量的應(yīng)用.本文引入了Beta分布作為二部圖節(jié)點(diǎn)間的鄰接關(guān)系的統(tǒng)計(jì)先驗(yàn),提出了最大化節(jié)點(diǎn)的預(yù)留匹配能力準(zhǔn)則作為在線匹配策略的評(píng)價(jià)度量,設(shè)計(jì)了在線匹配算法BetaOM,并證明了該算法的正確性.本文把BetaOM分別應(yīng)用于基于人造數(shù)據(jù)和真實(shí)數(shù)據(jù)的在線匹配問題,實(shí)驗(yàn)的結(jié)果顯示該算法優(yōu)于經(jīng)典的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.
【作者單位】： 華南理工大學(xué)經(jīng)濟(jì)與貿(mào)易學(xué)院;廣州番禺職業(yè)技術(shù)學(xué)院信息工程學(xué)院;
【基金】：國(guó)家自然科學(xué)基金(No.71572058) 廣東省公益研究與能力建設(shè)專項(xiàng)資金(No.2015A030402003) 廣東省哲學(xué)社科基金(No.GD15CGL05) 廣東省自然科學(xué)基金(No.2015A030313807) 中央高�；究蒲袠I(yè)務(wù)費(fèi)(No.2015QNXM20,No.2015ZZ057)
【分類號(hào)】：O213.9

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 馮文麗,原軍;一類度極大的非哈密爾頓簡(jiǎn)單平衡二部圖[J];華北工學(xué)院學(xué)報(bào);2003年05期

2 王秀英,劉春峰;關(guān)于二部圖是可跡的一個(gè)注記[J];吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年03期

3 卞秋香;孫志人;;二部圖的四圈覆蓋[J];江蘇科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年06期

4 劉春峰;佟紹成;;關(guān)于二部圖圈的一個(gè)結(jié)果[J];科學(xué)技術(shù)與工程;2007年08期

5 王洪偉;;二部圖匹配強(qiáng)迫數(shù)的譜[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2009年12期

6 閔安共;;二部圖的兩個(gè)判定方法及性質(zhì)[J];廊坊師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2010年01期

7 喬誠(chéng);王勤;;導(dǎo)出匹配可擴(kuò)二部圖度和條件的改進(jìn)[J];中國(guó)計(jì)量學(xué)院學(xué)報(bào);2010年01期

8 張國(guó)志;王世英;;飽和二部圖[J];晉中學(xué)院學(xué)報(bào);2010年03期

9 王文虎;楊雨;;二部圖的所有極大匹配[J];電腦開發(fā)與應(yīng)用;2011年08期

10 宋曉奎;李秀平;;二部圖的匹配的簡(jiǎn)單應(yīng)用[J];邢臺(tái)學(xué)院學(xué)報(bào);2012年04期

相關(guān)會(huì)議論文 前2條

1 常迎香;;一類無完美匹配的二部圖[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

2 李小強(qiáng);張寧;;基于鄰接矩陣的二部圖的判定方法[A];第五屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文（摘要）匯集[C];2009年

相關(guān)博士學(xué)位論文 前8條

1 成曉燕;關(guān)于一類代數(shù)二部圖的研究[D];揚(yáng)州大學(xué);2015年

2 孫靜;二部圖參數(shù)與圈型結(jié)構(gòu)研究[D];華中師范大學(xué);2014年

3 王洪偉;二部圖的匹配強(qiáng)迫數(shù)[D];蘭州大學(xué);2008年

4 邊紅;圖中的若干極值問題[D];廈門大學(xué);2008年

5 馬麗;素?cái)?shù)冪與2倍素?cái)?shù)冪階局部本原圖[D];云南大學(xué);2012年

6 葉萌;圖張開及其在互極大圖與互極大理想圖中的應(yīng)用[D];上海交通大學(xué);2013年

7 劉賽華;若干圖類的κ-共振問題的研究[D];蘭州大學(xué);2010年

8 呂華眾;圖的條件匹配排除問題的計(jì)算復(fù)雜性和平衡超立方圖的若干網(wǎng)絡(luò)性質(zhì)[D];蘭州大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 王玉玲;匹配的anti-Ramsey數(shù)的若干研究[D];浙江師范大學(xué);2015年

2 鄭連江;圖的關(guān)聯(lián)能量[D];上海大學(xué);2015年

3 沈富強(qiáng);無符號(hào)拉普拉斯特征值的界[D];上海理工大學(xué);2013年

4 楊立保;兩個(gè)二部圖設(shè)計(jì)到其子圖設(shè)計(jì)的變化[D];河北師范大學(xué);2016年

5 鄭延春;二部圖的彩虹匹配問題[D];山東大學(xué);2016年

6 張文琦;均衡二部圖中的2-因子[D];山東理工大學(xué);2010年

7 胡琳;二部圖的列表著色問題[D];新疆大學(xué);2004年

8 楊帆;（3，，4）-雙向正則二部圖的區(qū)間著色[D];華中師范大學(xué);2008年

9 丁立佳;二部圖完美匹配計(jì)數(shù)與禁位排列[D];大連交通大學(xué);2014年

10 馮文麗;關(guān)于二部圖的兩個(gè)結(jié)果[D];山西大學(xué);2005年

本文編號(hào)：2521938