Hamilton圈问题.pdf

Hamilton 圈问题 Hamilton 圈：包含图G(V , E) 中所有顶点的圈。 例 下图是包含10 个顶点的图，各个顶点之间的距离见 下表。现要找一条最短的Hamilton 圈。 最短Hamilton 圈的数学表达式 设dij 为顶点i 到顶点j 的距离，xij 1表示边(i, j)在所求路 上，xij 0表示边(i, j) 不在所求路上。 min  d x ij ij ( , ) i j E s.t . xij 1, i 1,10;  j V xji 1,i 1,10;  j V u u (n 1) n * x     i j ij u 0 i u 0 j (i, j 2,3, , n;) LINGO 程序求解 model : sets: cities/1..10/:u; link(cities, cities): d,x; endsets data: d = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=@size(cities); min=@sum(link(i,j): d(i,j)*x(i,j)); @for(cities(i): @sum(cities(j)|j#ne#i: x(j,i))=1; @sum(cities(j)|j#ne#i: x(i,j))=1; ); @for(link(i,j)|i#ne#1 #and# j#ne#1:u(i)-u(j)=n-1-n*x(i,j)); @for(link : @bin(x)); end 结果 结果不唯一