Article(id=1242117317488873791, tenantId=1146029695717560320, journalId=1146031591421210625, issueId=1242117308706001190, articleNumber=null, orderNo=null, doi=null, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1218988800000, receivedDateStr=2008-08-18, revisedDate=-2209017600000, revisedDateStr=1900-01-01, acceptedDate=null, acceptedDateStr=null, onlineDate=1186675200000, onlineDateStr=2007-08-10, pubDate=1186675200000, pubDateStr=2007-08-10, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1186675200000, onlineIssueDateStr=2007-08-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1774073445908, creator=sys-migrate, updateTime=1774073445908, updator=sys-migrate, issue=Issue{id=1242117308706001190, tenantId=1146029695717560320, journalId=1146031591421210625, year='2007', volume='25', issue='0715', pageStart='1', pageEnd='96', issueExtLink='null', onlineDate='null', pubDate='1186675200000', pubDateStr='2007-08-10', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=3, issueType=-1, specialIssue=null, createTime=1774073443815, creator='sys-migrate', updateTime=1774073443815, updator='sys-migrate', preIssue=null, nextIssue=null, articleTotal=null, ext=null, issueFiles=null, downloadFileDto=null}, startPage=53, endPage=57, ext={EN=ArticleExt(id=1242117320605241675, articleId=1242117317488873791, tenantId=1146029695717560320, journalId=1146031591421210625, language=EN, title=A New Algorithm for Solving Plane Travelling Salesman Problem: Travelling-around-the-center Method, columnId=1242116080374710456, journalTitle=Science & Technology Review, columnName=Articles, runingTitle=null, highlight=null, articleAbstract=A new algorithm, called the travelling-around-the-center method, is proposed in this paper. It is a deterministic algorithm, with its time complexity the same as the nearest neighbor algorithm, that is, O(n2), where n is the number of cities. Numerical tests for plane travelling salesman problems with various sizes are carried out by using the travelling-around-the-center method and the nearest neighbor algorithm, and the performances of both algorithms are compared. The following conclusions are drawn: (1) The relative performances of the solutions of the travelling-around-the-center method and the nearest neighbor algorithm depend on the number and distribution of the cities in a specific travelling salesman problem. (2) For n=4, the travelling-around-the-center method can always obtain the best solution, while the nearest neighbor algorithm often cannot do so. (3) For a small size problem with n<20, the travelling-around-the-center method can generally obtain better solutions than the nearest neighbor algorithm. (4) For a middle size problem with 20≤n≤30, the quality of the solution obtained by the travelling-around-the-center method is similar to that obtained by the nearest neighbor algorithm. (5) For a large size problem with n>30, the quality of the solution obtained by the travelling-around-the-center method is generally not as good as that obtained by the nearest neighbor algorithm., authors=null, authorsList=null, authorCompany=null, correspAuthors=null, authorNote=null, correspAuthorsNote=null, copyrightStatement=null, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=W8hg6YZmXkwixJK9RBr1UQ==, pdfFileSize=514151, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1242117320135476076, articleId=1242117317488873791, tenantId=1146029695717560320, journalId=1146031591421210625, language=CN, title=一种求解平面旅行商问题的新算法——绕中心周游法, columnId=1146540929516700224, journalTitle=科技导报, columnName=研究论文, runingTitle=null, highlight=null, articleAbstract=提出了一种求解平面旅行商问题的新算法——绕中心周游法，它是一种确定型算法，时间复杂性与最近邻算法相同，为O(n2)，其中n为城市数。利用所编写的绕中心周游法和最近邻算法程序，对不同规模的平面旅行商问题进行了数值试验，对两种算法的求解质量进行了对比分析。结果表明：① 绕中心周游法和最近邻算法求解质量的相对优劣取决于具体问题中城市的数量和分布；② 对于4城市问题，绕中心周游法总能得到最优解，而最近邻算法经常不能得到最优解；③ 对于小规模（n<20）问题，绕中心周游法的求解质量一般优于最近邻算法的求解质量；④ 对于中等规模（20≤n≤30）问题，绕中心周游法的求解质量总体上相当于最近邻算法的求解质量；⑤ 对于大规模（n >30）问题，绕中心周游法的求解质量一般次于最近邻算法的求解质量。, authors=宇德明, authorsList=宇德明, authorCompany=中南大学土木建筑学院, correspAuthors=null, authorNote=null, correspAuthorsNote=null, copyrightStatement=null, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=oB7IaciwruxrhPByuRf+kw==, pdfFileSize=514151, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null)}, authors=null, keywords=[Keyword(id=1242117319699272003, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1242117317488873791, language=CN, orderNo=1, keyword=平面旅行商问题), Keyword(id=1242117319778963782, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1242117317488873791, language=CN, orderNo=1, keyword=绕中心周游法), Keyword(id=1242117319867044167, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1242117317488873791, language=CN, orderNo=1, keyword=数值试验), Keyword(id=1242117319950930248, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1242117317488873791, language=CN, orderNo=1, keyword=最近邻算法), Keyword(id=1242117320026427721, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1242117317488873791, language=CN, orderNo=1, keyword=对比分析)], refs=null, funds=null, companyList=null, figs=null, attaches=null, journal=Journal(id=1125356956822126595, delFlag=0, nameCn=科技导报, nameEn=Science & Technology Review, nameHistory1=null, nameHistory2=null, issn=1000-7857, eissn=, cn=11-1421/N, coden=null, periodic=3, language=CN, oaType=0, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=wfghvu3bhh/dKxuZ+ucVHA==, journalPrice=null, startedYear=null, abbrevIsoEn=Sci Technol Rev, journalRemark=null, publicationField=null, createdTime=null, updatedTime=1784015846012, createdBy=null, updatedBy=13041195026, firstLetterCn=K, firstLetterEn=K, subjectCode=Natural Sciences, subjectName=自然科学, subjectCodeEn=Natural Sciences, subjectNameEn=null, picCn=wfghvu3bhh/dKxuZ+ucVHA==, picEn=yjSfclmpNm7ihn9NbTZ69g==, jcr=null, cjcr=null, exts=[JournalExt(id=1283818766098219763, language=CN, name=科技导报, nameHistory1=null, nameHistory2=null, managedBy=中国科学技术协会, sponsoredBy=中国科学技术协会, publishedBy=科技导报社, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=http://www.kjdb.org/CN/home, createdTime=1784015846037, updatedTime=1784015846037, createdBy=13041195026, updatedBy=13041195026, submissionGuidelinesUrl=http://www.kjdb.org/CN/column/column7.shtml, submissionAuthorUrl=https://kjdbauthor.cast.org.cn/webm, submissionEditorUrl=https://kjdbeditor.cast.org.cn/webm/, submissionReviewUrl=https://kjdbauthor.cast.org.cn/webm, submissionCeEditorUrl=https://kjdbeditor.cast.org.cn/webm/, submissionAeEditorUrl=https://kjdbeditor.cast.org.cn/webm/, option={"copyright":""}), JournalExt(id=1283818766144357108, language=EN, name=Science & Technology Review, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=http://www.kjdb.org/EN/home, createdTime=1784015846048, updatedTime=1784015846048, createdBy=13041195026, updatedBy=13041195026, submissionGuidelinesUrl=http://www.kjdb.org/EN/column/column7.shtml, submissionAuthorUrl=https://kjdbauthor.manuscriptcloud.com/login, submissionEditorUrl=https://kjdbeditor.manuscriptcloud.com/login, submissionReviewUrl=https://kjdbauthor.manuscriptcloud.com/login, submissionCeEditorUrl=https://kjdbeditor.manuscriptcloud.com/login, submissionAeEditorUrl=https://kjdbeditor.manuscriptcloud.com/login, option={"copyright":""})], databaseList=null, tenantJournalId=1146031591421210625, websiteList=[Website(id=1146104741081231361, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1146031591421210625, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/kjdb/CN, language=CN, createTime=1751182263881, createBy=18614031015, updateTime=1751778001962, updateBy=18614031015, name=科技导报, tplId=1146099689490845704, title=科技导报, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1148021146403992296, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146104741081231361, code=articleTextType, value=kx, createTime=1751639170504, updateTime=1751639170504, creator=18614031015, updator=18614031015), WebsiteProps(id=1148021146378826469, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146104741081231361, code=banner, value=null, createTime=1751639170498, updateTime=1751639170498, creator=18614031015, updator=18614031015), WebsiteProps(id=1148021146366243556, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146104741081231361, code=logo, value=https://castjournals.cast.org.cn/joweb/kjdb/CN/file/pic?fileId=9GHSf7eGlIPH0Tv/OOdstA==, createTime=1751639170495, updateTime=1751639170495, creator=18614031015, updator=18614031015), WebsiteProps(id=1148021146395603687, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146104741081231361, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/kjdb/CN/file/pic, createTime=1751639170502, updateTime=1751639170502, creator=18614031015, updator=18614031015), WebsiteProps(id=1148021146387215078, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146104741081231361, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1751639170500, updateTime=1751639170500, creator=18614031015, updator=18614031015)]), Website(id=1146105254833139715, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1146031591421210625, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/kjdb/EN, language=EN, createTime=1751182386363, createBy=18614031015, updateTime=1753500121937, updateBy=18614031015, name=科技导报, tplId=1146101810881728533, title=Science & Technology Review, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1155838567709528217, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146105254833139715, code=articleTextType, value=kx, createTime=1753502988984, updateTime=1753502988984, creator=18614031015, updator=18614031015), WebsiteProps(id=1155838567692750998, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146105254833139715, code=banner, value=null, createTime=1753502988980, updateTime=1753502988980, creator=18614031015, updator=18614031015), WebsiteProps(id=1155838567688556693, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146105254833139715, code=logo, value=https://castjournals.cast.org.cn/joweb/kjdb/EN/file/pic?fileId=9GHSf7eGlIPH0Tv/OOdstA==, createTime=1753502988979, updateTime=1753502988979, creator=18614031015, updator=18614031015), WebsiteProps(id=1155838567705333912, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146105254833139715, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/kjdb/EN/file/pic, createTime=1753502988983, updateTime=1753502988983, creator=18614031015, updator=18614031015), WebsiteProps(id=1155838567701139607, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1146105254833139715, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1753502988982, updateTime=1753502988982, creator=18614031015, updator=18614031015)])], journalTitle=科技导报, weixinUrl=null, journalUrl=null, iacademicId=null, status=1, seqNo=null, journalTitleEn=Science & Technology Review, journalPhotoCn=wfghvu3bhh/dKxuZ+ucVHA==, journalPhotoEn=yjSfclmpNm7ihn9NbTZ69g==, journalFirstLetter=K, journalRecommend=null, journalNew=null, journalCollection=1, jcrJf=null, cjcrJf=0.91, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/kjdb/CN/Y2007/V25/I0715/53, detailUrlEn=https://castjournals.cast.org.cn/joweb/kjdb/EN/Y2007/V25/I0715/53, pdfUrlCn=https://castjournals.cast.org.cn/joweb/kjdb/CN/PDF/Y2007/V25/I0715/53, pdfUrlEn=https://castjournals.cast.org.cn/joweb/kjdb/EN/PDF/Y2007/V25/I0715/53, aliStartDate=null, aliEndDate=null, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=0, orderTime=1186675200000, fullTextJson=null, articleText=null, reference=null)
科技导报
|研究论文
2007
, 25
(0715) :
53
-57
一种求解平面旅行商问题的新算法——绕中心周游法
全屏
宇德明
作者信息
A New Algorithm for Solving Plane Travelling Salesman Problem: Travelling-around-the-center Method
Affiliations
出版时间: 2007-08-10
文章导航
提出了一种求解平面旅行商问题的新算法——绕中心周游法，它是一种确定型算法，时间复杂性与最近邻算法相同，为O(n2)，其中n为城市数。利用所编写的绕中心周游法和最近邻算法程序，对不同规模的平面旅行商问题进行了数值试验，对两种算法的求解质量进行了对比分析。结果表明：① 绕中心周游法和最近邻算法求解质量的相对优劣取决于具体问题中城市的数量和分布；② 对于4城市问题，绕中心周游法总能得到最优解，而最近邻算法经常不能得到最优解；③ 对于小规模（n<20）问题，绕中心周游法的求解质量一般优于最近邻算法的求解质量；④ 对于中等规模（20≤n≤30）问题，绕中心周游法的求解质量总体上相当于最近邻算法的求解质量；⑤ 对于大规模（n >30）问题，绕中心周游法的求解质量一般次于最近邻算法的求解质量。
平面旅行商问题
/
绕中心周游法
/
数值试验
/
最近邻算法
/
对比分析
A new algorithm, called the travelling-around-the-center method, is proposed in this paper. It is a deterministic algorithm, with its time complexity the same as the nearest neighbor algorithm, that is, O(n2), where n is the number of cities. Numerical tests for plane travelling salesman problems with various sizes are carried out by using the travelling-around-the-center method and the nearest neighbor algorithm, and the performances of both algorithms are compared. The following conclusions are drawn: (1) The relative performances of the solutions of the travelling-around-the-center method and the nearest neighbor algorithm depend on the number and distribution of the cities in a specific travelling salesman problem. (2) For n=4, the travelling-around-the-center method can always obtain the best solution, while the nearest neighbor algorithm often cannot do so. (3) For a small size problem with n<20, the travelling-around-the-center method can generally obtain better solutions than the nearest neighbor algorithm. (4) For a middle size problem with 20≤n≤30, the quality of the solution obtained by the travelling-around-the-center method is similar to that obtained by the nearest neighbor algorithm. (5) For a large size problem with n>30, the quality of the solution obtained by the travelling-around-the-center method is generally not as good as that obtained by the nearest neighbor algorithm.
宇德明.
一种求解平面旅行商问题的新算法——绕中心周游法.
科技导报,
2007
, 25
(0715)
: 53
-57
.
.
A New Algorithm for Solving Plane Travelling Salesman Problem: Travelling-around-the-center Method[J].
Science & Technology Review ,
2007
, 25
(0715)
: 53
-57
.
2007年第25卷第0715期
PDF下载
189
49
引用本文
BibTeX
文章信息
接收时间：2008-08-18
首发时间：2007-08-10
出版时间：2007-08-10
收稿日期：2008-08-18
修回日期：1900-01-01
https://castjournals.cast.org.cn/joweb/kjdb/CN/1242117317488873791
引用本文
BibTeX
2种不同金属材料的力学参数
科 属数 种数 占总种数比例 属 种数 占总种数比例 鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78 小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39 多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39 红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87 小菇属 Mycena 11 5.26 光柄菇属 Pluteus 5 2.39 红菇属 Russula 17 8.13 栓菌属 Trametes 5 2.39
关闭全屏
BibTeX
EndNote
RefWorks
TxT
PDF下载
全屏
189
49
关闭全屏
北京市海淀区学院南路86号
010-62199257（仅加盟咨询）
qkjq@cast.org.cn
