1、分類號密級UDC編號碩士學位論文基于網絡拓撲分析的分層規(guī)劃算法研究基于網絡拓撲分析的分層規(guī)劃算法研究學位申請人：人：李夢楊指導教師：師：楊宗霄教授學科專業(yè)：業(yè)：應用數學學位類別：別：理學2014年4月摘要I論文題目：論文題目：基于網絡拓撲分析的分層規(guī)劃算法研究基于網絡拓撲分析的分層規(guī)劃算法研究專業(yè)：業(yè)：應用數學應用數學研究生：生：李夢楊李夢楊指導教師：指導教師：楊宗霄教授楊宗霄教授摘要作為運籌學優(yōu)化理論的一個重要研究方向，全局最短路徑規(guī)

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

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

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