货郎担问题的实现

贪心算法 送报线路安排 一个送报员从送报中心出发到五个小区 送报，最后要回到送报中心。 送报，最后要回到送报中心。送报中心到各 小区的距离及各小区间的距离均已知（ 小区的距离及各小区间的距离均已知（见表 问送报员应按怎样的线路行驶较好？ 1），问送报员应按怎样的线路行驶较好？ ），问送报员应按怎样的线路行驶较好 距离单位为千米） （距离单位为千米）
阶段指标函数d : 设从城市1出发，第k-1阶段到达到城市j,
ji
则城市j与下一阶段（第k阶段）的目的地城市i之间的距离为d ji 最优指标函数 fk (S, i) ：从城市1出发，经过S中k个城市,到 达城市i的最短距离.
则动态规划的顺序递推关系为:
m { fk1(S \ j, j) + d ji} in fk (S, i) = j∈S f0 (φ, i) = d1i , i = 2,3,, n, k =1,2,, n 1.
f1(S,2) = m f0 (φ,3) + d32, f0 (φ,4) + d42} in{
= m 7 + 8,9 + 5} =14, in{
* x2 ({4},2) = 4
即从城市1出发，途经1个城市去城2，应先到4，再到2。
城 城 市 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 市 1 2 3 4
当k=3时，从城市1出发，途经3个城市到达城市1的最短距离
f3({2,3,4},1) = m f2 ({2,3},4) + d41, f2 ({2,4},3) + d31, f2 ({3,4},2) + d21} in{ = m 22 + 6,18 + 5,20 + 8} = 23 in{

& 53
##########################################
!接 上 页 "
这个结论& 增量式算法只需对已聚类数据计算相似系数$ 不用计算已聚类数据之间的相似系数$ 相对其他算法而 言 $其 计 算 量 已 大 为 减 小 & 在 发 现 海 量 数 据 库 的 知 识 时 $尤 其 是 在 数 据 快 速 增 长 的 情 况 下 $利 用 本 文 所 提 出 的 增 量 式 聚 类 技 术 $不 仅 有 利 于提高聚类分析效率$ 而且有助于维护和扩充聚类结果$ 降低知识库维护的开销& 参考文献
个 城 市 排 列 # " %#$ # )’%) ! # )’!) !& & ! # )’ *) & 和 + !#$ # )’ ,*%) ! # )’ ,*!) !
,
& & ! #)’!)& ! ’"% " "!# ! 且 "% # "!# " ) ! 使 得 $ ’ ’#)’$) !#)’$ *%))*
个和第三个聚类合并#
!" $ # $ $ $ % $ & $ "’ $ (#) $ !* $ + $ , $ - $ (*) $ !(( $ (+)
第 (, 个 数 据 和 第 (* % (+ 个 类 似 $ 归 入 已 有 的 聚 类 #
!( $ # $ $ $ % $ & $ (. $ (# $ (,) $ !* $ + $ , $ - $ (*) $ !(( $ (+)
货郎担问题在运筹学中是一个著名的命题& 命题为# 有 # 个城 市 $它 们 之 间 的 距 离 已 知 & 有 一 货 郎 要 从 某 一 城 市 出 发 走 遍 所 有 城 市 $且 每 个 城 市 只 能 经 过 一 次 $最 后 回 到原处& 问如何选择路线可使他所走过的路径最短& 该命 题 亦 适 合 于 投 递 员 %配 货 车 运 送 等 问 题 & 货郎担问题的数学描述如下# 有 # 个 城 市 # $ 5! %3 $ %* $’ ’ $ %#) $ 每 个 城 市 $& 的 坐 标 为

宁夏师范学院数学与计算机科学学院
《计算复杂性分析》实验报告
实验序号：6实验项目名称：货郎担问题
学 号
13
姓 名
魏倩
专业、班级
2011级信息与计算科学
实验地点
214年6月11日
一、实验目的及要求
1.理解掌握动态规划的基本思想
2.了解货郎担问题
3.用动态规划实现货郎担问题
4.分析动态规划的时间复杂性
六、教师评语
签名:
日期： 年 月 日
成绩
d=min(k(4,2)+h(2,3),k(4,3)+h(3,2));
v=min(a+k(1,2),b+k(1,3));
l=min(v,d+k(1,4));
四、实验结果与数据分析
输入城市数目：4
n =
4
输入城市间的距离：[0 6 7 9;8 0 9 7;5 8 0 8;6 5 5 0]
k =
0 6 7 9
8 0 9 7
5 8 0 8
6 5 5 0
>> a
a =
17
>> b
b =
21
>> d
d =
19
>> v
v =
23
>>
五、分析与讨论
动态规划的实质是分治思想和解决冗余，动态规划是一种将问题实例分解为更小的，相似的字问题。其所针对的问题有一个显著的特征，即它所对应的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。动态规划在最好的情况下的时间复杂性是O（n^2），最坏的情况下是O（n^2）。此次试验不足的地方是该程序只能解决4个城市之间的问题，有待改进。

1997年9月Jour nal o f Guangx i U niver sity(N at Sci Ed)Sept.1997　求解货郎担问题的认识和实践卢怀山　黄宁恩(广西中医学院微机室,南宁,530001;第一作者43岁,男,讲师)摘　要　分析货郎担问题的解空间,用简捷的交换插入算法求解货郎担问题,并提出用求多个局部最优解的方法,然后再从中得出全局最优解.关键词　交换插入算法;多局部最优解;货郎担问题分类号　TP301.6;T P311.1货郎担问题(又称旅行商问题T raveling Salesman Problem,T SP)是一个NP难题,n城市的T SP的解有(n-1)!/2个,解空间非常的大.常用的近似算法的基本思想是从一给定解开始,构造一个产生新解的机制和一个评价函数,以控制新解的产生向着较优的方向发展,可求出局部的最优解.1　T SP的解空间及基本求解过程分析TSP的解空间,发现它是一个多维的、多局部极值的、趋于无穷大的复杂问题空间.可以形象地认为这是一个无穷大的丘陵地带,各山峰或山谷的高度即是问题的解值.而求解TSP,则是在此不能穷尽的丘陵地带中攀登以达到山峰顶或山谷底的过程.根据评价函数不同的构造方式,本质上有下列两种方法.盲目爬山法(评价函数只参考有限个邻近点)　在每一个当前步中,探索周围邻近的环境,引导搜索向着较高的方向前进,最后到达某个山顶而停止搜索.这应是与出发点相关的“附近”的山顶,但不能保证是全局最高的山顶.明目爬山法(评价函数与相当多的点有关)　首先考查有限的一大片地区,从而或隐或现地“看清”该地区的地形结构,然后控制搜索过程从出发点导向这地区的最高峰.由于上述方法中登山的路线只有一条,且不可能穷尽整个多山地区,所以只能找到与初始态及新解产生控制机制有关的局部最高点,不一定能找到全局最高点.2　多点分区搜索T SP的解空间既然只能搜索到TSP解空间某一区域的最高点,那么,如果分别搜索多个不同的区域,扩大搜索范围,能否从中得到全局最优解呢?关键是算法搜索到某个区域的最高点后,能够摆脱这个区域极值的束缚,跳到新的区域进行搜索,可以采用如下两种方法来进行多点分区搜索.遗传搜索　当搜索到一个区域最高点后,可沿原搜索路径后退一步,转向另一个方向重新搜索以期到达新的区域最高点,如此不断搜索有限个不同的区域,直至触发停止机制.然后从收稿日期:1997240广西大学学报(自然科学版)第22卷　诸个最高点中得出一个“最高”的最高点.算法的实质为单一深度优先搜索结合回溯广度优先搜索多个点的过程.但“遗传”搜索比较偏于原来的区域一隅,区域分布不够广泛.突变搜索　当搜索到一个区域最高点后,随机“突变”地跳到新的区域重新搜索.使搜索尽可能广泛地分布于整个解空间.算法的实质为初始态不同的并行单一深度优先搜索过程.也可以使用并行算法,以提高运行速度.在基本算法的基础上用提高一个数量级的办法求解多个不同的最优解,虽然也不能保证得到全局最优解,但使得到全局最优解的几率极大地增加.3　交换插入算法我们采用简单的交换插入算法求在我国31个城市之间巡游的TSP解的实践.其中的城市间距离数据取自文献[1].3.1　插入算法　在初始排列的一条城市巡游回路中,任取一个城市出来,随意地插入到序列中的另一个位置,得到一条新的巡游回路.比较这两个回路的长短,保留其中较优的回路.接着循环重复进行上述步骤,使回路序列逐渐地向优化的方向发展.具体地,取I城市出来插入到J城市后,这两个排列不同的地方在于…,I-1,I,I+1,…,J,J+1,…,…,I-1,I+1,…,J,I,J+1,….因此,只要计算城市I-1到I,I到I+1,J到J+1的三个城市距离之和,再计算城市I-1到I+1,J到I,I到J+1的另三个城市距离之和,比较这两个距离和的大小,就可以相应比较出这两条回路的长短,而不必要把两条回路的总长度都计算出来以进行比较.此算法计算量很小,每一步只须计算6个加法和1个比较,即用3个加法代替了31个加法,若巡游的城市越增多,代替的优势越明显.3.2　交换算法　在已经排列好的一条城市巡游回路中任取两个城市出来,交换它们的位置后插入回原序列中去,得到一条新的巡游回路.然后判断比较这两条回路,保留其中较优者.接着循环重复上述步骤,直至达到局部最优的巡游回路为止.这两个排列不同的地方在于…,I-1,I,I+1,…,J-1,J,J+1,…,…,I-1,J,I+1,…,J-1,I,J+1,….可见,交换算法的每一步只须计算与交换城市相关的8个加法及1个比较.在12种初始排列不同的巡游回路实验中,我们发现用插入算法运算量较少,收敛速度较快,最终得到的局部最优解好于交换算法.下面给出插入算法的T URBO BASIC程序,算法时间复杂性为O(N2)次加法、比较和O(N3)次交换排列.fo r i=1to n-1 ’循环使得插入有序,循环N2/2次fo r j=i+1to ns o=d(c(i-1),c(i))+d(c(i),c(i+1))+d(c(j),c(j+1))s n=d(c(i-1),c(i+1))+d(c(j),c(i))+d(c(i),c(j+1))if s n<s o thent=c(i) ’交换较优的排列fo r k=i to j-1: c(k)=c(k+1): nex tc (j )=t ’交换的算法时间复杂性O (N )end if nex t nex t从实验中可知,一个循环的计算往往不够,而且逆方向上的循环“插入”还可以进一步加快收敛的速度.但有限个循环以后交换就停止下来,达到局部最优解.其算法复杂性为O (N 3)次加法和比较、O (N 4)次交换排列.交换插入算法虽然简单,但实验结果很好.平均约进行4700多次比较、不到40次交换,12条巡游回路中就有2条巡游回路出现了全局最佳值15404km.而最长的巡游回路为17225km ,相差12%.可见初始态的不同,会收敛到不同的解(见表1).表1　插入算法结果初始态/km 停止解/km 交换次数 比较次数 218241540431418544273163938355803113616925586975241781646329418521628158583765105546916452795115383941648473790515904*156258372015492**154043232118318172257186019614160872432552063817156315580 *引自文献[1],**引自文献[2].全局最佳值比优化了的神经网络法和几何法求得的回路分别缩短了500km 和88km .具体的巡游回路如下:北京401呼和浩特341太原171石家庄376郑州437西安521银川346兰州192西宁1440乌鲁木齐1592拉萨1257成都641昆明434贵阳449南宁373海口455广州563长沙299武汉270南昌441福州252台北596杭州160上海269南京141合肥537济南271天津605沈阳281长春232哈尔滨1061北京4　多点搜索算法4.1　遗传多点搜索算法　以插入算法为多点搜索实验的基础,每优化前进一步,作一个标记.当搜索停止到局部最优点后,再回溯到最近标记点附近重新搜索新的局部最优点.实验中,曾发生运行陷入死循环的状况,原因为当运行到达某一局部最佳点后,退回到最近标记点附近重新搜索,经过若干次搜索又可能回到这一最佳点,好比陷入了沼泽地里.当增加跳出死循环的机制后,搜索能够正常进行.在平均进行106次比较、考查约500个局部最佳点后,有6条回路得到全局最优值.4.2　突变多点搜索算法　以插入算法为基础,当搜索到达局部最优点后.随机运行上述插入241第3期卢怀山等:求解货郎担问题的认识和实践242广西大学学报(自然科学版)第22卷　算法一次,得到一个“遗传突变”的新的巡游回路,重新运用插入算法进行新的搜索.在平均进行约5×105次比较、考查约800个左右的局部最佳点后,所有回路都达到全局最优(见表2).在“奔腾”90微机上运行时间均不超过1min.由于是有限个“多点搜索”,增加了一个数量级的运算量,算法时间复杂性为O(N4)次加法和比较.由实验可知,突变产生的“多点搜索”较遗传产生的“多点搜索”为优.表2　突变(随机产生)多点搜索结果初始态/km新解数目*最终解/km交换次数　比较次数 44273 6 15404 159 32841311361298154042057817456241785721540411264259732162817515404259953345546917161540428039859363839498515404157459948615904**90715404188174806618318148115404225094306419614691540425144562206381657154042926981366 *每条回路均进行5次试验,数据为平均值.**引自文献[1].一般的算法求解货郎担问题,不能保证得到全局最优解.本文在允许增加一个数量级运算量的条件下,尽量均匀地在整个解空间中求多个局部最优解,然后再从中得到全局最优解.参　考　文　献1　靳　蕃,范俊波,谭永东.神经网络与神经计算机.成都:西南交通大学出版社,19912　周培德.几何算法求解货郎担问题.计算机研究与发展,1995(10)3　卢怀山.交换插入算法简捷求解货郎担问题.广西民族学院学报,1996(2)Practice of Searching for a Solution tothe Travel Salesman ProblemLu Huaishan　Huang Ningen(Sectio n of Computer,G uang xi Colleg e of T raditional Chinese M edicine,Na nning,530001)Abstract　By using mo re superior alg orithm of interchange insertion method the Travel Salesman Problem is solved simply and directly.T he idea that is easier to find o ut the glo bal optim um solution by the w ay o f seeking out the partial optimum solutio n fro m solution gr oups is put forw ard.Key words　algo rithm of interchang ing and inserting;partial optimum solution o f multiple so lution g roups;T ravel Salesm an Problem(责任编辑　刘海涛)。