数学建模常用Matlab/Lingo/c代码总结系列——hamilton回路

原创 2011年11月20日 00:20:21
  提供一种求解最优哈密尔顿的算法---三边交换调整法,要求在运行jiaohuan3(三交换法)之前,给定邻接矩阵C和节点个数N,结果路径存放于R中。
  bianquan.m文件给出了一个参数实例,可在命令窗口中输入bianquan,得到邻接矩阵C和节点个数N以及一个任意给出的路径R,,回车后再输入jiaohuan3,得到了最优解。

由于没有经过大量的实验,又是近似算法,对于网络比较复杂的情况,可以尝试多运行几次jiaohuan3,看是否能到进一步的优化结果。


%%%%%%bianquan.m%%%%%%%
N=13;
for i=1:N
    for j=1:N
        C(i,j)=inf;
    end
end
for i=1:N
    C(i,i)=0;
end
C(1,2)=6.0;C(1,13)=12.9;
C(2,3)=5.9;C(2,4)=10.3;
C(3,4)=12.2;C(3,5)=17.6;
C(4,13)=8.8;C(4,7)=7.4;
C(4,5)=11.5;
C(5,2)=17.6;C(5,6)=8.2;
C(6,9)=14.9;C(6,7)=20.3;
C(7,9)=19.0;C(7,8)=7.3;
C(8,9)=8.1;C(8,13)=9.2;
C(9,10)=10.3;
C(10,11)=7.7;
C(11,12)=7.2;
C(12,13)=7.9;
for i=1:N
    for j=1:N
        if  C(i,j) < inf
            C(j,i)=C(i,j);
        end
    end
end
for i=1:N
    C(i,i)=0;
end

R=[4 7 6 5 3 2 1 13 12 11 10 9 8];
%%%%%%%%jiaohuan3.m%%%%%%%%%%
n=0;
for I=1:(N-2)
    for J=(I+1):(N-1)
        for K=(J+1):N
            n=n+1;
            Z(n,:)=[I J K];
        end
    end
end
R=1:N
for m=1:(N*(N-1)*(N-2)/6)
    I=Z(m,1);J=Z(m,2);K=Z(m,3);
    r=R;
    if J-I~=1&K-J~=1&K-I~=N-1
        for q=1:(J-I)
            r(I+q)=R(J+1-q);
        end
        for q=1:(K-J)
            r(J+q)=R(K+1-q);
        end
    end
    if J-I==1&K-J==1
        r(K)=R(J);r(J)=R(K);
    end
    if J-I==1&K-J~=1&K-I~=N-1
        for q=1:(K-J)
            r(I+q)=R(I+1+q);
        end
        r(K)=R(J);
    end
    if K-J==1&J-I~=1&K~=N
        for q=1:(J-I)
            r(I+1+q)=R(I+q);
        end
        r(I+1)=R(K);
    end
    if I==1&J==2&K==N
        for q=1:(N-2)
            r(1+q)=R(2+q);
        end
        r(N)=R(2);
    end
    if I==1&J==(N-1)&K==N
        for q=1:(N-2)
            r(q)=R(1+q);
        end
        r(N-1)=R(1);
    end
    if J-I~=1&K-I==N-1
        for q=1:(J-1)
            r(q)=R(1+q);
        end
        r(J)=R(1);
    end
    if J==(N-1)&K==N&J-I~=1
        r(J+1)=R(N);
        for q=1:(N-J-1)
            r(J+1+q)=R(J+q);
        end
    end
    if cost_sum(r,C,N)<cost_sum(R,C,N)
        R=r
    end
end
fprintf('总长为%f\n',cost_sum(R,C,N))

%%%%%%cost_sum.m%%%%%%%%function y=cost_sum(x,C,N)y=0;for i=1:(N-1) y=y+C(x(i),x(i+1));endy=y+C(x(N),x(1));




0-1整数规划的LINGO求解

1.LINGO简介     LINGO是由美国LINDO公司推出的求解优化模型的软件,LINGO是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。官方提供免费试用版,可以在其官网...
  • Mr_Grit
  • Mr_Grit
  • 2015年05月08日 19:12
  • 4379

简学LINGO(三)——实例篇

1. 装配线平衡模型 一个
  • yzu_120702117
  • yzu_120702117
  • 2014年08月10日 11:26
  • 2175

Lingo超经典案例大全

Lingo超经典案例大全 LINGO是Linear Interactive and General Optimizer的缩写,即“交互式的线性和通用优化求解器”。Lingo超强的优化计算能力...
  • u012717411
  • u012717411
  • 2014年09月03日 17:31
  • 1344

数学建模常用Matlab/Lingo/c代码总结系列——灰色预测

clear clc X=[136 143 165 152 165 181 204 272 319 491 571 605 665 640 628]; x1(1)=X(1); X1=[]; for i=...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月18日 12:47
  • 3566

数学建模常用Matlab/Lingo/c代码总结系列——最小费用最大流问题

例 19(最小费用最大流问题)(续例18)由于输油管道的长短不一或地质等原因, 使每条管道上运输费用也不相同,因此,除考虑输油管道的最大流外,还需要考虑输油 管道输送最大流的最小费用。图 8 所示...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月17日 12:56
  • 6548

数学建模常用Matlab/Lingo/c代码总结系列——floyd最短路径

例 9   某公司在六个城市 c1,c2, …c6 中有分公司,从 i ci 到 cj的直接航程票价记在下述矩阵的 (I,j) 位置上。(∞表示无直接航路),请帮助该公司设计一张城市c1 到其它城市...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月16日 23:37
  • 4941

数学建模常用Matlab/Lingo/c代码总结系列——插值拟合

相关知识 在生产和科学实验中,自变量 与因变量 间的函数关系 有时不能写出解析表达式,而只能得到函数在若干点的函数值或导数值,或者表达式过于复杂而需要较大的计算量。当要求知道其它点的函数值时,需要估...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月18日 12:39
  • 2642

数学建模常用Matlab/Lingo/c代码总结系列——旅行商TSP问题

Lingo代码: MODEL: SETS: CITY / 1.. 6/: U; ! U( I) = sequence no. of city; LINK( CITY, C...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月17日 13:06
  • 4466

数学建模常用Matlab/Lingo/c代码总结系列——参数估计

Matlab中用fminsearch实现参数估计  文章的主要思想来源于Matlab|Simulink仿真世界的一篇类似的文章。我这里把这个思想引入到我们的体系来,并以一个新的例子讲解这一用...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月18日 12:34
  • 2740

数学建模常用Matlab/Lingo/c代码总结系列——Matlab图形绘制函数汇总

基本绘图和图形 box 坐标轴边界 errorbar 沿曲线绘制误差条 hold 在图形窗口中保留当前图形 ...
  • xiangshimoni
  • xiangshimoni
  • 2011年11月20日 00:16
  • 4173
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:数学建模常用Matlab/Lingo/c代码总结系列——hamilton回路
举报原因:
原因补充:

(最多只允许输入30个字)