平面p-center問題是計算幾何和運籌學研究的熱點問題。該問題在實際的生產生活中有極大的應用價值,例如在物流站點建設,城鎮(zhèn)規(guī)劃和通信基站建設等方面的應用。同時平面p-center問題是個經典NP-hard問題,探索求解該問題的高效算法有較大的理論價值。本文的主要工作是設計了兩個求解平面p-center問題的算法。本文首先介紹了平面p-center問題的研究價值和應用價值,并回顧了圍繞平面p-center問題展開的各類工作和成果,明確了研究的目標和方向。其次,本文研究并介紹了與平面p-center問題有關的經典的計算幾何算法、幾何概念和啟發(fā)式算法。之后,在總結和分析相關文獻的基礎上,設計了兩個算法,凸位置點集3-center求解算法和bee-gen算法,分別求解連續(xù)型和離散型的平面p-center問題。凸位置點集3-center求解算法是精確解法,bee-gen算法是使用混合策略的啟發(fā)式算法。在給出算法相關設計細節(jié)和偽代碼描述后,使用Scala語言對bee-gen算法進行實際的編碼和實現(xiàn)。為了驗證bee-gen算法的有效性和正確性,本文構造了多組測試數(shù)據,供bee-gen算法進行計算。... 

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究的背景與意義
    1.2 國內外研究現(xiàn)狀
    1.3 研究內容
    1.4 論文的組織結構
    1.5 本章小結
2 基礎理論知識與經典算法
    2.1 基礎知識
        2.1.1 計算幾何學的相關概念
        2.1.2 相關基本定義與術語
    2.2 計算幾何學的經典問題及其算法
        2.2.1 凸包掃描算法
        2.2.2 最小包圍圓算法
        2.2.3 凸位置點集2-center問題的求解算法
        2.2.4 生成組合算法
    2.3 幾個啟發(fā)式優(yōu)化算法
        2.3.1 人工蜂群算法
        2.3.2 遺傳算法簡介
    2.4 本章小結
3 平面p-center問題的求解算法設計與分析
    3.1 問題的描述
    3.2 平面凸位置點集的3-center的算法
        3.2.1 符號說明
        3.2.2 DFTI數(shù)列最小值搜索算法
        3.2.3 相關引理及其證明
        3.2.4 凸位置點集的3-center算法設計
    3.3 離散版本p-center問題的窮舉算法
    3.4 基于人工蜂群和遺傳算法的啟發(fā)式算法
        3.4.1 編碼方式及初始化方式
        3.4.2 選擇算子
        3.4.3 交叉算子
        3.4.4 變異算子
        3.4.5 算法描述
    3.5 本章小結
4 實驗結果
    4.1 bee-gen算法的測試
        4.1.1 bee-gen算法實現(xiàn)的基本數(shù)據結構
        4.1.2 測試數(shù)據的構造
    4.2 bee-gen算法的實驗結果
        4.2.1 小規(guī)模算例的實驗結果
        4.2.2 bee-gen算法與M-ABC算法比較
    4.3 本章小結
結論
    論文的工作總結
    展望
參考文獻
致謝
作者簡歷及攻讀碩士學位期間的科研成果


【參考文獻】：
期刊論文
[1]基于并行分散搜索的p-中心定位算法[J]. 閆志遠,孫文彬,周長江,熊婷,王江.  地理與地理信息科學. 2013(04)
[2]基于單親遺傳模擬退火算法的頂點p-中心問題[J]. 蔣建林,徐進澎,文杰.  系統(tǒng)工程學報. 2011(03)
[3]受限p-中心的遺傳算法及其應用[J]. 閻新芳,胡華東,趙仲華,孫雨耕.  計算機工程. 2006(04)



本文編號：3723826