ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



ȷ˻㷨*
1֣γ112
ժҪȷ˻෽Ӧ,һʽ㷨.÷ɢģתΪģȥ,ͨһϵ¶ȱ仯ϵͳܺľֲСĽ,һ򵥵ʽʽ.,㷨.
ؼʡȷ˻,,,ԭ.
ͼšTP18
An Algorithm for Travelling Salesman Problem Using Deterministic Annealing
YANG Guang-wen1ZHENG Wei-min1WANG Ding-xing1LI Xiao-ming2
AbstractIn this paper, the deterministic annealing and clustering algorithms are applied to the travelling salesman problem, and a heuristic algorithm for the travelling salesman problem is put forward. The method transforms the discrete model of the travelling salesman problem into the continuous model, and the solution of the problem is obtained by solving local optimal solution of a series of problems to minimize the free energy of a physical system which varies with temperature. A simple explicit iterative formula is given. The computation results indicate that this algorithm has good performance.
Key wordsDeterministic annealing, travelling salesman problem, clustering, the principle of maximum entropy.
TSPtravelling salesman problemһͼ.һΪNPѽ,ŽǷǳѵ,ĿǰûʮЧķ.
Ȼ㡰Ȼѧе˼뷽䴫ͳӦ֮,ԭ˼뷽ıȡ,ڽе⡱,Ϊ⸴ϵͳṩеļ㷽.1ΪһҪ֧,ȷ˻K.Roseʿģ2,˻,ŻŵתΪһϵ¶ȱ仯ϵͳܺļС.Ͻ,ܹʹ㷨ֲܿСõȫּС,йӦǰ.Ľȷ˻ӦTSP,һʽ㷨.
1ȷ˻
һϵͳ,ۻ,¶½㹻ʱ,ÿһ¶,ϵͳﵽƽ̬,¶Ⱥܵʱ,ȫ,ϵͳﵽ̬.ÿһ̶¶,ϵͳȡļСֵӦϵͳƽ̬,ϵͳԷƽ̬.ȷ˻ǻ˻һ.
һС
minE=E(x),(1) 
E(x)ɿĳһϵͳ.ĳһ¶,ϵͳ״̬ı仯ǳܼٵķ,ϵͳﵽƽ̬ʱ,ܺﵽС.ϵͳ(ʽ(1))ӦܺF(x,T).ܺF(x,T):T=ʱ,F(x,T)xȫּСT=0ʱ,F(x,T)=E(x).Ϊȷ˻ܺҪ.ȷ˻,ϵͳT=T+TʱܺС״̬xmin(T+T)Ϊʼ,ͨminF(x,T)ļСģϵͳﵽƽ̬Ĺ.ܺΨһ,ιʵܺҪĹؼ.
2ȷ˻ģ͵TSP
X={x1,x2,...,xN}Ϊһģʽ,ΪY={yT1,yT2,...,yTM}V={vxj},ʹD(Y,V)=xjd(x,yj)С,yjΪjCjĴԪ,d(x,yj)Ϊxyjľ.VΪΪϷ,һx,Ψһ.
,M=N,XеÿһΪһ.ټʹd(yj-1,yj)С(y0=yN),ͨTSP.
minD(Y,V)=xjd(x,yj)+d(yj-1,yj),(2)
Xм.ŽY={yT1,yT2,...,yTN}ӦTSPһŽ.xiyjӦ,xiΪۻԱߵĵj.˿Ǳ仯Ļȷ,ʾʽе2Ҫ̶.
ȷ˻(2).
Ӧ(2)һܺ.¶T,涨YV,ƣY,V}Ϊһʵ,P(Y,V)ʾʵY,Vֵĸ.
E={Y,V}P(Y,V)D(Y,V),(3)
ȡغΪH=-{Y,V}P(Y,V)lnP(Y,V),üԭP(Y,V)=.Ц¡ʽ(3)ȷ.ʹP(Y,V)ȡ(Y,V)Ϊɼʵ.P(Y,V)ıԵֲ

F(Y,)=lne-d(x,yj),g(Y)=d(yj-1,yj),ɵ

(Y,)=F(Y,)+g(Y),ʹP(Y)ȡYΪɼṹ.P(Y)ȼڼС(Y,).(Y,)Ϊʽ(2)Ӧϵͳܺ.
3TSPһʽ㷨
ȡ,ٶd(x,y)yΪ͹,򵱦=0ʱ,(Y,0)=(1)/(N)d(x,yj)YΪ͹,ɴͳŻ,ȫŵ.¡ʱ,(Y,)=xjd(x,yj)+g(Y)=D(Y,V).ɼ,(Y,)Ϊܺ,ȷ˻Ҫ.ǰTSPתΪ¶ȱ仯ܺļС⣺
min(Y,)=F(Y,)+g(Y).
ȡd(x,y)=x(i)-y(i)2,ŽһױҪʽ
4 
,ɸTSPһʽ㷨.
(1) 0=0,min(Y,0)ŵΪYmin(0)=(y*T1,y*T2,...,y*TN)T,y*1=y*2=...=y*N=(1)/(N)xx,xһ,k=0
(2) Ӧ,k+1=(k)(Ϊһ,k+1k),Ymin(k)Ϊʼmin(Y,k+1),ɰʽ(4)е,ŵΪYmin(k+1)
(3) ֹ׼,ֹͣ,Ymin(k+1)ӦTSPһ;,k=k+1,ת(2).
Ϊһʽ㷨,ֱϽ㷨TSPȫ.Ϊ³ִʱ,ÿһΪһ,¡ʱ,(Y,)ĵ1Ϊ0,2Ϊ·.
ʽ㷨һЩģ,Сⶼɷ·,һЩ޹Ĵ,ܲѡȡӰܴ.ģ˻㷨,ѡȡʵ,ͬ¶ȿƷʽֹͬ,㷨ģ˻㷨.
4ᡡ
ĸTSPһʽ㷨,ȷ˻,TSPɢģתΪģȥ,һ򵥵ĵʽ,TSP;.,µı仯ѡȡֱӰ㷨.µı仯ٶȿ,㷨ٶȿ,ܿܲ֮,㷨ļ,ܱȽϺ.Щдһо.,ڹ̶һ,ͨɸѡ,ܿҵʵĲ.㷨˼һ,һЩѽ.
оõƼԤл.
߽ܣ,1963,ʿ,,ҪоΪֲϵͳ,д,㷨.
֣γ,1946,,ʿʦ,ҪоΪ/ֲ.
,1937,,ʿʦ,ҪоΪ/ֲ.
,1957,ʿ,,ʿʦ,ҪоΪм.
ͨѶϵˣ, 100084,廪ѧѧ뼼ϵ
1997-10-20յԭ,1998-01-19յ޸ĸ
ߵλġ֣γˡ廪ѧѧ뼼ϵ100084
ѧѧ뼼ϵ100871
E-mail: ygw@est4.cs.tsinghua.edu.cn
ο
1Fox G C. Physical computation. Concurrency: Practice and Experience, 1991,3(6):627653
2Rose K, Gurewitz E, Fox G C. Statistical mechanics and phase transitions in cluster. Physical Review Letters, 1990,65:945948
1997-10-20յԭ,1998-01-19յ޸ĸ 
