项目负责人：

大连科技学院信息科学与技术学院王立娟教授

项目简介：

项目针对平面上给定的n个几何物体构成的序列以及起点s和终点t，要求计算一条从点s出发，依次遍历每个物体，最终回到点t的最优遍历路径，针对所研究的问题，如：平面上可相交线段序列、不相交凸多边形序列、可相交凸多边形序列和不相交任意多边形序列问题给出了相对优化的解决方案。本课题的研究成果可用于求解部件切割等一些实际应用问题，如以最小成本在一块板材料上连续切割出一系列不相交多边形部件的问题，该问题实际上是要计算一条最短的切割路线，而本课题的研究结果正好用于求解该问题。此外，机器人行走路线、物流规划中的最佳配送路线、最小成本旅游路线等实际应用问题的求解，也可借助本课题的研究结果，以获得高效的解决方案。本课题的研究结果可为求解一些实际应用问题提供一个经济、可行的解决方案，为社会带来很大的经济效益。