【摘 要】
：
本文针对简单多边形中限于给定点集的最短路径问题进行研究,以期设计出一个求解算法,使得对于简单多边形中给定的点集以及起点s和终点t,能够找到一条从点s出发,中间经过给定
论文部分内容阅读
本文针对简单多边形中限于给定点集的最短路径问题进行研究,以期设计出一个求解算法,使得对于简单多边形中给定的点集以及起点s和终点t,能够找到一条从点s出发,中间经过给定点集中的某些点(也可能不经过),到达点t的最短路径。若这样的路径存在,则输出该路径;否则,报告出最短路径不存在的结论。该问题是TSP问题的变形问题,也是很多实际应用问题(如物流配送问题等)的抽象模型,因此研究该问题,不仅具有理论意义,而且具有很大的实际应用价值。本文首先分析了简单多边形中点的可视性与最短路径计算的关联关系,然后通过分析简单多边形的顶点凸凹特性,将给定的简单多边形分割成若干个边链,求出边链对应的可视集,使得分布于每个可视集中的给定点之间相互可视。在此基础上,计算出关于给定点集的所有可视点对,最后运用Dijkstra算法计算出从点s到点t的最短路径。由于给定点集具有任意性,所以满足要求的最短路径未必存在,本文详细地分析了最短路径存在性,设计出了相应的判别算法以及最短路径的求解算法并加以分析。为了验证所设计算法的有效性,本文实现了所设计的算法并对算法运行结果做了较为详细的分析。实现结果表明,本文所设计的算法是高效的,在时间性能上优于已有的输出敏感度等算法。
其他文献
目的:探讨缺血性卒中急性期中经络不同证型与现代医学血脂指标及脂蛋白相关磷脂酶A2(Lp-PLA2)的相关性及关系,为中西医进一步结合治疗缺血性卒中提供理论依据。方法:1.患者证型分类依据《中国脑梗死中西医结合诊治指南(2017)》制定证型判定量表,将缺血性卒中急性期的患者分为5个证型,并将5个证型归纳为虚证、实证、虚实夹杂证以便研究,详见附录。2.研究指标的检验方法患者入院后第2日清晨采取空腹静脉
HT计量检定系统研制项目虽技术处于先进水平,但管理水平尤其是进度管理水平十分薄弱。本文以国防计量测试设备需求为背景,对HT计量检定系统研制项目的进度管理进行了研究。首
新疆经济比其他发达省份的经济更具有脆弱性,因此,如何保护好新疆经济的稳定发展是关键,而房地产和银行业是重中之重,我国个人住房抵押贷款的法律法规不完善,在市场利润的推
为保证社会秩序的稳定以及人民财产不受侵害,我国自2003年开始建设以人民政府为主体的“政府综合应急系统”。综合应急是为了解决应急事件中的资源调配问题的,重点在于协调而
世界经济在经历了工业化、信息化之后,正逐步走向低碳化,低碳化的发展是一个新的经济发展模式,这一理念已经成为当今世界发展的潮流。改革开放以来,随着我国社会经济的迅速发
随着近几年移动互联网络的快速发展,特别是带有定位功能的智能手机的兴起,使得基于位置信息的服务急速地融入到了人们日常生活的方方面面。比如常用的导航软件、社交软件、外
股票预测是金融领域的经典问题。然而,由于股票走势具有不稳定性、季节性等特点,股价预测受到大量因素的限制。股票的价格取决于众多因素,而这些因素不能直观得到。隐马尔可夫模型可以根据有序的观测数据对隐藏状态转换进行建模,它是一个含有双随机过程的模型。所以隐马尔可夫模型天然适合股价预测,本文即研究将隐马尔可夫模型应用于股票预测。隐马尔可夫模型的学习问题是约束优化问题,常使用Baum-Welch算法求模型参
来氟米特(Leflunomide)属于异恶唑类免疫抑制剂。它的治疗机理主要是通过抑制酪氨酸激酶和二氢乳清酸脱氢酶(Dihydroorotate Dehydrogenase DHODH)的活性,影响活化淋巴细胞的嘧啶合成,干扰细胞增殖,从而抑制淋巴细胞介导的细胞及体液免疫反应。来氟米特上市以来,凭借其独特的免疫抑制作用在类风湿关节炎的临床治疗中得到了比较广泛的应用,在狼疮性肾炎、系统性血管炎治疗以及