本文關(guān)鍵詞：兩個守衛(wèi)問題的最優(yōu)掃描算法研究與實現(xiàn)，由筆耕文化傳播整理發(fā)布。

【摘要】：Two-guard問題是計算幾何學領(lǐng)域的熱點問題,研究該問題,不僅涉及到求解多邊形的可視性、Frechet距離、最短路徑等理論問題的技術(shù)方法與研究成果,而且由于Two-guard問題也是很多實際應用問題的抽象模型使得該問題的研究具有很好的實際應用背景,因此,研究該問題,不僅具有理論意義,而且具有很大的實際應用價值。本文在論述畫廊問題、Frechet距離問題、簡單多邊形及其可視性、min-sum與min-max量度標準及含義的基礎(chǔ)上,對兩個守衛(wèi)可掃描簡單多邊形的幾何結(jié)構(gòu)極其特性,做了較為深入的研究,分析了可掃描簡單多邊形的直掃描和反掃描的掃描方式、掃描規(guī)則及其掃描方案的構(gòu)成,詳細論述了min-sum度量標準下的掃描規(guī)則與射線段圖與min-max度量下的關(guān)鍵掃描線段與原子掃描圖的構(gòu)造過程與構(gòu)造技術(shù),運用圖論的技術(shù)方法,將幾何搜索問題轉(zhuǎn)化為圖的遍歷問題,分別設(shè)計出了時間復雜度為O(n2)的min-sum度量標準下的最優(yōu)搜索策略和min-max度量標準下的最優(yōu)搜索策略。針對所設(shè)計的掃描策略,設(shè)計出了合理的數(shù)據(jù)結(jié)構(gòu)并編程加以實現(xiàn),給出了算法運行的可視化結(jié)果及其分析。實現(xiàn)結(jié)果表明,本文所提出的搜索策略是切實可行的解決方案。
【關(guān)鍵詞】：兩個守衛(wèi)問題 min-sum度量 min-max度量 射線段圖 原子掃描圖
【學位授予單位】：大連海事大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP391.41;O18
【目錄】：

• 摘要5-6
• ABSTRACT6-9
• 第1章 緒論9-16
• 1.1 研究背景及意義9-11
• 1.2 國內(nèi)外研究現(xiàn)狀概述11-14
• 1.3 主要研究內(nèi)容14
• 1.4 論文的組織結(jié)構(gòu)14-16
• 第2章 兩個守衛(wèi)問題的相關(guān)理論基礎(chǔ)16-27
• 2.1 Two-guard問題的一般描述16-17
• 2.2 Two-guard問題的相關(guān)基礎(chǔ)17-24
• 2.2.1 計算幾何學概述17-18
• 2.2.2 基本概念定義18-23
• 2.2.3 掃描簡單多邊形23-24
• 2.3 Frechet距離問題24-25
• 2.4 Two-guard問題的最優(yōu)度量標準25-27
• 2.4.1 min-sum度量標準25
• 2.4.2 min-max度量標準25-27
• 第3章 基于min-sum度量標準的最優(yōu)搜索算法27-39
• 3.1 相關(guān)基礎(chǔ)27
• 3.2 掃描操作分析27-30
• 3.2.1 直掃描分析27-29
• 3.2.2 反掃描分析29-30
• 3.3 Min-sum問題的算法構(gòu)造30-39
• 3.3.1 射線段圖的構(gòu)造31
• 3.3.2 弧的權(quán)重31-32
• 3.3.3 算法流程32-36
• 3.3.4 算法偽代碼描述36-39
• 第4章 基于min-max度量標準的最優(yōu)搜索算法39-52
• 4.1 相關(guān)基礎(chǔ)39-41
• 4.2 掃描操作分析41-44
• 4.2.1 直掃描分析41-42
• 4.2.2 反掃描分析42-44
• 4.2.3 一般掃描分析44
• 4.3 Min-max問題的算法構(gòu)造44-52
• 4.3.1 原子掃描圖的構(gòu)造44-45
• 4.3.2 弧的權(quán)重45-46
• 4.3.3 算法流程46-50
• 4.3.4 算法偽代碼描述50-52
• 第5章 算法實現(xiàn)及其結(jié)果分析52-62
• 5.1 基本數(shù)據(jù)結(jié)構(gòu)52-55
• 5.2 測試數(shù)據(jù)的構(gòu)造55-56
• 5.3 測試結(jié)果分析56-60
• 5.3.1 min-sum問題的測試結(jié)果分析56-58
• 5.3.2 min-max問題的測試結(jié)果分析58-60
• 5.4 時間復雜度分析60-62
• 5.4.1 Min-sum問題的算法復雜度分析60-61
• 5.4.2 Min-max問題的算法復雜度分析61-62
• 第6章 總結(jié)與展望62-64
• 6.1 論文工作總結(jié)62
• 6.2 進一步的研究工作62-64
• 參考文獻64-68
• 攻讀學位期間公開發(fā)表論文68-69
• 致謝69

