基于霍夫曼树的TSP求解算法
发明专利申请公布后的视为撤回
摘要
本发明公开了一种基于霍夫曼树的TSP求解算法，它是一种启发式算法，其目标是快速寻找TSP的高质量的近优解。本发明整个算法分为两部分：算法的第一部分是根据TSP实例建立一棵霍夫曼树；算法的第二部分是根据霍夫曼树逐步建立TSP路径。该求解算法的解的质量略高于边交换法，远高于最邻近法(贪婪法)和最接近插入法；运算速度略低于最邻近法(贪婪法)和最接近插入法，与边交换法的3边交换算子相当，高于元启发式法；编程的复杂性略高于最邻近法(贪婪法)、最接近插入法和边交换法的3边交换算子，低于元启发式法；本算法都能求得较高质量的解，用该算法对几个城市数为数千的TSP实例求解结果，高出最优解5％左右。
基本信息
专利标题 ：
基于霍夫曼树的TSP求解算法
专利标题（英）：
暂无
公开（公告）号 ：
CN1873671A
申请号 ：
CN200610024167.7
公开（公告）日 ：
2006-12-06
申请日 ：
2006-02-27
授权号 ：
暂无
授权日 ：
暂无
发明人 ：
徐伯庆孙国强
申请人 ：
上海理工大学
申请人地址 ：
200093上海市杨浦区军工路516号
代理机构 ：
上海申汇专利代理有限公司
代理人 ：
吴宝根
优先权 ：
CN200610024167.7
主分类号 ：
G06Q10/00
IPC分类号 ：
G06Q10/00
IPC结构图谱
G
G部——物理
G06
计算；推算或计数
G06Q
专门适用于行政、商业、金融、管理、监督或预测目的的数据处理系统或方法；其他类目不包含的专门适用于行政、商业、金融、管理、监督或预测目的的处理系统或方法
G06Q10/00
行政；管理
法律状态
2011-01-12 ：
发明专利申请公布后的视为撤回
号牌文件类型代码 : 1603
号牌文件序号 : 101061480425
IPC(主分类) : G06Q 10/00
专利申请号 : 2006100241677
公开日 : 20061206
号牌文件序号 : 101061480425
IPC(主分类) : G06Q 10/00
专利申请号 : 2006100241677
公开日 : 20061206
2007-01-31 ：
实质审查的生效
2006-12-06 ：
公开
注：本法律状态信息仅供参考，即时准确的法律状态信息须到国家知识产权局办理专利登记簿副本。
文件下载
暂无PDF文件可下载
