從邊界未知的危險區(qū)域中快速撤離的算法研究.pdf

1、從邊界未知的危險區(qū)域中快速撤離問題的研究，是從很多實際應(yīng)用問題中抽象出來的一個理論課題，在一定的約定條件下，研究受災人員如何從邊界未知的危險區(qū)域中快速撤離的撤離策略，可為解決一些實際應(yīng)用問題提供技術(shù)支撐。因此，本課題的研究，不僅具有重要的理論意義，而且還具有較高的實用價值。
　　本文針對從邊界未知的危險區(qū)域中快速撤離的策略進行研究，包括單源點問題和多源點問題。為此，首先論述了問題求解過程中所涉及的計算幾何學的相關(guān)基礎(chǔ)知識，如判斷某

2、點是否在線段上、構(gòu)造平面點集的凸包等，并對競爭比、凸包，以及構(gòu)造凸包的格雷厄姆方法等，作了較為詳細的論述。在此基礎(chǔ)上，論述了單源點問題及其相關(guān)撤離策略，并對等角策略的基本原理、執(zhí)行過程以及競爭比等，做了較為詳細的分析，提出了改進的單源點問題撤離策略。對比分析了多源點問題與單源點問題的問題特征，基于單源點問題的等角撤離策略，結(jié)合多源點問題的問題特征，進一步提出了多源點問題的等角撤離策略，并對撤離策略的競爭比做了較為詳盡的理論分析，給出了競