Զѧ
AGTA AUTOMATICA SINICA
1999 25 2 Vol.25 No.2 1999



TSPֲ㷨ĸӶо1)
¬ܴ
ؼʡTSPֲ㷨̬࣬㸴Ӷ.
COMPLEXITY ANALYSIS OF THE MULTI-LAYERED
CLUSTERING ALGORITHMS IN TSP
LU XinLI Yanda
(Department of Automation, Tsinghua University, Beijing100084)
Key wordsTraveling salesman problem(TSP), local search algorithm, multi-layered clustering, complexity of computation.
1TSP⼰򻮷㷨
TSP(traveling salesman problem)ѱ֤NP⣬еŻ㷨֧硢̬滮Ž⣬Ҫģָʱ12.ģʱڼʱƶɥʧԣֻһĲԶԽռʽںʱڵõһ.Ƚ㷨ʱҪԽԼʱΪ׼3.
TSPУĽṹȫɳ֮ԾDij(i,j=1,,N).ˣþϢоΪһЩСͿԽֽ⣬㷨Ч.
ģʱͨ򻮷֣ʹÿһεģһķΧڣĸӶ.⣬òмʵTSPֲŻ临ӶԼ¸ӶȵԭҲԵı仯Ӷ㷨оָͬķ.
2ֲ̬ģTSP⼰ܷ
㷨ɼ£
1) СԤȸĿֱӵþֲ㷨.
2) лΪPPģþֲ㷨һPĵ·.
3) ÿһ·ϵڵΪ̶㣬ݹöֲ̬㷨.
NģTSP⣬һƾֲ㷨ļ㸴ӶȲO(N2)ƻۣ123.
һNCֵ໮֣㷨ӶȹΪO(N)P估Pڷֱþֲ㷨Ѱţ൱ڽһPģP(NP)ģTSP.ԣԾֲ㷨ļ㸴Ӷ½֤һλ֣NTSPΪPʱоȷֲÿһеĿȣ㸴ӶȹƲ

(1)
Թ̶ĿPkλʱ㸴ӶȹƲ

(2)


(3)
ѻֲk

(4)
logPNΪʱȡk=logPN-1ʱ

(5)

(6)
Nʱ
(7)
k㻮ֺ㷨ļ㸴ӶȹΪ

(8)
ֲ㷨ȣ㸴ӶȽO(NlnN).ģԽ㷨ЧʸĽԽ.
3ʵ
һ̨Pentium 166 PCзʵ.ʱڲͬʵֻ¿ܻнϴ𣬵㷨ԱȽϻ.
Զֲ̬Ż㷨˷о.һCHN144ʵһɣȷֲTSP.ÿη10ÿ20УÿϷֱִ10(̬10)100(̬100)ֲ㷨.ͬʱҲִ˾ֲ㷨֮Ƚϣÿֻһ.
1ǶCHN144⣬ÿ㷨ִ100ΣȡƽֵŵĽԱ.
1CHN144ʱȽ

㷨ƽ
ʱ()(km)(%)ʱ()(km)(%)
̬10040.11032 01394.946.90132 83592.5
̬102.47332 41293.73.35133 33791.1
ֲ40.93432 08994.752.02233 11391.7


ӱ1пԿ㷨õĽ൱ҪĲʱ.ڶ̬100ÿִ100ֲ㷨ִֻһΣԣ̬෽ٶǾֲ㷨ĴԼ100ٶߵĻǺ.
2ǶɣȷֲTSP.ֻǱȽ϶ֲ̬㻮ַڸģµļٶȣ֤㸴ӶȵĹ.ȽõǶ̬10ķ144ģǱ1еCHN144⣬ÿģʮɵʵÿʵѰ100ΣģѰٶȵǰķ.
2ͬģ¶̬෽ļʱȽ

ģ()ƽ()()
1001.2641.5271.648
1442.4733.3513.901
1 00015.54916.31817.640
10 000230.752237.812252.589


4㷨Ĳʵּ临Ӷо
ڴģTSPĶֲ̬Ż㷨һʽʵʽ㸴Ӷ.
ֲ̬Ż㷨У߲򻮷ֺ󣬵Ͳÿ·Ѱʵֻ꣬һϢڸ߲򻮷ֹлõ.ԣͲÿ֮Ѱ໥޹صģԺ׵ʵֲд.

ͼ1ֲ̬Ż㷨Ĳʵֽṹͼ
㷨ĲʵһPʽ.ڵNе򻮷֣PָڶPڵͬиѰ.Pڵһ򻮷֣·ֽ.㷨ʱPҶڵ㣬ͿԽյĽ·.ĵķв㷨ĸӶȷԿNΪk=logPN-1ʱ㸴ӶȿԱʾΪ

(9)
ڼ㸴ӶҪɶ̬㷨ֲ㷨ӰԱ˴Ҫ.Ҳʹоصת˶̬㷨.ѰҸЧľ㷨㷨Ĳʵ֣Խһ㷨ӶȣΪһоķ.
1)ȻѧĿ.
߼飺¬1996ҵ廪ѧѧʿѧλ.Ϊ廪ѧԶϵʿ.оȤΪϢѧܼŻ㷨.
ܴ廪ѧԶϵڡϢѧԺԺйѧԺԺʿ.ڴϢѧźŴͼۼӦõо.
ߵλ廪ѧԶϵ100084
ο
1Johnson D S, Papadimitriou C H, Yannakakis M. How easy is local search?J. Comput. Sys.Sci.198837(1)79100
2Papadimitriou C H, Yannakakis M. Optimization, Approximation and complexity classes. J. Comput. Sys. Sci.199143(3)425440
3Ausiello G, Protasi M. Local search, reducibility and approximability of NP-optimization problem.Information Processing Letters,199554(2)7379
ոڡ1997-04-09
޸ĸڡ1998-04-28
