货郎担问题的实现

《货郎担问题的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、货郎担问题的实现上机实践要求：题目：在计算机上求解货郎担问题和哈密顿图判定问题,并分析算法性能要求：1以文件方式输入问题，你的程序首先读入该文件，并将结果保存在你的程序采用的数据结构中。通过编辑或者修改文件，可以改变输入的问题。2语言不限3提交实验报告。报告应该包括以下内容：a)题目b)算法c)运行情况d)测试算法性能或者改善算法性能的尝试、分析、结果e)认识与体会f)程序一、题目：利用分枝限界法求解货郎担问题二、算法：给定一个图的代价矩阵，例如下图，找出有最小代价的周游路线。确定解的表示形式：(X1,X2,…,Xn),各顶点分别编号1,2,…,n,Xi表

2、示第i步经过的顶点号。∞254031275∞1730251915∞6195024∞6228710∞三、算法：ProcedureTS_reduced_matrix_LCBBBegin1输入代价矩阵A[aij]把矩阵A归约成A1，设约数为r1U:=∞E:＝1，X:=1^C(1):=r1L:=ΦCurrentcity(1):=1Citytrveled(1):=1While^C(E)属于AE则beginADD(X+1)

3、;X:=X+1;parent(X):=E;currentcity(X):=jCitytraveled(X):=Citytraveled(E)∪{j}endAx:=AE把Ax的I行j列以及Ax(j,i)置成无穷大归约Ax,得到约数rx^C(X):=^C(E)+AE((I,j))+rxend3如果L非空thenbegin4E:=Least(L)如果

4、

5、Citytraveled(E)

6、

7、=n且(currentcity(E),1)属于AEthenbegin5ans:=E;U:=min{U,rE+AE(currentcity(E),1)}end5对活节点表中所有节点

8、，如越界则删除end4else^C(E):=无穷大end2输出U输出Citytraveled(ans)end1四、三、运行情况运行环境：PII800256MB内存。节点较少的情况下运行速度很快。五、结果正确。输出的回路为：1、2、3、5、4、1测试算法性能或者改善算法性能的尝试、分析、结果通过在原图代价矩阵上增加结点的方法来测试算法性能，当结点数N=5时运行速度很快在1秒以内，当N=40时，约需5秒。开始我在找代价最小的活结点，只考察了它们的代价，后来发现当有多个具有相同最小代价的节点存在时，它们会依次都被展开。这样导致活节点表的长度增长非常快，为了避免这

9、种情况，我又增加了一个条件：找那些已经使用节点数目最多的活节点。这样不仅使速度加快同时也使得活节点表的长度不会增长得太长。这里还有一个问题：我使用的活节点表的长度定为node*node或node*node*node。不知道到底是否合适，虽然目前还没有发现任何问题。内存使用我采用动态申请，但没有及时释放，这只有通过关闭程序来释放了。六、认识与体会由于分枝限界法的时间复杂性在最坏情况下是O(n22n)，由实验结果知，当N增大时，所需运行时间增加很快。在这种解决NP问题的程序中，我认为设计一种合适的算法与如何合理利用计算机资源同样非常重要。七、程序