- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
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
结果
结果不唯一
文档评论(0)