本文針對(duì)平面上不相交線段集的最小邊界長(zhǎng)凸包問題進(jìn)行研究,目標(biāo)是要找到一個(gè)包含或者經(jīng)過每條給定線段的最小邊界長(zhǎng)凸包。該問題的研究,不僅具有較大的理論價(jià)值,而且也有很大的實(shí)際應(yīng)用價(jià)值。因?yàn)樗兄谇蠼鈾C(jī)器人行進(jìn)路線、最優(yōu)物流配送路線、機(jī)械零件的切割等一類實(shí)際應(yīng)用問題。本文首先論述了 TSP、WRP以及Rubber-band算法等相關(guān)知識(shí)概念以及現(xiàn)有相關(guān)研究成果。然后在此基礎(chǔ)上,深入研究與分析了與本文研究問題相關(guān)的研究,指出了現(xiàn)有研究結(jié)果所存在的不足,即算法時(shí)間復(fù)雜度較高等。為改進(jìn)已有相關(guān)算法的不足,本文通過分析線段與凸多邊形的位置關(guān)系等要素,設(shè)計(jì)出了一個(gè)求解平面內(nèi)給定的不相交線段集的最小邊界長(zhǎng)凸包問題的優(yōu)化算法,將計(jì)算最小邊界長(zhǎng)凸包分為兩個(gè)主要過程.:一是求出包含所有線段的凸包;二是收縮所得到的凸包且同時(shí)保證沒有任何一條線段會(huì)完全位于凸包的外部,從而求出一個(gè)具有最小邊界長(zhǎng)的凸包。通過上述兩個(gè)過程的有機(jī)融合,本文設(shè)計(jì)出了一個(gè)O（n4）的求解算法,優(yōu)化了求解該問題的現(xiàn)有算法。 

【文章頁(yè)數(shù)】：63 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景與意義
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
    1.3 研究?jī)?nèi)容
    1.4 論文的組織結(jié)構(gòu)
    1.5 本章小結(jié)
2 相關(guān)基礎(chǔ)知識(shí)與算法
    2.1 基礎(chǔ)知識(shí)概念
        2.1.1 計(jì)算幾何學(xué)的相關(guān)概念
        2.1.2 相關(guān)基本概念及定義
        2.1.3 平面上不相交線段集的遍歷問題
    2.2 幾個(gè)經(jīng)典算法及其性能分析
        2.2.1 Graham Scan算法
        2.2.2 線段與凸多邊形位置關(guān)系的判斷算法
        2.2.3 Rubber-band算法
        2.2.4 局部路徑收縮及優(yōu)化技術(shù)
    2.3 本章小結(jié)
3 最小邊界長(zhǎng)凸包的構(gòu)造方法
    3.1 問題及求解方法概述
    3.2 包含所有線段端點(diǎn)的凸包構(gòu)造
    3.3 最小邊界長(zhǎng)凸包的構(gòu)造過程
        3.3.1 凸包C_0的構(gòu)造及其特征分析
        3.3.2 凸包邊界的收縮方法
    3.4 本章小結(jié)
4 算法設(shè)計(jì)及其分析
    4.1 CHSP算法設(shè)計(jì)
    4.2 算法的性能分析
    4.3 算法實(shí)驗(yàn)結(jié)果與分析
        4.3.1 測(cè)試數(shù)據(jù)的生成
        4.3.2 運(yùn)行結(jié)果分析
    4.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
致謝
作者簡(jiǎn)歷及攻讀碩士學(xué)位期間的科研成果


【參考文獻(xiàn)】：
期刊論文
[1]密集障礙物環(huán)境下基于凸包和微粒群優(yōu)化的機(jī)器人路徑規(guī)劃[J]. 鞏敦衛(wèi),耿娜,張勇.  控制理論與應(yīng)用. 2012(05)
[2]多邊形的簡(jiǎn)單性、方向及內(nèi)外點(diǎn)的判別算法[J]. 王志強(qiáng),肖立瑾,洪嘉振.  計(jì)算機(jī)學(xué)報(bào). 1998(02)



本文編號(hào)：3724306