最小hamilton圈问题的求解新方法

《最小hamilton圈问题的求解新方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第24卷第2期华侨大学学报(自然科学版)Vol.24No.22003年2月JournalofHuaqiaoUniversity(NaturalScience)Apr.2003文章编号100025013(2003)0220194207最小Hamilton圈问题的求解新方法张银明(华侨大学信息科学与工程学院,福建泉州362011)摘要最小Hamilton圈可以用于求解货郎担问题,但至今没有一种有效的求解最小Hamilton圈的方法.文中提出元素判别值分配法是求解该问题的一个有效方法,可将其应用于求解最小Hamilton圈的算法设计.关键词Hamilton圈,元素判别值分配法,算法设

2、计中图分类号O22文献标识码A运筹学中的货郎担问题是一个引起诸多学者兴趣并进行研究的问题.对它的求解,已提出不少有效的方法.其中一种著名的求解方法,就是通过求一条总权最小的Hamilton圈或称最〔1〕小H2圈的方法.然而到目前为止,对于这个问题仍没有一个有效的算法.由Lin,Held和〔1〕Karp提出的近似解法在对所举的例子进行求解时,需要做3次调整,方能得到最优通路.如〔2～3〕果使用元素判别值分配法求解最小H2圈,只需一次分配便可获最优方案,无须调整.因此,它是求解哈密尔顿最优通路的有效新方法,有其独特的创新性.1运筹学的货郎担问题运筹学的货郎担问题一般可叙述为,有n个

3、地点Ai,从Ai到Aj的耗费(时间、单位运费、距离及其它耗费)为Cij,其中i,j=1,2,⋯,n.要求耗费最小的调配方案,可归结成线性规划问题.假设Xij表示Ai到Aj的调配待定变量,不妨称为元素,则其数学模型可表示为nnminZ=22Cij,(1)i=1j=1约束条件为n2Xij=n,j=1,2,⋯,n,(2)i=1n2Xij=n,i=1,2,⋯,m,(3)j=11从Ai城到Aj城(该元素得到调配或被选上),Xij=(4)0不从Ai城到Aj城(该元素得不到调配或未被选上).这类问题的调配可使用一般形式的调运分配表.对于货郎担或排序问题,是一般调运问题的特例,即m=n.因而,

4、可简单地表示成调配分配图,如图1所示.收稿日期2002210210作者简介张银明(19392),男,教授第2期张银明:最小Hamilton圈问题的求解新方法195Cij=Cji是对称的货郎担问题,而Cij≠Cji则是不对称的货郎担问题.Cij所在格子的对应待〔4〕定变量Xij,称为元素.此类问题可使用元素判别值分配法求解.图1货郎担问题一般调配分配图1.1元素判别值的数学模型〔5〕计算Xij的元素判别值的数学模型为(m-1)(n-1)dXij=2fs(△Xij)=s=1mn22fs(Cij-Ci,j+k+Ci+l,j+k-Ci+l,j),(5)i=1j=1其中1-i≤l≤m-i

5、且l≠0,1-j≤k≤n-j且k≠0,△Xij=Cij-Ci,j+k+Ci+l,j+k-Ci+l,j为元素Xij的矩形回路检验数.i=1,2,⋯,m,1-i≤l≤m-i且l≠0,j=1,2,⋯,n,1-j≤k<≤n-j且k≠0.而fs(△Xij)是如下的定义函数.即1,当△Xij<0,fs(△Xij)=(6)0,当△Xij≥0.对一般具有m×n阶调配平衡表中,含有m×n个元素.每个元素以它为顶点的矩形回路计有(m-1)(n-1)个,因而其判别值dXij∈[0,(m-1)(n-1)].按照元素判别值进行调配的求解方法,称为元素判别值分配法.1.2元素Xij的总检验数计算模型元素X

6、ij所有矩形回路的检验数之和,称为元素Xij的总检验数.记作ZXij.其总检验数的数学模型为mnZXij=2$Xij=22(Cij-Ci,j+k+Ci+l,j+k-Ci+l,j),(7)i=1j=1其中1-i≤l≤=m-i且l≠0,1-j≤k<≤n-j且k≠0.1.3元素判别值分配法的调配原则〔2〕对原来元素判别值分配法的调配基本原则,经过求解问题的检验,原第3条分配原则必〔3〕须进行修改,以保证一次调配便可获得最优解.现将完善后的货郎担问题求解的调配原则进行叙述.196华侨大学学报(自然科学版)2003年原则1判别值越大,其分配的优先级越高.原则2当对某元素Xij进行分配或选

7、上后,则将该元素置为Xij=1,并将它的对应元素Xji标上‘×’(不允许出现Xij2Xji回路),且将该元素所的i行及j列标上记号‘<’.原则3若有多个元素的判别值相同,则元素总检验数小的先分配.如果元素总检验数也相同,则耗费小的优先分配,再按下标的顺序进行分配.原则4当某行或某列已经具有标记‘<’或某元素含有‘×’时,那么处于该行或该列的元素及标记为‘×’的元素,不论判别值多大,皆已失去分配权.1.4对角线上元素耗费值的设置货郎担(或旅行商)问题是一般调配问题的特例,即M=N.而且,因为不