排序方式: 共有22条查询结果,搜索用时 0 毫秒
21.
寻求中国货郎担问题最短回路的多项式时间算法 总被引:7,自引:1,他引:6
研究求解中国货郎担问题最短回路的多项式时间算法。首先利用计算机几何凸壳与中轴的结构将集划分尤其中干个子点集,然后反复采用求子点集凸壳及划分科余子点集的方法,求得通过子点集的子路径,最后将各子路径连接成一条回路。中国货郎担问题存在多项时间算法求得最短回路。 相似文献
22.
确定任意多边形中轴的算法 总被引:8,自引:0,他引:8
提出确定凸多边形中轴和任意简单多边形中轴两个算法,其基本思想是利用与多边形两条边或三条边等距离的点的轨迹。算法的时间复杂性均为线性的,优于Lee算法(1982年)和Aggarwal算法(1989年)。与Chin等人提出的算法(1999年)具有相同的时间复杂性的阶,但思想方法完全不同,并且产生的结果也不相同,该算法获得直线段树,更有利于应用。 相似文献