平面上成組疏散的Online搜索算法研究.pdf

1、平面上成組疏散的Online搜索問題的求解研究，不僅涉及計算幾何、圖論、組合優(yōu)化等技術(shù)方法，而且是解決很多實際應用問題的基礎(chǔ)，所以針對該問題的研究，不僅具有理論意義，而且具有較高的實際應用價值。
　　本文針對邊界信息未知的單源點疏散問題中分組數(shù)為n(n≥2）的快速疏散策略進行研究，首先分析了用于問題求解的相關(guān)基礎(chǔ)知識及概念，如判斷點在直線上、判斷點是否在多邊形內(nèi)、競爭比的計算等，然后對直線上探索問題的雙倍策略、單源點與多源點的成組

2、等角疏散策略、單源點半圓疏散策略等已有研究結(jié)果進行了較為詳細的分析，指出了其中存在的不足。在此基礎(chǔ)上，針對分組數(shù)為2的單源點疏散問題，應用半圓疏散策略，設(shè)計出了相應的求解算法，并拓展應用到分組數(shù)為n(n≥3）的情形，設(shè)計出了相應的成組扇形疏散策略，分析了每個疏散策略的競爭比。同時指出分組數(shù)≥2的半圓疏散策略同樣適用于求解疏散區(qū)域為非凸多邊形的疏散問題，并對非凸情形下的競爭比做了詳細分析。
　　最后，編碼實現(xiàn)了n=2的半圓疏散策略以