基于凸链存储的可相交线段序列遍历算法研究

《基于凸链存储的可相交线段序列遍历算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：密级１０１５１ＵＤＣ单位代码：）乂是洛事乂學禱、巧全日制应用型硕±研究生学位论文基于凸链存储的可相交线段序列遍历算法研究杨阳指导教师曹志英副教授企业导师赵蠢龙高级工程师申请学位类别工程硕±工程领域软件工程学位授予单位大连海事大学２０１６年６月分类号密级ＵＤＣ单位代码１０１５１大连海事大学工程硕±学位论文基于凸链存储的可相交线段序列遍历算法研究（学位论文形式：应用研究）

2、杨阳指导教师曹志英职称副教授企业导师赵蠢龙职称高级工程师学位授予单位大连海事大学申请学位级别工程硕±工程领域软件工程论文完成日期２０１６年５月答辩日期２０１６年６月答辩委员会主席Ｒｅ－ｓｅａｒｃｈｏｎｔｈｅＴｏｕｒｉｎＡｌｏｒｉｔｈｍｓｏｆＰａｒｔｉａｌｏｉｎｔｇｇｊＳｅｍｅｎｔｓｉｎＯｒｄｅｒＢａｓｅｄｏｎＣｏｎｖｅｘＣｈａｉｎＳｔｏｒａｅｇｇＡ化ｅｓｉｓＳｕｂｍｉｔｔｅｄ化ＤａｌｉａｎＭａｒｉｔｉｍｅＵ

3、ｎｉｖｅｒｓｉｔｙＩｎａｒｔｉａｌｆｕｌｆｉｌｌｍｅｎｔｏｆｔｈｅｒｅｕｉｒｅｍｅｎｔｓｆｏｒｔｈｅｄｅｒｅｅｏｆｐｑｇＭａｓｔｅｒｏｆＥｎｉｎｅｅｒｉｎｇｇｂｙＹａｎＹａｎｇｇＳｏｆｔｗａｒｅＥｎｉｎｅｅｒｉｎ（ｇｇ）ＴｈｅｓｉｓＳｕｐｅｒｖｉｓｏｒ：ＡｓｓｏｃｉａｔｅＰｒｏｊｆｅｓｓｏｒＣａｏＺｈｉｙｉｎｇ＜Ｊｕｎｅ２０１６大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工

4、作所取得的成果，＂某＂撰写成博／硕±学位论文于凸链存储的可相安线段序列遍历算法研究。除论文中已经注明引用的内容外，，对论文的研究做出重要贡献的个人和集体均已在文中Ｗ明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名：掀沪学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规定，目：大连海事大学有权保留并向国家有关部口或机构送交学位论Ｐ文的复印件

5、和电子版，允许论文被查阅和借阅。本人授权大连海事大学可Ｗ将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到《中国优秀博硕±学位论文全文数据库》（中国学术期刊（光盘版）电子杂志社）、《中国学位论文全文数据库》（中国科学技术信息研究所）等数据库中，并Ｗ电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于：保密□在年解密后适用本授权书。＂＂不保琴（请在Ｗ上方框内打Ｖ）论文作者签

6、名：导师签名：曰期；細＾年＾＾月化曰中文摘要摘要一本文针对平面内可相交线段序列的最优遍历问题进行研究，目标是寻找条从给定起点出发，依次遍历给定的可相交线段序列，最后到达终点的最短遍历路一径，，。研究该问题的高效求解方法不仅是个理论问题而且有助于机器人运动一规划，因而具有较大的理论意义和实际、无人机控制等些实际应用问题的求解应用价值。本文详细分析了ｂｅｒ－ｂａｎｄＲｕｂ算法在求解可相交线段序列遍历问题时所出现的退化现象，Ｗ及局部最优路径迭代计算过程中存在的重复计算等问

7、题，同时指出为处理线段相交点而提出的Ｒｕｂｂｅｒ－ｂａｎｄ改进算法（枢点法）中存在着计算结果不精确的问题。为解决这些问题，本文在分析点与线段的位置关系的基础上，详细论述了穿越、完美反射，，Ｗ及在线段端点处发生折射等局部最优路径收缩技术提出了基于跨线段处理相交点与局部最优路径凸链存储结构的分段优化并加Ｗ组一〇＊２ｌ合的求解方法，设计出了个时间复杂度为ｎｏ？的求解可相交线段序列遍历（ｇ）问题的算法。该算法不仅有效地解决了退化问题，而且有效地减少了局部最优遍历路径收缩计算中的迭代次数。为

8、验证所设计算法的有效性，本文设计出了相应，Ｊａｖａ语言编程实现了所设计出的算法，的数据结构用，随机构造了大量测试数据并给出了算法运行的可视化结果。实验结果表明，本文所提出的算法，不仅有效地解决了Ｒｕｂｂ－ｅｒｂａｎｄ算法的退化现象等问题，而且所计算出的最短遍历路径比采用枢点法的结果更为精确，是迄今为止解决可相交线段序列遍历问题的最优算法。－关键词：Ｒｕｂｂｅｒｂａｎｄ算二分检索