【摘 要】
:
ESP问题是计算几何中的经典问题。本文针对遍历平面内可相交直线序列的ESP问题进行研究,研究目标是要寻找一条从起点出发到达终点,且遍历给定直线序列中每条直线至少一次的最
论文部分内容阅读
ESP问题是计算几何中的经典问题。本文针对遍历平面内可相交直线序列的ESP问题进行研究,研究目标是要寻找一条从起点出发到达终点,且遍历给定直线序列中每条直线至少一次的最短路径。该问题是很多实际应用问题的抽象模型,针对该问题的研究,不仅具有重要的理论意义,而且也具有很高的实际应用价值。本文首先阐述了与求解问题相关的基础知识与求解方法,如点与直线的位置关系、直线与直线的位置关系、对称点、凸包、贪婪算法、Rubber-band算法等。在此基础上,通过构造给定直线序列的凸多边形,将平面内直线序列的遍历问题转化为平面内可相交线段序列的遍历问题。为此,本文详细论述了凸包构造方法以及依据凸包构造凸多边形的详细过程,给出了遍历给定可相交直线序列的最优遍历路径一定包含在所构造的凸多边形内部的研究结论及其严格的理论证明。接着,通过对比分析两种求解可相交线段序列的改进Rubber-band算法,选择交换访问顺序的处理方式,提出了一个时间复杂度为O(n2)的求解平面内可相交直线序列的最短遍历路径的算法。针对提出的算法,设计了相应的数据结构,并用C++程序设计语言实现了该算法。随机构造了大量测试数据,对所提出的算法进行了测试,并可视化算法运行结果,验证了算法的正确性和有效性。
其他文献
中国的A股市场具有我国的特色。本文旨在构建股票上涨期间不同板块交替上行中技术特征的识别方法,用来指导投资者把握不同时间强势板块的轮动,从而指导投资者踏准上涨过程中
对采自内蒙古自治区鄂尔多斯库布齐沙漠对三种样地中379个蜥蜴胃的内容物进行分析,其中草原沙蜥(Phrynocephalus frontal is)47只,密点麻蜥(Eremias multiocellata)48只,丽斑
随着工业化进程的发展,近年来我国水体藻类水华污染严重,大量繁殖的藻类释放出大量有毒的藻毒素。藻毒素是一种肝毒素,它对水环境和人的身体健康已经造成不可忽视的危害。因
自工业革命以来,由于人类的活动大气中CO_2浓度持续增加,导致环境问题日益严重,对城市气候以及生存环境带来了显著影响。因此减排增汇成为可持续发展中的重要内容。城市绿地作为城市重要的自然生态系统,是城市生态系统中所存在唯一的自然碳汇。绿地能够通过其自身的光合作用固碳释氧,从而减缓城市区域内气候恶化的趋势。因此在城市边界内,植物群落的碳汇作用对城市碳循环有积极影响。同时,在城市中的植被也因自身的相关措
河岸带生态系统在陆地与河流相交边界的两侧到不受河水影响的位置,属于陆生生态系统与水生生态系统的生态过渡区。河岸缓冲带在涵养水源和保持水土等方面具有重要的生态服务功能。河岸带生态系统在增加动植物物种种源、提高生物多样性和生态系统生产力、治理水土流失、稳定河岸、调节微气候、美化环境、开展旅游活动等均有重要的现实和潜在价值。河岸带独特的植被、土壤、地形、地貌和水文特性决定生态系统独特性、复杂性与动态性。
随着我国经济的高速发展,城市化水平逐步提升,促使我国的基建业和城市建设日益繁荣。我国的工业发展水平逐步进入中后期阶段,铁矿石作为工业生产主要原料之一,对铁矿石价格进行准确的预测和掌控,可以在铁矿石价格谈判时提供重要参考依据,同时为钢铁企业提供一个反映铁矿石市场情况的指示器。首先,通过分析全球以及我国的铁矿石供需市场的发展现状,明确了铁矿石供需市场的格局。并且从供需、成本、政策、市场类型和金融五个角
最近,垃圾分类成为人们关注的焦点。截止目前我国已有46所城市开始严格执行垃圾分类政策。Reduce,Reuse,Reimagine:Sorting outthe Recycling System(《少排放,重利用,再构想:重整回收系统》)一书对中国当前的垃圾分类有一定的借鉴意义。本翻译实践报告所选材料来自该书的第一章和第九章,第一章主要介绍了再循环生态系统的重要性;第九章主要向人们介绍了垃圾分类的
随着现代科技发展,人工智能技术的研究受到广泛的关注。基于数据的机器学习是其重要的研究内容,即从收集的数据样本中学习规律,并且使用这些规律对未来观测数据或无法观测的事物进行预测。然而现实环境中存在大量的繁琐复杂的现象与事物,随着收集观测事物的数据信息的增多,“维数的诅咒”随之出现,它指的是,在缺乏简单假设的情况下,估计一个具有多个变量的函数达到一定精度所需的样本量在变量数量上呈指数增长。高维数据虽然
蛋白质作为生命活动的重要承载者,它的结构对于生物学和医学研究有着重要的意义,利用计算手段预测蛋白质结构逐渐成为生物信息学的重要课题。本文的研究内容是从一级结构提取
棉花是一种重要的经济作物,在日常生活中有重要的应用价值。棉花D-7蛋白属于第三组胚胎发育晚期富集蛋白(LEA)家族的成员,有研究表明第三组LEA基因是一个诱导基因,在种子成熟