哈密顿回路

由来

算法

由来

天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。

这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不一定是双向的。比如A→B不允许,但B→A是允许的。

换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。

算法

哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。

从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。

要满足两个条件：

1.封闭的环

2.是一个连通图，且图中任意两点可达

经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。

经过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。

平凡图是哈密顿图。

3.若以1到2、2到3、3到4、4到5、5到1，为计数规律，则各点均出现两次；这种判断方法在计算机编程运算中显得尤为重要，其会精简很多运算过程。

4.新出炉，有待检测的代码如下：

%-------输入的数据的原数据参照

% v1 v2 v3 v4 v5

%v1 0 20 1 11 2

%v2 0 0 9 1 3

%v3 0 0 0 13 8

%v4 0 0 0 0 6

%v5 0 0 0 0 0

%以上为输入数据的原数据参照

%建议所计算的数据矩阵长度为5，不会产生bug，且不会对任何计算机造成计算负担

%输入数据矩阵长度可以超过5，但是最初计算出的n个最小值中，重复次数超过2的点的种类只允许为一种

a=[0 20 1 11 2

0 0 9 1 3

0 0 0 13 8

0 0 0 0 6

0 0 0 0 0];

l=length(a)

s1=inf

zp=inf

n2=1

f=a

f(a==0)=inf

b=zeros(l)

i1=0

while i1<=l-1

[r c]=find(f==min(min(f)))

b(r(1),c(1))=f(r(1),c(1))

f(r(1),c(1))=inf

i1=i1+1

end

f1=f

[rz cz]=find(b>0)

pathz=[rz cz]

pz=[rz;cz]

p2z=zeros(2*l,1)

i2z=1

n2z=0

while i2z<=2*l

[r2z c2z]=find(pz==pz(i2z,1))

k1z=size(r2z)

if k1z(1,1)>2

p2z(r2z,1)=pz(r2z,1)

n2z=n2z+1

end

i2z=i2z+1

end

if n2z==2

HHL=b

zp=sum(sum(b))

else

while min(min(f1))~=inf

if n2>2

b=snh

end

[r1 c1]=find(b>0)

path1=[r1 c1]

p1=[r1;c1]

p2=zeros(2*l,1)

i2=1

n2=0

while i2<=2*l

[r2 c2]=find(p1==p1(i2,1))

k1=size(r2)

if k1(1,1)>2

p2(r2,1)=p1(r2,1)

n2=n2+1

end

i2=i2+1

end

[r3 c3]=find(p2>0)

p3=zeros(l,2)

i3=0

while i3<=n2-1

if r3(1)<=l

p3(r3(1),:)=path1(r3(1),:)

else

p3(r3(1)-l,:)=path1(r3(1)-l,:)

end

r3(1)=[]

i3=i3+1

end

p3(p3==0)=[]

p3=reshape(p3,n2,2)

p8=p2

[r8 c8]=find(p8>0)

p9=p8

r9=r8

i4=1

while i4<=n2

f1(p9(r9(1),1),:)=inf

f1(:,p9(r9(1),1))=inf

r9(1)=[]

i4=i4+1

end

[r4 c4]=find(f1==min(min(f1)))

f1(r4,c4)=inf

b1=b

b1(r4,c4)=a(r4,c4)

i5=1

p4=p3

while i5<=n2

b1=b

b1(r4(1),c4(1))=a(r4(1),c4(1))

b1(p4(1,1),p4(1,2))=0

p4(1,:)=[]

[r5 c5]=find(b1>0)

p5=[r5;c5]

i6=1

n6=0

while i6<=2*l

[r6 c6]=find(p5==p5(i6,1))

k6=size(r6)

if k6(1,1)>2

n6=n6+1

end

i6=i6+1

end

if n6>2

if sum(sum(b1))<s1

snh=[]

s1=sum(sum(b1))

snh=b1

end

else

if sum(sum(b1))<zp

HHL=[]

zp=sum(sum(b1))

HHL=b1

end

end

i5=i5+1

end

end

[rs cs]=find(HHL>0)

minpaths=[rs cs]

journeys=zp

注：这段代码采用分支定界法作为编写程序的依据，因此代码依旧局限在算法上；而且代码的使用对所要计算的数据是有要求的，如下：

1.只要数据在开始计算出的n个最小值中，其重复次数超过2次的点的种类只能为一种，例如：代码段中的数据五个最小值中其重复次数超过2次的点只有v5。

2.数据矩阵格式要求：只允许为上三角矩阵，不支持全矩阵以及下三角矩阵的运算。

3.代码扩展方法请使用者独立思考，不唯一。

4.运算数据扩展方法，请使用者独立思考，不唯一。

5.此代码为本人毕设的附加产品，不会对使用此代码者，因理解不当或使用不当而造成的任何不良后果，付出任何责任。

6.代码仅供交流。