24805.基于網(wǎng)絡(luò)拓?fù)浞治龅姆謱右?guī)劃算法研究

1、分類號密級UDC編號碩士學(xué)位論文基于網(wǎng)絡(luò)拓?fù)浞治龅姆謱右?guī)劃算法研究基于網(wǎng)絡(luò)拓?fù)浞治龅姆謱右?guī)劃算法研究學(xué)位申請人：人：李夢楊指導(dǎo)教師：師：楊宗霄教授學(xué)科專業(yè)：業(yè)：應(yīng)用數(shù)學(xué)學(xué)位類別：別：理學(xué)2014年4月摘要I論文題目：論文題目：基于網(wǎng)絡(luò)拓?fù)浞治龅姆謱右?guī)劃算法研究基于網(wǎng)絡(luò)拓?fù)浞治龅姆謱右?guī)劃算法研究專業(yè)：業(yè)：應(yīng)用數(shù)學(xué)應(yīng)用數(shù)學(xué)研究生：生：李夢楊李夢楊指導(dǎo)教師：指導(dǎo)教師：楊宗霄教授楊宗霄教授摘要作為運(yùn)籌學(xué)優(yōu)化理論的一個(gè)重要研究方向，全局最短路徑規(guī)

2、劃即最小Steiner樹問題已經(jīng)成為管理科學(xué)與工程學(xué)的研究熱點(diǎn)，如何實(shí)現(xiàn)有效資源的節(jié)約成本是我國實(shí)施構(gòu)建節(jié)約型社會(huì)必須優(yōu)先考慮的重大課題。其中系統(tǒng)內(nèi)部輔助節(jié)點(diǎn)的客觀位置和數(shù)目的確定是當(dāng)前的主要技術(shù)瓶頸，如何解決此類問題已成為該領(lǐng)域的一個(gè)研究熱點(diǎn)和發(fā)展趨勢。本文首先介紹了一種全新的可視化試驗(yàn)方法從物理試驗(yàn)入手，對數(shù)學(xué)上難以解決的全局路徑規(guī)劃問題進(jìn)行建模，利用溶液泡膜的物理特性構(gòu)造最小Steiner樹的可視化薄膜軌跡。但隨著應(yīng)用需求和信息技

3、術(shù)的發(fā)展，鑒于最短路徑可視化試驗(yàn)裝置應(yīng)用于大規(guī)模圖數(shù)據(jù)規(guī)劃中的效率不高，形成路徑不穩(wěn)定。本文在可視化試驗(yàn)方法的基礎(chǔ)上提出了基于網(wǎng)絡(luò)拓?fù)浞治龅姆謱右?guī)劃算法。分層算法充分利用了人類對路徑搜索過程的認(rèn)知，對于遠(yuǎn)距離路徑規(guī)劃的優(yōu)化能力，引入了“分而治之”的策略，通過劃分空間層次來提高算法效率。分層算法的構(gòu)建主要包括分層網(wǎng)絡(luò)的定義、分層抽象和層次拓?fù)潢P(guān)系的形成。其思想來源于地理學(xué)的空間層次推理理論和圖論的子圖劃分理論；其核心是通過Delaunay

4、三角剖分對n節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行層次劃分；對每一層構(gòu)造滿Steiner樹，最終通過連接各個(gè)子層的滿Steiner樹來構(gòu)造整體全局的最小Steiner樹。以彌補(bǔ)當(dāng)給定點(diǎn)數(shù)增多時(shí)試驗(yàn)形成薄膜路徑困難的不足之處，達(dá)到快速的系統(tǒng)路徑規(guī)劃能力。本文首先通過簡單的算法實(shí)例闡述了該方法的可行性；然后進(jìn)一步通過工程實(shí)例得到的分層算法優(yōu)化數(shù)據(jù)分別與最小生成樹的試驗(yàn)數(shù)據(jù)和可視化試驗(yàn)的試驗(yàn)數(shù)據(jù)，三種數(shù)據(jù)進(jìn)行對比分析；既驗(yàn)證了該算法的正確性，又進(jìn)一步說明了該算法的可行