【相似文獻】

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

1 胡國棟;李旭東;胡金喜;;一種判定簡單多邊形可視頂點的算法[J];甘肅科技;2007年10期

2 宋曉眉;程昌秀;周成虎;;簡單多邊形頂點凹凸性判斷算法綜述[J];國土資源遙感;2011年03期

3 胡國棟;李旭東;胡金喜;;簡單多邊形凸凹頂點的識別[J];甘肅科技;2007年08期

4 周文科;一種簡單多邊形凸包的快速算法及程序設(shè)計[J];廣州大學學報(自然科學版);2003年06期

5 曲吉林,楊洪萬;平面內(nèi)任意一組簡單多邊形的可見性[J];山東師大學報(自然科學版);2000年02期

6 宋立明;閆浩文;王邦松;方愛玲;;兩個簡單多邊形求交的算法[J];測繪與空間地理信息;2011年06期

7 崔先國;毛定山;;簡單多邊形間最大距離的求解算法[J];測繪科學;2008年06期

8 劉國棟;;整點多邊形[J];惠陽師專學報(自然科學版);1991年03期

9 徐嘉;;二面體群作用下簡單多邊形的分類[J];計算機輔助設(shè)計與圖形學學報;2012年07期

10 王相海;制定點是否包容于簡單多邊形中的一個三角剖分方法[J];松遼學刊(自然科學版);1995年02期

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

1 劉建東;環(huán)形走廊中1-searcher搜索問題的算法研究[D];大連海事大學;2016年

2 劉元;兩個守衛(wèi)問題的最優(yōu)掃描算法研究與實現(xiàn)[D];大連海事大學;2016年

3 馬永卓;簡單多邊形構(gòu)造方法研究[D];南昌航空大學;2013年

4 韓冰;簡單多邊形內(nèi)LR可視問題的求解算法研究[D];大連海事大學;2011年

5 李玉娟;簡單多邊形中兩個守衛(wèi)的min-sum算法研究[D];大連海事大學;2011年

6 周志峰;簡單多邊形中兩個守衛(wèi)的max-min算法研究[D];大連海事大學;2012年

7 郭佳;可掃描簡單多邊形中兩守衛(wèi)間min-max距離求解研究[D];大連海事大學;2013年

8 湯立東;計算幾何中LR可視化問題研究[D];大連海事大學;2010年

9 何雨靜;Link-2可視多邊形中三守衛(wèi)問題的求解算法研究[D];大連海事大學;2014年

10 李麗;多邊形搜索的幾種策略研究[D];蘭州理工大學;2011年

  本文關(guān)鍵詞：兩個守衛(wèi)問題的最優(yōu)掃描算法研究與實現(xiàn)，，由筆耕文化傳播整理發(fā)布。

本文編號：366462