货郎担问题的几何解法

微信服务号

微信订阅号

首页 > 过刊浏览>1995年第6卷第7期 >420-424

货郎担问题的几何解法
DOI:
                        
                    
作者:
                        
                        
                    
作者单位:
作者简介:
通讯作者:
中图分类号:
基金项目:

GEOMETRIC METHOD FOR SOLVING TS PROBLEM

Author:

Affiliation:

Fund Project:

摘要

图/表

访问统计

参考文献

相似文献

引证文献

资源附件

文章评论

摘要:

本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（n²/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 Ｏ（ｎｍ）, the number of comparisons is Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）） and the number of computation included angle is Ｏ（n²/m）.

参考文献

相似文献

引证文献

引用本文

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

复制

文章指标

点击次数:
下载次数:
HTML阅读次数:
引用次数:

历史

收稿日期:1993-10-23
最后修改日期:1994-03-15
录用日期:
在线发布日期:
出版日期:

微信服务号

微信订阅号

引用本文

分享

文章指标

历史