基于求解TSP问题的改进贪婪算法

来源 :运筹与管理 | 被引量 : 0次 | 上传用户：baogehaohao

【摘要】

：

分析了求解旅行商问题（Traveling Salesman Problem,TSP）的经典贪婪算法（Greedy Heuristic,GR）的特点,发现影响GR求解质量的主要因素是在构造后期添加的边过长,从而导致最终求解

【作者】

：

饶卫振金淳

【机构】

：

大连理工大学系统工程研究所

【出处】

：

运筹与管理

【发表日期】

：

2012年6期

【关键词】

：

运筹学旅行商问题改进贪婪算法 HeldKarp模型

【基金项目】

：

国家自然科学基金资助项目(70571008);辽宁省自然科学基金资助项目(20062184)

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

分析了求解旅行商问题（Traveling Salesman Problem,TSP）的经典贪婪算法（Greedy Heuristic,GR）的特点,发现影响GR求解质量的主要因素是在构造后期添加的边过长,从而导致最终求解质量不高。为此,借鉴Held Karp模型的思路,构造了一种新的距离矩阵改造法（Transforming Distance Matrix,TDM）。GR结合TDM得到的改进贪婪算法GR-TDM能够有效地克服传统GR在构造后期添加长边的缺点。通过计算来自TSP算例标准库和TSP世界挑战赛网站

其他文献

利用激发极化法划分第四纪含水层的体会

<正> 目前,激发极化法已在水文地质勘察中得到推广应用,在山西则已成为普查地下水的主要物探手段,具有一定的地质效果。由于该法在一个测点上可同时测得四个不同参数的曲线(

期刊

含水层激发极化法电测深曲线

功能性食品产业发展现状与对策研究

随着人们生活水平的提高,饮食健康逐渐成为了现代人关注的热点。但是基于我国社会经济及城市化建设的发展,人们的生活环境及生活结构发生了恶性变化,许多慢性疾病随之而生,影

期刊

饮食健康功能性食品食品产业

利率市场化对商业银行的影响分析——以我国的上市银行为例

利率市场化是由金融机构根据金融市场资金供求状况和自身经营状况来自主制定和调节利率。本文将从理论方面分析利率市场化给我国商业银行的收入、资本结构、风险水平、金融创

期刊

利率市场化商业银行发展

常用的快检技术在提高食品药品快速检验中的应用分析

目的分析常用的快检技术在提高食品药品快速检验中的应用效果。方法回顾性分析2018.1-2018.6食品药品监管部门应用快检技术及普通检测技术完成的3000件食品药品检验,其中应用

期刊

常用快检技术食品药品快速检验应用分析

音频处理器的原理及使用

主要介绍音频处理器的原理、音频处理器的主要功能、音频处理器的设定与调整、音频处理器的主观评价调整以及使用等。 Mainly introduces the principle of the audio proce

期刊

音频处理器原理柔软AGC设定与调整主观评价调整

药剂科抗菌药物合理应用的管理措施分析

目的:探讨药剂科抗菌药物合理应用的管理措施。方法:选择2013年1月至2014年1月我院223张抗菌药物处方作为对照组,选择2014年2月至2015年2月我院245张抗菌药物处方作为研究组

期刊

药剂科抗菌药物合理应用

无线电磁波坑透探测技术的应用

利用无线电磁波坑透探测技术,对采煤工作面的断层、陷落柱等地质异常体进行探测,在工作面生产前准确掌握各异常体的位置、产状、切割关系等,以便采取科学、合理的生产工艺和

期刊

电磁波坑透原理探测应用

基于Copula函数的铣削表面粗糙度预测研究

回回产卜爹仇贱回——回日E回。”。回祖一回“。回干肉果幻中 N_。NH lP7-ewwe--一”＄ MN。W;- __._——————》砧叫]们羽制作:陈恬’＃陈川个美食 Back to yield

学位

智能加工Copula函数神经网络相关性切削力振动表面粗糙度

基于求解TSP问题的改进贪婪算法

与本文相关的学术论文