访问平面内不相交线段ESP问题的最优求解算法及其验证

An optimal algorithm and its verification on ESP problem of visiting disjoint segments in the plane

针对依次访问平面内一组互不相交线段的ESP问题,以Rubber-band算法为基础,提出一个改进的Rubber-band算法.该算法通过引入分而治之方法来减少算法的迭代次数.设计一个测试数据自动生成算法并随机生成4个测试数据集,实际运行改进前后的两个算法,采用事后分析方法对两个算法的运行时间性能进行对比分析.结果表明:改进算法的时间复杂度为O(n),优于时间复杂度为O(n2)的Rubber-band算法,是一个时间性能最优的ESP问题的求解算法.

This paper mainly studied on the ESP problem of visiting a sequence of disjoint segments given in the plane.Based on Rubber-band algorithm,an improved algorithm was proposed,which adopted the thought of divide-and-conquer to reduce the times of iteration.An automatic generation test data algorithm which generated randomly 4 groups of test data sets was designed to analyze the algorithm＇s time performance,and the two algorithms were operated and compared.Results show that the time complexity of Rubber-band algorithm is O（n2） and that of the improved algorithm is O（n）.The experiments demonstrate that the Rubber-band developed algorithm is superior to the known same-purpose implementation.