本文關(guān)鍵詞：最大流問(wèn)題及歐幾里德Steiner樹問(wèn)題初探　出處：《青海師范大學(xué)》2016年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 增廣路算法 最短增廣路 Steiner最小樹 Steiner點(diǎn)

【摘要】：最大流問(wèn)題及歐幾里德Steiner樹問(wèn)題都是運(yùn)籌學(xué)領(lǐng)域取得迅速發(fā)展的理論,無(wú)論從理論上還是實(shí)際應(yīng)用中,它們的建立和求解算法的不斷改進(jìn)為解決很多實(shí)際問(wèn)題提供了十分重要的工具.除了用于具體的數(shù)學(xué)問(wèn)題的優(yōu)化外,它們還在工程計(jì)算機(jī)原理、通信系統(tǒng)、應(yīng)用數(shù)學(xué)、社會(huì)以及軍事等實(shí)際領(lǐng)域方面有著廣泛的應(yīng)用.它們都是組合優(yōu)化中的一個(gè)NP難解問(wèn)題,難求解是該問(wèn)題的固有屬性,雖然對(duì)于最大流問(wèn)題及歐幾里德Steiner樹問(wèn)題研究已經(jīng)持續(xù)了幾十年,該類問(wèn)題的研究進(jìn)展已經(jīng)得到很大的提高,但是它們的研究還有很大的空間去探索.本文具體內(nèi)容包括:第一章闡述最大流問(wèn)題及歐幾里德Steiner樹問(wèn)題的研究進(jìn)展、應(yīng)用背景以及研究意義.第二章概述最大流問(wèn)題的研究、經(jīng)典增廣路算法、算法進(jìn)展以及算法時(shí)間復(fù)雜度,并對(duì)最短路增廣路算法改進(jìn)最大流問(wèn)題的證明進(jìn)行了補(bǔ)充修正.第三章介紹Steiner樹問(wèn)題、算法研究現(xiàn)狀,重點(diǎn)討論歐幾里德Steiner樹問(wèn)題.概述歐幾里德Steiner最小樹的性質(zhì)以及構(gòu)造Steiner樹的復(fù)雜性,并討論證明歐式平面內(nèi)三個(gè)點(diǎn)、四個(gè)點(diǎn)、五個(gè)點(diǎn)的Steiner最小樹的構(gòu)造情況.第四章對(duì)本文內(nèi)容進(jìn)行總結(jié),給出問(wèn)題研究的難點(diǎn)與期望.
【學(xué)位授予單位】：青海師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O224

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 曹翠珍;最大流問(wèn)題與突發(fā)事件的應(yīng)對(duì)[J];科技進(jìn)步與對(duì)策;2004年09期

2 凌永發(fā);王杰;李正明;;網(wǎng)絡(luò)最大流問(wèn)題典型組合算法研究[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

3 張豐;羅罕勛;;一類網(wǎng)絡(luò)最大流問(wèn)題的簡(jiǎn)便算法[J];中國(guó)科技信息;2009年07期

4 朱永津,田豐,馬仲蕃,蔡茂誠(chéng);網(wǎng)絡(luò)上兩類物資聯(lián)合最大流問(wèn)題的極流特征[J];中國(guó)科學(xué);1974年06期

5 周玉濤;;基于層次網(wǎng)絡(luò)的最大流問(wèn)題研究[J];科技廣場(chǎng);2008年01期

6 柴麗琴;王紅昌;;網(wǎng)絡(luò)最大流問(wèn)題應(yīng)用實(shí)例研究[J];全國(guó)商情(理論研究);2013年17期

7 張遠(yuǎn)福,葉正道,唐靜波;一個(gè)制造網(wǎng)絡(luò)的最大流算法[J];工程數(shù)學(xué)學(xué)報(bào);2005年05期

8 毛華;毛曉亮;李斌;;網(wǎng)絡(luò)最大流部分割矩陣算法[J];計(jì)算機(jī)科學(xué);2011年12期

9 周隆盛;;計(jì)算機(jī)用‘自學(xué)習(xí)’算法求解網(wǎng)絡(luò)最大流問(wèn)題[J];鄭州大學(xué)學(xué)報(bào)(自然科學(xué)版);1986年01期

10 蓋宇仙;李方豫;頡棟棟;;一類流量增減最大值可預(yù)見(jiàn)的不確定網(wǎng)絡(luò)最大流的模型與算法[J];蘭州交通大學(xué)學(xué)報(bào);2007年04期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前2條

1 劉文濤;張群;陳子毅;;基于網(wǎng)絡(luò)最大流的瓶頸分析[A];管理科學(xué)與系統(tǒng)科學(xué)研究新進(jìn)展——第8屆全國(guó)青年管理科學(xué)與系統(tǒng)科學(xué)學(xué)術(shù)會(huì)議論文集[C];2005年

2 史新生;董志強(qiáng);方志耕;;應(yīng)用邏輯割樹模型求解模糊可靠條件下的網(wǎng)絡(luò)最大流問(wèn)題研究[A];面向復(fù)雜系統(tǒng)的管理理論與信息系統(tǒng)技術(shù)學(xué)術(shù)會(huì)議專輯[C];2000年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 杜政均;一種新的最大流算法的研究[D];電子科技大學(xué);2015年

2 刁強(qiáng)強(qiáng);最大流問(wèn)題及歐幾里德Steiner樹問(wèn)題初探[D];青海師范大學(xué);2016年

3 許顯勝;快速求解大規(guī)模網(wǎng)絡(luò)最大流問(wèn)題的研究[D];安徽大學(xué);2013年

4 景虹;最大流算法的仿真與分析[D];華中科技大學(xué);2009年

5 周廣露;不確定圖上的最大流研究[D];哈爾濱工業(yè)大學(xué);2014年

6 郭玉芬;網(wǎng)絡(luò)最大流及回收中心選址問(wèn)題研究[D];湖南大學(xué);2008年

7 孟曉婉;網(wǎng)絡(luò)最大流算法與應(yīng)用研究[D];南京郵電大學(xué);2013年

8 陳靜;容差修正網(wǎng)絡(luò)最大流算法研究[D];燕山大學(xué);2009年

9 李天南;基于最大流的車輛容遲網(wǎng)絡(luò)路由算法研究[D];上海交通大學(xué);2011年

10 蘇建忠;基于粒化思想求解大規(guī)模網(wǎng)絡(luò)最大流的研究[D];安徽大學(xué);2014年

，

本文編號(hào)：1307969