###
DOI:
Journal of Software:1995.6(7):420-424

货郎担问题的几何解法
周培德
(北京理工大学计算机系,北京,100081)
GEOMETRIC METHOD FOR SOLVING TS PROBLEM
Zhou Peide
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2996   Download 3605
Received:October 23, 1993    Revised:March 15, 1994
> 中文摘要: 本文提出货郎担问题的一种新的求解方法,即几何解法.它的时间复杂性为:求距离运算次数为nm),比较次数为(max(nm,nlogn)),求夹角次数为(n2/m),其中为点集中点的数目,为点集的凸包顶点数.
中文关键词: 几何算法  算法复杂性  货郎担问题  
Abstract:In this paper, a new geometric method for solving TS problem is presented.Let n be the number of points in the point set, and m be the number of vertexes in convex hulls of the point set. The time complexity of the algorithm is: the number of computation distance is nm), the number of comparisons is (max(nm,nlogn)) and the number of computation included angle is (n2/m).
文章编号:     中图分类号:    文献标志码:
基金项目:
Foundation items:
Reference text:

周培德.货郎担问题的几何解法.软件学报,1995,6(7):420-424

Zhou Peide.GEOMETRIC METHOD FOR SOLVING TS PROBLEM.Journal of Software,1995,6(7):420-424