本文主要针对平面上相邻可能相交凸多边形序列的遍历问题进行研究,目标是寻找一条从起点s出发,按照它们事先约定好的顺序依次遍历每个凸多边形,最终到达终点t的最短路径。该问题既是TSP问题的延伸研究,也是计算几何学领域的一个理论课题,研究该问题,不仅具有一定的理论价值,而且也有很大的实际应用价值。本文在论述TSP问题、画廊问题、WRP问题、简单多边形及其凹凸性、局部最短路径及现有相关研究成果的基础上,对平面上相邻可能相交凸多边形序列的遍历问题,做了比较深入的研究,指出了现有研究结果中存在的问题,即所采用的数据结构较为复杂且难以实现,以及算法时间复杂度较高等。为了解决这些问题,本文通过分析点与直线的位置关系、点到直线的距离、点与凸多边形的位置关系等几何要素,结合动态规划算法的思想,运用组合优化策略,设计出了一个求解平面内相邻可能相交凸多边形序列遍历问题的优化算法,将计算最短路径分为两个主要过程:一是从前往后求解凸多边形序列的最短路径图的过程;二是从后往前求解所有凸多边形必须访问边的过程。通过上述两个过程的有机融合,将平面内凸多边形序列的遍历问题,转化为平面内一组有序线段构成的序列的遍历问题,最终设计出了一个O(kn)的优化求解算法,降低了求解该问题的算法时间复杂度。在此基础上,通过构造相应测试数据,编程实现所设计的算法,可视化算法的运行结果,并与理论结果作对比分析,验证了本文所设计的算法的可行性及其有效性。