ESP问题,即Euclidean最短路径问题,是计算几何中一个比较典型的问题。该问题的基本描述为：在欧式空间中,给定源点、目标点以及一系列障碍物,希望求出从源点出发经过这些障碍物到达目标点的最短路径。本文对访问平面内无序不相交线段的ESP问题进行研究,该问题的几何描述如下：给定平面内的两个点：源点p,目标点q,以及包含n(n>0)条线段的线段集S={s1,s2…,sn},且si∩sj=φ(1≤ij≤n),希望求出从点p到达点q并访问这些线段当且仅当一次的最短路径。该问题是ESP问题的一个子问题。该问题可以作为很多实际问题的逻辑模型,例如二维模式识别、机器人运动规划、图像处理分析、巡视员等问题。在求解ESP问题时,会遇到大量计算几何的基础知识和算法。所以,本文首先针对计算几何的相关基础知识和算法进行了研究,主要学习了线段相交性判断、连通图、生成树、三角剖分和对偶图等。随后,对访问平面内有序不相交线段的ESP问题的一种求解算法——-Rubberband算法及其改进算法进行了深入的研究。然后,针对本文要求解的ESP问题,运用最小生成树的思想,提出了本文的求解算法,并且对该算法进行了分析,分析结果表明该算法时间复杂度为O(n3)。最后,运用事后分析法对该算法的运行时间和结果进行了分析,绘制了“算法运行时间／线段条数”关系曲线,并且运用了对比分析法将该算法的运行时间、结果与穷举法进行了对比。对比结果表明：在误差允许范围内,该算法运行结果可信,可以在多项式时间复杂度内得到ESP问题的近似最优解。本文的重点在于确定平面内无序线段的访问顺序上,主要使用了动态构造最小生成树并且遍历最小生成树的方法进行解决。