本文關(guān)鍵詞：從邊界未知的危險區(qū)域中快速撤離的算法研究

  更多相關(guān)文章： 計(jì)算幾何 Online問題 撤離策略 競爭比

【摘要】：從邊界未知的危險區(qū)域中快速撤離問題的研究,是從很多實(shí)際應(yīng)用問題中抽象出來的一個理論課題,在一定的約定條件下,研究受災(zāi)人員如何從邊界未知的危險區(qū)域中快速撤離的撤離策略,可為解決一些實(shí)際應(yīng)用問題提供技術(shù)支撐。因此,本課題的研究,不僅具有重要的理論意義,而且還具有較高的實(shí)用價值。本文針對從邊界未知的危險區(qū)域中快速撤離的策略進(jìn)行研究,包括單源點(diǎn)問題和多源點(diǎn)問題。為此,首先論述了問題求解過程中所涉及的計(jì)算幾何學(xué)的相關(guān)基礎(chǔ)知識,如判斷某點(diǎn)是否在線段上、構(gòu)造平面點(diǎn)集的凸包等,并對競爭比、凸包,以及構(gòu)造凸包的格雷厄姆方法等,作了較為詳細(xì)的論述。在此基礎(chǔ)上,論述了單源點(diǎn)問題及其相關(guān)撤離策略,并對等角策略的基本原理、執(zhí)行過程以及競爭比等,做了較為詳細(xì)的分析,提出了改進(jìn)的單源點(diǎn)問題撤離策略。對比分析了多源點(diǎn)問題與單源點(diǎn)問題的問題特征,基于單源點(diǎn)問題的等角撤離策略,結(jié)合多源點(diǎn)問題的問題特征,進(jìn)一步提出了多源點(diǎn)問題的等角撤離策略,并對撤離策略的競爭比做了較為詳盡的理論分析,給出了競爭比不超過4(?)2的研究結(jié)果。最后,針對所設(shè)計(jì)的算法,構(gòu)造測試數(shù)據(jù)并運(yùn)行所實(shí)現(xiàn)的程序,驗(yàn)證了算法的可行性與有效性。實(shí)驗(yàn)結(jié)果表明,本文提出的針對單源點(diǎn)問題和多源點(diǎn)問題的撤離策略,能夠有效地解決單源點(diǎn)問題和多源點(diǎn)問題,關(guān)于競爭比的實(shí)驗(yàn)結(jié)果與理論分析結(jié)果比較一致,且可保障所有受災(zāi)人員安全地撤離出危險區(qū)域。因此,本文所提出的解決單源點(diǎn)問題和多源點(diǎn)問題的算法是切實(shí)可行、有效的。
【關(guān)鍵詞】：計(jì)算幾何 Online問題 撤離策略 競爭比
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：X4;TP301.6
【目錄】：

• 摘要5-6
• Abstract6-9
• 第1章 緒論9-15
• 1.1 研究背景與意義9-10
• 1.2 國內(nèi)外研究現(xiàn)狀10-12
• 1.3 研究內(nèi)容12-13
• 1.4 論文的組織結(jié)構(gòu)13-15
• 第2章 相關(guān)基礎(chǔ)知識15-26
• 2.0 計(jì)算幾何學(xué)概述15-16
• 2.1 基本定義16-18
• 2.2 經(jīng)典問題及算法18-25
• 2.2.1 基礎(chǔ)算法18-21
• 2.2.2 直線搜索問題及其求解算法21-22
• 2.2.3 計(jì)算平面點(diǎn)集凸包的算法22-25
• 2.3 本章小結(jié)25-26
• 第3章 單源點(diǎn)問題及其求解算法26-40
• 3.1 單源點(diǎn)問題的描述26-27
• 3.2 撤離策略27-39
• 3.2.1 等角撤離策略27-29
• 3.2.2 等角撤離策略競爭比分析29-37
• 3.2.3 等角撤離策略的改進(jìn)及競爭比分析37-39
• 3.3 本章小結(jié)39-40
• 第4章 多源點(diǎn)問題及其求解算法40-54
• 4.1 多源點(diǎn)問題的描述40-41
• 4.2 單源點(diǎn)與多源點(diǎn)問題的對比分析41-42
• 4.3 撤離策略42-46
• 4.4 競爭比分析46-53
• 4.4.1 Online算法的成本D_(online)47-48
• 4.4.2 Offline算法的成本D_(offline)48-53
• 4.5 本章小結(jié)53-54
• 第5章 算法有效性驗(yàn)證54-59
• 5.1 單源點(diǎn)問題實(shí)驗(yàn)結(jié)果及其分析54-56
• 5.2 多源點(diǎn)問題實(shí)驗(yàn)結(jié)果及其分析56-59
• 第6章 總結(jié)與展望59-61
• 6.1 論文工作總結(jié)59-60
• 6.2 進(jìn)一步研究工作60-61
• 參考文獻(xiàn)61-64
• 致謝64-65
• 研究生履歷65

【參考文獻(xiàn)】

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

1 鄧禮禮;求圖中受限制的所有最短路徑算法的分析與研究[D];華東師范大學(xué);2009年

，

本文編號：711791