本文選題：受限資源 + 樹(shù)形圖　； 參考：《西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)》2017年08期

【摘要】：資源受限的最小賦權(quán)樹(shù)形圖問(wèn)題(RMWA)是NP-難的,針對(duì)RMWA問(wèn)題給出一種新的貪婪分解啟發(fā)式算法.通過(guò)分解目標(biāo)函數(shù)和約束條件,把RMWA模型分解成一個(gè)最小賦權(quán)樹(shù)形圖問(wèn)題和n個(gè)獨(dú)立的特殊背包問(wèn)題.對(duì)這n個(gè)獨(dú)立的特殊背包問(wèn)題,設(shè)計(jì)貪婪算法求其解,其時(shí)間復(fù)雜度為O(nmlog2m);然后調(diào)整該解使其滿足樹(shù)形圖的約束條件得到RMWA問(wèn)題的一個(gè)可行解,該算法總的復(fù)雜度為O(nm2).最后,給出實(shí)例來(lái)闡述該貪婪分解啟發(fā)式算法.
[Abstract]:The resource-constrained least weighted tree graph problem (RMWA) is NP-difficult. A new greedy decomposition heuristic algorithm is proposed for the RMWA problem. RMWA model is decomposed into a minimum weighted tree graph problem and n independent special knapsack problems by decomposing objective functions and constraints. For these n independent special knapsack problems, a greedy algorithm is designed to find its solution, whose time complexity is O (nmlog2m), and then adjusts the solution to satisfy the constraint condition of tree graph to obtain a feasible solution of the problem. The total complexity of the algorithm is O (nm2). Finally, an example is given to illustrate the greedy decomposition heuristic algorithm.
【作者單位】： 云南大學(xué)旅游文化學(xué)院;云南大學(xué)數(shù)學(xué)系;
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(11126355) 云南省教育廳科學(xué)研究基金項(xiàng)目(2017ZDX270) 云南大學(xué)旅游文化學(xué)院項(xiàng)目(2015XY08)
【分類號(hào)】：O157.6;TP301.6

【相似文獻(xiàn)】

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

1 李詩(shī)珍;;配送中心訂單分批揀貨模型及種籽啟發(fā)式算法[J];起重運(yùn)輸機(jī)械;2009年01期

2 王慶貞;趙雁;鐘斌;王玉龍;;車(chē)輛優(yōu)化調(diào)度算法研究初探[J];黑龍江科技信息;2010年03期

3 王樂(lè)善;_5良震;;求圖的總體最佳2—?jiǎng)澐值挠行l(fā)式算法[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);1983年02期

4 徐亦文;運(yùn)輸路徑問(wèn)題的一個(gè)新啟發(fā)式算法[J];上海機(jī)械學(xué)院學(xué)報(bào);1987年02期

5 郭耀煌,范莉莉;貨運(yùn)汽車(chē)調(diào)度的一種啟發(fā)式算法[J];系統(tǒng)工程;1989年01期

6 陳駐民;羊英;;混流企業(yè)中基于瓶頸的啟發(fā)式算法的應(yīng)用[J];武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版);2010年02期

7 鄭攀;胡思繼;張晨;;機(jī)門(mén)指派模型建立與啟發(fā)式算法設(shè)計(jì)[J];系統(tǒng)工程學(xué)報(bào);2011年01期

8 馬磊;任成磊;韓定定;;模塊度優(yōu)化啟發(fā)式算法應(yīng)用[J];現(xiàn)代電子技術(shù);2012年19期

9 黃干平,劉娟;解“時(shí)間表問(wèn)題”的啟發(fā)式算法[J];武漢大學(xué)學(xué)報(bào)(自然科學(xué)版);1996年01期

10 趙赫,杜端甫;TSP的鄰域搜索算法的分析和改進(jìn)[J];中國(guó)管理科學(xué);1997年01期

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

1 羅守成;唐國(guó)春;;二維集裝箱問(wèn)題的一個(gè)啟發(fā)式算法[A];2001年全國(guó)數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

2 劉青松;孔云峰;黨蘭學(xué);王震;;元啟發(fā)式算法在校車(chē)路徑規(guī)劃中的應(yīng)用[A];第七屆全國(guó)地理學(xué)研究生學(xué)術(shù)年會(huì)論文摘要集[C];2012年

3 劉嘉敏;馬廣煜;黃有群;;基于組合的三維集裝箱裝入啟發(fā)式算法的研究[A];全國(guó)第13屆計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)（CAD/CG）學(xué)術(shù)會(huì)議論文集[C];2004年

4 何正文;徐渝;;多模式項(xiàng)目支付進(jìn)度問(wèn)題的優(yōu)化模型及啟發(fā)式算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

