本文選題：計(jì)算幾何　切入點(diǎn)：Online搜索問題　出處：《大連海事大學(xué)》2017年碩士論文

【摘要】：平面上成組疏散的Online搜索問題的求解研究,不僅涉及計(jì)算幾何、圖論、組合優(yōu)化等技術(shù)方法,而且是解決很多實(shí)際應(yīng)用問題的基礎(chǔ),所以針對(duì)該問題的研究,不僅具有理論意義,而且具有較高的實(shí)際應(yīng)用價(jià)值。本文針對(duì)邊界信息未知的單源點(diǎn)疏散問題中分組數(shù)為n(n≥2)的快速疏散策略進(jìn)行研究,首先分析了用于問題求解的相關(guān)基礎(chǔ)知識(shí)及概念,如判斷點(diǎn)在直線上、判斷點(diǎn)是否在多邊形內(nèi)、競(jìng)爭(zhēng)比的計(jì)算等,然后對(duì)直線上探索問題的雙倍策略、單源點(diǎn)與多源點(diǎn)的成組等角疏散策略、單源點(diǎn)半圓疏散策略等已有研究結(jié)果進(jìn)行了較為詳細(xì)的分析,指出了其中存在的不足。在此基礎(chǔ)上,針對(duì)分組數(shù)為2的單源點(diǎn)疏散問題,應(yīng)用半圓疏散策略,設(shè)計(jì)出了相應(yīng)的求解算法,并拓展應(yīng)用到分組數(shù)為n(n≥3)的情形,設(shè)計(jì)出了相應(yīng)的成組扇形疏散策略,分析了每個(gè)疏散策略的競(jìng)爭(zhēng)比。同時(shí)指出分組數(shù)≥2的半圓疏散策略同樣適用于求解疏散區(qū)域?yàn)榉峭苟噙呅蔚氖枭栴},并對(duì)非凸情形下的競(jìng)爭(zhēng)比做了詳細(xì)分析。最后,編碼實(shí)現(xiàn)了n=2的半圓疏散策略以及分組數(shù)≥2的成組扇形疏散策略。運(yùn)行結(jié)果表明,本文所設(shè)計(jì)的算法是可行且高效的。
[Abstract]:The research of solving the Online search problem of group evacuation on the plane is not only related to computational geometry, graph theory, combinatorial optimization and other technical methods, but also the basis of solving many practical application problems.Not only has the theory significance, but also has the higher practical application value.In this paper, the fast evacuation strategy for single source point evacuation problem with unknown boundary information is studied. Firstly, the basic knowledge and concepts for solving the problem are analyzed, such as the judgment point is on a straight line.To determine whether the point is in the polygon, to calculate the competition ratio, and then to explore the double strategy of the problem on the straight line, the group equiangular evacuation strategy of the single source point and the multiple source point, etc.The research results of single source point semi-circular evacuation strategy are analyzed in detail, and the shortcomings are pointed out.On this basis, for the evacuation problem of single source point with number of groups 2, a corresponding algorithm is designed by using semi-circular evacuation strategy, and extended to the case where the number of groups is n / n 鈮，

本文編號(hào)：1716588