货郎担问题的实现.doc

货郎担问题的实现上机实践要求：题目：在计算机上求解货郎担问题和哈密顿图判定问题,并分析算法性能要求：1 以文件方式输入问题，你的程序首先读入该文件，并将结果保存在你的程序采用的数据结构中。通过编辑或者修改文件，可以改变输入的问题。 2 语言不限 3 提交实验报告。报告应该包括以下内容： a) 题目 b) 算法 c) 运行情况 d) 测试算法性能或者改善算法性能 的尝试、分析、结果 e) 认识与体会 f) 程序 一、题目：利用分枝限界法求解货郎担问题二、算法：给定一个图的代价矩阵，例如下图，找出有最小代价的周游路线。 确定解的表示形式：(X1,X2,Xn), 各顶点分别编号1,2,n, Xi表示第i步经过的顶点号。 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 三、算法：Procedure TS_reduced_matrix_LCBBBegin1 输入代价矩阵Aaij 把矩阵A归约成A1，设约数为r1 U := E:1， X :=1 C(1) :=r1 L := Currentcity(1) :=1 Citytrveled(1) :=1 While C(E) U do Begin2对1,2,nCitytraveled(E)中每个城市 j dobegin3 I:=currentcity(E) 如果属于AE 则 begin ADD(X+1); X:=X+1; parent(X):=E; currentcity(X):=jCitytraveled(X):=Citytraveled(E) j end Ax:=AE 把Ax的I行j列以及Ax(j, i)置成无穷大 归约Ax,得到约数rx C(X):=C(E)+AE(I,j) + rxend3如果L非空then begin4E:=Least(L)如果|Citytraveled(E)| = n 且 (currentcity(E),1)属于AE then begin5 ans:=E; U:=minU,rE+AE (currentcity(E),1) end5对活节点表中所有节点，如越界则删除 end4else C(E):=无穷大 end2 输出 U 输出Citytraveled(ans)end1四、三、运行情况运行环境：PII 800 256MB内存。节点较少的情况下运行速度很快。五、结果正确。输出的回路为：1、2、3、5、4、1测试算法性能或者改善算法性能的尝试、分析、结果 通过在原图代价矩阵上增加结点的方法来测试算法性能，当结点数N=5时运行速度很快在1秒以内，当N=40时，约需5秒。开始我在找代价最小的活结点，只考察了它们的代价，后来发现当有多个具有相同最小代价的节点存在时，它们会依次都被展开。这样导致活节点表的长度增长非常快，为了避免这种情况，我又增加了一个条件：找那些已经使用节点数目最多的活节点。这样不仅使速度加快同时也使得活节点表的长度不会增长得太长。这里还有一个问题：我使用的活节点表的长度定为node*node或node*node*node。不知道到底是否合适，虽然目前还没有发现任何问题。内存使用我采用动态申请，但没有及时释放，这只有通过关闭程序来释放了。六、认识与体会由于分枝限界法的时间复杂性在最坏情况下是O(n22n)，