旅行商问题的一种启发式算法.pdfVIP

第 35 卷第 2 期 河 海 大 学 学 报 ( 自 然 科 学 版 ) Vol . 35 No . 2 ( ) 2007 年 3 月 Journal of Hohai University Natural Sciences Mar . 2007 旅行商问题的一种启发式算法 1 2 1 洪玉振 ,张际东 ,李 　明 ( 1. 河海大学商学院 ,江苏 南京 　210098 ; 2 . 河海大学外国语学院 ,江苏 南京 　210098) 摘要 :用一个有向图表示旅行商避开某一城市到 1 个顶点的所有最短路径, 并在每条弧上定义一个 线性表, 用以记录所有包含该弧的图, 从而将判断某条弧和某个顶点是否应该存在于某个子图中的 最短路径上的问题转化为线性表的相关操作, 进而讨论了图上的弧都在某一最短路径上的充要条 件, 以及如何顺序产生第 1 列到第 n 列的顶点上的图, 如何从这些图上有哪些信誉好的足球投注网站出近似最优解的方法. 关键词 :旅行商问题 ;最短路径 ;有向图;启发式算法 ( ) 中图分类号 :O224 　　　文献标识码 :A 　　　文章编号 :1000 1980 2007 020229 04 本文沿用文献[ 1] 的符号和定义. 在文献[ 1] 的图 1 中, 每个顶点 v ( p k) 上用一个图来表示旅行商避开一 个被访问城市 p n 到它的所有最短路径. 已知第 k - 1 列上的图, 根据文献[ 1] 提供的最短路径的必要条件, 确 定第 k 列上的图, 重复这一步骤, 求出第 n 列上的图. 显然, 这涉及动态规划的思想. Bellman 等[23] 运用动态规划原理讨论了旅行商的路径优化问题. Clientsov 等[46] 研究了路径问题中的离散连续优化方法的应用. Chentsov 等[4 , 8] 分析了动态规划应用于 TSP 路径优化 的过程. 以上提及的动态规划在 TSP 方面的应用基于 Bellman 的最优性原理 ,而本文探讨的 TSP 算法依据 文献[ 1] . 1 　图和弧上的线性表 1. 1 　图 G ( v ( pk) r 1 , r2 , …, r g) 的定义 用图 G( v ( p k) r1 , r2 , …, rg) 来表示旅行商避开城市 r1 , r2 , …, rn 到 v ( p k) 的全部最短路径, 定义它为 2 个符号集合 :顶点的集合 Ω( v ( p k) r1 , r2 , …, rg) 和弧的集合 A ( v ( p k) r1 , r2 , …, rg) , 即 ( ( ) ) ( Ω( ( ) ) ( ( ) ) ) ( ) G v p k r1 , r2 , …, rg = v p k r1 , r2 , …, rg , A v p k