度約束最小生成樹(shù)算法.pdf

1、西安電子科技大學(xué)碩士學(xué)位論文度約束最小生成樹(shù)算法姓名：焦森林申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：劉紅衛(wèi)20080101A b s t r a c tW el i v e i n an e t w o r k s o c i e t y ．I n as e n s e ，m o d e r n s o c i e t y i s ac o m p u t e ri n f o r m a t i o nn e t w o r k ，

2、t e l e p h o n ec o m m t m i c a t i o n sn e t w o r k ，t r a n s p o r tn e t w o r k ，e n e r g ya n dm a t e r i a l d i s t r i b u t i o n n e t w o r k a n do t h e r n e t w o r kc o m p o n e n t s o ft h e c

3、o m p l e xn e t w o r k s y s t e m ．N e t w o r k O p t i m i z a t i o n i s t h e s t u d y o f h o we f f e c t i v e p l a n n i n g ，m a n a g e m e n ta n dc o n t r o lo f t h en e t w o r ks y s t e m ．M a k ei

4、 t t o m a x i m i z et h es o c i a la n de c o n o m i cb e n e f i t s ．T h e d e g r e e - c o n s t r a i n e d m i n i m u ms p a n n i n g t r e e p r o b l e m i s ac o m m o n n e t w o r ko p t i m i z a t ／o n

5、p r o b l e mI nt h e r e a lw o r l d ，h a v em a n ye x a m p l e so f t h i s ．S u c h a s ：c i r c u i td e s i g n , p i p e l i n el a y i n g ，c o m p u t e r n e t w o r k s ，c o m m u n i c a t i o n ss y s t e

6、m s ，a n dS O0 1 1 ．H o wt o s o l v et h ec o n s t r a i n tn e t w o r km i n i m u m s p a n n i n gt r e ep r o b l e mh a sb e c o m e a g o o d r e s e a r c h t o p i c ．1 1 l em a i n W O r ks u m m a r i z e d

7、a sf c I l l o w s ：I nc h a p t e rt w o ，w eh a v ea s i n g l ep o i n to f t h e c o n s t r a i n e dm i n i m u m s p a n n i n gt r e ep r o b l e mw a s s t u d i e d ．F i r s t , w ep r o p o s e dt h el a r g e

8、 s ts i n g l ep o i n to f m i n i m u m s p a n n i n gt r e ea l g o r i t h ma n da n a l y s i so ft h e c o m p l e x i t yo ft h ea l g o r i t h m ．C o m p l e x i t yo ft h ea l g o r i t h m i s O ( n 2 ) ．I no

9、 r d e rt of a c i l i t a t e t h eo p e r a t i o no nt h ec o m p u t e r ，w ea r eg i v e nt h e r i g h t o ft h e c o r r e s p o n d i n g m a t r i xm e t h o d ．S e c o n d l y ，w e f o u n d t h a t t h r o u g

10、 ha n a l y s i s ：a l lt h es p a n n i n gt r e e i n t h en e t w o r k , t h e s m a l l e s td e g r e eo f v o o ne x a c t l ye q u i v a l e n tt o t h en u m b e ro f i t s s p l i t ．O nt h eb a s i s ，w ep r o

11、 p o s e dt h es m a l l e s ts i n g l ep o i n to f m i n i m u m s p a n n i n gt r e ea l g o r i t h m ．C o m p l e x i t y o f t h ea l g o r i t h mi s O ( n 2 ) ．I nt h ea b o v ea l g o r i t h mo nt h e b a s i

12、 s o ft w o ，w ed e d u c e dt h e s u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n s o f k - g r e e —c o n s t r a i n tm i n i m u m s p a n n i n gt r e ee x i s t , a n d g i v e a s i n g l ep O i m o fk

13、- d e g r e e —c o n s t r a i n tm i n i m u m s p a n n i n g t r e ea l g o r i t h m ．T h eG l o v e ·K l i n g r n a na l g o r i t h mh a sb e e ni m p r o v e d ，al a r g en u m b e rs i m u l a t i o ne x p

14、e r i m e n t ss h o wt h a tt h ei m p r o v e da l g o r i t h m i sv e r y e f f e c t i v e ．I nc h a p t e r t h r e e ，o u rm a i n c o n s t r a i n to n t h ed e g r e e - c o n s t r a i n tm i n i m u m s p a n

15、 n i n gt r e ep r o b l e m ，v i e wo f t h eb i n d i n g p r o b l e m ，w eg i v e a n e w f a s ta l g o r i t h ms i m i l a r t ot h ep o b l e m ．E x p e r i m e n t a lr e s u l t ss h o w t h a tt h ea l g o r i

16、 t h mp e r f o r m a n c e ．O n t h i sb a s i s ，w ep r o p o s e d a t w o - s t e p s o l u t i o no ft h et r a v e l i n g s a l e s m a np r o b l e m ，a l a r g en u m b e ro fs i m u l a t i o n e x p e r i m e

17、n t ss h o w t h a tt h ea l g o r i t h m h a s p r o d u c e dg o o d r e s u l t s ．K e y w o r d s ：N e t w o r k M i n i m u m t r e e M i n i m u m t r e ea l g o r i t h mT r a v e l i n g s a l e s m a np r o b l