5 趙文丹;汪定偉;郭小萍;王貴成;;網(wǎng)絡(luò)廣告資源優(yōu)化問(wèn)題研究[A];第二十九屆中國(guó)控制會(huì)議論文集[C];2010年

6 楊士準(zhǔn);謝政;陳摯;熊李軍;;k約束QoS問(wèn)題的啟發(fā)式算法[A];中國(guó)通信學(xué)會(huì)第六屆學(xué)術(shù)年會(huì)論文集（下）[C];2009年

7 劉金朋;魏長(zhǎng)江;;啟發(fā)式算法求最短路徑的一種高效率實(shí)現(xiàn)方法[A];2007北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)通信與信息技術(shù)會(huì)議論文集（上冊(cè)）[C];2008年

8 范敏;鄒平;朱興東;;一種啟發(fā)式離散化算法及其Delphi實(shí)現(xiàn)[A];第二屆中國(guó)智能計(jì)算大會(huì)論文集[C];2008年

9 王文瀚;杜斌;朱俊;賈樹(shù)晉;;集成MILP與啟發(fā)式的混合算法求解板坯設(shè)計(jì)問(wèn)題[A];中國(guó)計(jì)量協(xié)會(huì)冶金分會(huì)2012年會(huì)暨能源計(jì)量與節(jié)能降耗經(jīng)驗(yàn)交流會(huì)論文集[C];2012年

10 馮德鴻;唐加福;郭琦;李輝;;訂貨批量問(wèn)題改進(jìn)的相關(guān)策略啟發(fā)式算法與仿真分析[A];2007系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2007年

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

1 李福清;交通規(guī)劃中專用道設(shè)置問(wèn)題建模和求解研究[D];廣東工業(yè)大學(xué);2016年

2 賴向京;原子團(tuán)簇結(jié)構(gòu)預(yù)測(cè)的現(xiàn)實(shí)途徑—高性能啟發(fā)式算法[D];華中科技大學(xué);2012年

3 黎展滔;具有成組約束的柔性流水車(chē)間作業(yè)計(jì)劃制定的啟發(fā)式算法[D];廣東工業(yè)大學(xué);2012年

4 曹斌;生物啟發(fā)式智能計(jì)算及其應(yīng)用的研究[D];吉林大學(xué);2012年

5 董興業(yè);啟發(fā)式算法及其在同順序流水作業(yè)問(wèn)題中的應(yīng)用[D];北京交通大學(xué);2008年

6 古繼興;KOD多播技術(shù)與Steiner樹(shù)啟發(fā)式算法[D];上海交通大學(xué);2007年

7 胡大偉;設(shè)施定位和車(chē)輛路線問(wèn)題模型及其啟發(fā)式算法研究[D];長(zhǎng)安大學(xué);2008年

8 楊玉珍;基于元啟發(fā)式算法的帶生產(chǎn)約束作業(yè)車(chē)間調(diào)度問(wèn)題若干研究[D];華東理工大學(xué);2014年

9 任志磊;組合優(yōu)化問(wèn)題的特化與泛化算法設(shè)計(jì)[D];大連理工大學(xué);2013年

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

1 朱璽睿;氯氧鎂板材生產(chǎn)線優(yōu)化研究[D];東北林業(yè)大學(xué);2015年

2 尹青山;綠色微數(shù)據(jù)中心與NGPON融合網(wǎng)絡(luò)部署規(guī)劃研究[D];大連海事大學(xué);2015年

3 石闖;基于啟發(fā)式算法的Ad Hoc網(wǎng)絡(luò)QoS路由協(xié)議的研究與仿真[D];東北大學(xué);2013年

4 張毅;啟發(fā)式算法的自調(diào)參數(shù)方法研究[D];西安工程大學(xué);2016年

5 周書(shū)橙;護(hù)士排班的啟發(fā)式算法研究與排班管理系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)[D];北京交通大學(xué);2016年

6 任平飛;基于啟發(fā)式算法的云計(jì)算負(fù)載均衡問(wèn)題研究[D];哈爾濱工業(yè)大學(xué);2016年

7 戈麗娜（Galina Deeva）;配送過(guò)程中提貨送貨問(wèn)題的靜態(tài)動(dòng)態(tài)方法的應(yīng)用效果研究[D];哈爾濱工業(yè)大學(xué);2016年

8 劉賽賽;基于增強(qiáng)學(xué)習(xí)的啟發(fā)式和元啟發(fā)式搜索的參數(shù)調(diào)優(yōu)策略[D];電子科技大學(xué);2016年

9 李鵬;定制衣柜零件分揀方式及效能分析[D];南京林業(yè)大學(xué);2016年

10 劉志宏;合同組批系統(tǒng)中優(yōu)化算法的研究[D];東北大學(xué);2013年

，

本文編號(hào)：2064222