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

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

• 摘要5-6
• ABSTRACT6-9
• 第1章 緒論9-16
• 1.1 研究背景及意義9-11
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀概述11-14
• 1.3 主要研究?jī)?nèi)容14
• 1.4 論文的組織結(jié)構(gòu)14-16
• 第2章 兩個(gè)守衛(wèi)問(wèn)題的相關(guān)理論基礎(chǔ)16-27
• 2.1 Two-guard問(wèn)題的一般描述16-17
• 2.2 Two-guard問(wèn)題的相關(guān)基礎(chǔ)17-24
• 2.2.1 計(jì)算幾何學(xué)概述17-18
• 2.2.2 基本概念定義18-23
• 2.2.3 掃描簡(jiǎn)單多邊形23-24
• 2.3 Frechet距離問(wèn)題24-25
• 2.4 Two-guard問(wèn)題的最優(yōu)度量標(biāo)準(zhǔn)25-27
• 2.4.1 min-sum度量標(biāo)準(zhǔn)25
• 2.4.2 min-max度量標(biāo)準(zhǔn)25-27
• 第3章 基于min-sum度量標(biāo)準(zhǔn)的最優(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問(wèn)題的算法構(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度量標(biāo)準(zhǔn)的最優(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問(wèn)題的算法構(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章 算法實(shí)現(xiàn)及其結(jié)果分析52-62
• 5.1 基本數(shù)據(jù)結(jié)構(gòu)52-55
• 5.2 測(cè)試數(shù)據(jù)的構(gòu)造55-56
• 5.3 測(cè)試結(jié)果分析56-60
• 5.3.1 min-sum問(wèn)題的測(cè)試結(jié)果分析56-58
• 5.3.2 min-max問(wèn)題的測(cè)試結(jié)果分析58-60
• 5.4 時(shí)間復(fù)雜度分析60-62
• 5.4.1 Min-sum問(wèn)題的算法復(fù)雜度分析60-61
• 5.4.2 Min-max問(wèn)題的算法復(fù)雜度分析61-62
• 第6章 總結(jié)與展望62-64
• 6.1 論文工作總結(jié)62
• 6.2 進(jìn)一步的研究工作62-64
• 參考文獻(xiàn)64-68
• 攻讀學(xué)位期間公開(kāi)發(fā)表論文68-69
• 致謝69

【相似文獻(xiàn)】

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

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

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

3 胡國(guó)棟;李旭東;胡金喜;;簡(jiǎn)單多邊形凸凹頂點(diǎn)的識(shí)別[J];甘肅科技;2007年08期

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

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

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

7 崔先國(guó);毛定山;;簡(jiǎn)單多邊形間最大距離的求解算法[J];測(cè)繪科學(xué);2008年06期

8 劉國(guó)棟;;整點(diǎn)多邊形[J];惠陽(yáng)師專學(xué)報(bào)(自然科學(xué)版);1991年03期

9 徐嘉;;二面體群作用下簡(jiǎn)單多邊形的分類[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2012年07期

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

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

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

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

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

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

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

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

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

8 湯立東;計(jì)算幾何中LR可視化問(wèn)題研究[D];大連海事大學(xué);2010年

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

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

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

本文編號(hào)：366462