论文开题：实施并改进旅行问题算法

大学本科毕业论文(设计)开题报告
学院：计算机科学与技术学院　　　　　　　　　　　　　专业班级：08计算机科学与技术B班

课题名称 实施并改进旅行问题算法

1、 本课题的的研究目的和意义：

在现实生活中各种各样的加工工业上, 例如, 制衣, 制窗, 或机械加工等, 常常需要从大片的纸, 布料, 玻璃, 金属, 等上面切割出很多的部件(假如以简单多边形为模型),而切割的部件通常需要使面积最小或周长最短. 这些应用虽只是解决TP问题中最初始的一步，但不难看出他的实际应用性和重要性。TP问题在交通运输、管道铺设、旅游出行、电路板线路设计、工业材料切割以及物流配送等领域内有着广泛的应用。解决好这个问题对于节约时间金钱、节约城市资源、物流配送人力资源，降低工业制造类企业不必要的开支有着重要的意义，也会对提高运输效率和建设节约型社会十分有利。当然实际上的应用需要解决更复杂的问题，也需要更多的人力物力，所以本课题主要以理想的条件下考虑。

2、 文献综述（
……（新文秘网https://www.wm114.cn省略698字，正式会员可完整阅读）……　
应的步骤进行相应算法的研究与实现，最后我将视时间允许以否把这三个部分进行整合。
成果就是把上面所述的三个部分用开发工具将算法实现,如果有时间将整合到MFC中.


4、拟解决的关键问题：

本课题主要介绍和应用基于三角剖分的TP算法，所以主要解决的是如何将平面多边形进行三角剖分、解决如何进行剪枝优化所求的线段、如何利用RBA橡皮筋算法求解点-线—点最短路径等，。因此该课题所要研究是如何把算法实现以及如何把算法优化最终得到理想的效果。
所谓的技术的路线和方法无非就是运用所学知识把算法在计算机上实现，这也是本课题的重中之重和难点所在。如果非要列出个方法那就是我将应用vc等开发工具进行算法的设计和实现，这就是选择算法课题的优势和劣势所在。
虽然了了几句就把解决问题的方法搞定了，但是这其中要付出的恐怕不比别的课题少。

5、研究思路、方法和步骤：
为了解决TP问题，本课题将引入了点-边-点的最短路径的思路（该知识点李发捷老师做过相关研究），提出基于三角剖分的TP算法如下：
1.对平面上的简单多边形进行三角剖分。（该部分有独立的课）所以剖分的算法我将研究凹凸点判别分割简单多边形为三角形，和实现凸多边形的最优剖分）；
2.按三角形分割的先后顺序将三角形区域进行编号：V1,V2,……，Vn；再将其公共边进行编号e1,e2,……en-1。建立一棵以三角形为节点V,公共边为该树的边E的完整树T；
3.运用树上最短路（The shortest path on the tree）算法对完整树进行剪枝，得到一棵目标树。所求解的旅行问题的最短路径必经过该目标树的所有树边；
4.到这里问题将转化为已知起(终)点，有序的经过目标树上所给的线段。本课题将采用橡皮筋算法（Rubber Band Algorithm，RBA），通过不断调整点与线段，点与点之间的距离，循环比较每次运算得到的路径距离，最后得到简单多边形内任意联系两点间的最短路径，即两个帐篷间的最短路径。
5.以步骤4中的终点为起点，重复步骤4，即可得到到下一个终点得最短距离，如此循环，直到再回到起点，可得到环路最短路径，最后所得即为TP问题所求解。

6、本课题的进度安排(期间将去公司实习所以时间还是偏紧)：
本课题计划分为三部分：

第一部分
2012-2-15——2012-2-28(13天)：主要进行课题的材料收集和课题的前期研究，期间将完成开题报告；
第二部分
2012-3-1——2012-3-20（20天）：主要学习和研究并选择一种算法实现简单多边形的三角剖分（该部分由于有另一个独立课题所以不做深入的研究，然而这又是本课题的基础所以也不得不多花点时间学习）；
2012-3-20——2012-4-05（15天）：主要学习和研究并实现树上最短路算法；
2012-4-05——2012-4-30（25天）：主要学习研究和实现点-线-点问题中两点最短距离的求解及最终TP问题的求解（最终TP问题的求解实现以否和实现效果好坏将依时间而定），这是本课题中最重要的部分，所以讲花比较大的篇幅。（期间有中期检查，将对中期检查的意见进行相应的整理）

第三部分
2012-5-01——答辩：将整理课题设计成果并进行毕业论文材料的收集整理和撰写，完成毕业答辩。














7、参考文献：
1．徐春蕾．李思昆．一种适用任意平面多边形的三角剖分算法[J]．国防科技大学．2000．（02）．
2．马小虎．潘志庚．石教英．基于凹凸顶点判定的简单多边形Delaunay三 ……（未完，全文共3878字，当前仅显示1958字，请阅读下面提示信息。收藏《论文开题：实施并改进旅行问题算法》）