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

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

【學位級別】：碩士

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


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



本文編號：3724306