平面p-center问题求解算法研究

发布时间：2022-12-22 18:40

　　平面p-center问题是计算几何和运筹学研究的热点问题。该问题在实际的生产生活中有极大的应用价值,例如在物流站点建设,城镇规划和通信基站建设等方面的应用。同时平面p-center问题是个经典NP-hard问题,探索求解该问题的高效算法有较大的理论价值。本文的主要工作是设计了两个求解平面p-center问题的算法。本文首先介绍了平面p-center问题的研究价值和应用价值,并回顾了围绕平面p-center问题展开的各类工作和成果,明确了研究的目标和方向。其次,本文研究并介绍了与平面p-center问题有关的经典的计算几何算法、几何概念和启发式算法。之后,在总结和分析相关文献的基础上,设计了两个算法,凸位置点集3-center求解算法和bee-gen算法,分别求解连续型和离散型的平面p-center问题。凸位置点集3-center求解算法是精确解法,bee-gen算法是使用混合策略的启发式算法。在给出算法相关设计细节和伪代码描述后,使用Scala语言对bee-gen算法进行实际的编码和实现。为了验证bee-gen算法的有效性和正确性,本文构造了多组测试数据,供bee-gen算法进行计算。... 

【文章页数】：58 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究的背景与意义
    1.2 国内外研究现状
    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 几个启发式优化算法
        2.3.1 人工蜂群算法
        2.3.2 遗传算法简介
    2.4 本章小结
3 平面p-center问题的求解算法设计与分析
    3.1 问题的描述
    3.2 平面凸位置点集的3-center的算法
        3.2.1 符号说明
        3.2.2 DFTI数列最小值搜索算法
        3.2.3 相关引理及其证明
        3.2.4 凸位置点集的3-center算法设计
    3.3 离散版本p-center问题的穷举算法
    3.4 基于人工蜂群和遗传算法的启发式算法
        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算法实现的基本数据结构
        4.1.2 测试数据的构造
    4.2 bee-gen算法的实验结果
        4.2.1 小规模算例的实验结果
        4.2.2 bee-gen算法与M-ABC算法比较
    4.3 本章小结
结论
    论文的工作总结
    展望
参考文献
致谢
作者简历及攻读硕士学位期间的科研成果


【参考文献】：
期刊论文
[1]基于并行分散搜索的p-中心定位算法[J]. 闫志远,孙文彬,周长江,熊婷,王江.  地理与地理信息科学. 2013(04)
[2]基于单亲遗传模拟退火算法的顶点p-中心问题[J]. 蒋建林,徐进澎,文杰.  系统工程学报. 2011(03)
[3]受限p-中心的遗传算法及其应用[J]. 阎新芳,胡华东,赵仲华,孙雨耕.  计算机工程. 2006(04)



本文编号：3723826