P r o j e k t o w a n i e e f e k t y w n y c h a l g o r y t m w
L a b o r a t o r i u m
T E M A T :
A l g o r y t m p r o g r a m o w a n i a d y n a m i c z n e g o
P R O B L E M :
P r o b l e m K o m i w o j a |e r a
D a t a o d d a n i a
& . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
O c e n a
& . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A u t o r : M i c h a B K a c z a r a
N r i n d e k s u : 1 8 1 1 3 2
R o k i k i e r u n e k
I n f o r m a t y k a I s t . i n |. , r o k 3 , s e m . 5
s t u d i w :
G r u p a w i c z e n i o w a : P N / T N 9 : 1 5 - 1 1 : 0 0
P r o w a d z c y : M g r i n |. A g a t a R u s o D
1 . O p i s s Bo w n y i m a t e m a t y c z n y p r o b l e m u . K r y t e r i u m o p t y m a l i z a c j i
1 . 1 O p i s p r o b l e m u
P r o b l e m K o m i w o j a |e r a ( a n g . T S P T r a v e l l i n g S a l e s m a n P r o b l e m ) d e f i n i u j e
s y t u a c j , w k t r e j k o m i w o j a |e r m a o d w i e d z i w s z y s t k i e N m i a s t t y l k o r a z i w r c i d o
m i a s t a p o c z t k o w e g o , p r z y c z y m t r a s a j e g o p o d r o |y p o w i n n a b y j a k n a j k r t s z a .
D r o g a p o m i d z y k a |d p a r m i a s t m a p a r a m e t r k o s z t j e j p r z e b y c i a , d Bu g o [ l u b n p .
c z a s p o d r |y . W r o z p a t r y w a n y m p r z y p a d k u p a r a m e t r e m j e s t k o s z t p r z e b y c i a d r o g i .
P o d w z g l d e m m a t e m a t y c z n y m , p r o b l e m m a s w o j e o d z w i e r c i e d l e n i e w t e o r i i
g r a f w . K a |d e z N m i a s t j e s t w i e r z c h o Bk i e m g r a f u z u p e Bn e g o , w a |o n e g o k a |d a
k r a w d z Bc z c a d w a w i e r z c h o Bk i ( V i , V j ) m a w a g , o d p o w i a d a j c k o s z t o w i
p r z e b y c i a d r o g i z V i d o V j . Z n a l e z i e n i e t a k i e j d r o g i , a b y k a |d y z N w i e r z c h o Bk w
w y s t p o w a B n a n i e j t y l k o r a z s p r o w a d z a s i d o z n a l e z i e n i a w g r a f i e t z w . c y k l u
H a m i l t o n a . P r o b l e m K o m i w o j a |e r a j e s t p r o b l e m e m N P - t r u d n y m .
1 . 2 D a n e w e j [c i o w e p r o b l e m u
D a n e w e j [c i o w e p r o b l e m u s t a n o w i N - w i e r z c h o Bk o w y g r a f p e Bn y , w a |o n y ,
p r z e d s t a w i o n y w p o s t a c i m a c i e r z y k o s z t w o r o z m i a r a c h N x N , z a p i s a n e j w p l i k u
t e k s t o w y m . K a |d a w a r t o [ m a c i e r z y n a l e |y d o p r z e d z i a Bu < 0 ; 1 0 0 > i j e s t o d d z i e l o n a
o d p o z o s t a By c h z a p o m o c t a b u l a t o r a ( \ t ) . P o n i e w a | z m i a s t a N i d o m i a s t a N i d r o g i n i e
m a , d i a g o n a l a m a c i e r z y z a w i e r a w a r t o [c i r e p r e z e n t u j c e n i e s k o Dc z o n o [.
D l a u Ba t w i e n i a i m p l e m e n t a c j i z a n i e s k o Dc z o n o [ p r z y j t a z o s t a Ba l i c z b a 9 9 9 9 .
L i s t i n g 1 . P r z y k Ba d o w e d a n e w e j [c i o w e p r o b l e m u
9 9 9 9 9 9 3 1 3
4 2 9 9 9 9 8 8 1 6
1 7 8 8 9 9 9 9 3 6
3 3 7 2 1 9 9 9 9
1 . 3 R o z w i z a n i e p r o b l e m u
R o z w i z a n i e p r o b l e m u s k Ba d a s i z c z t e r e c h l i n i i . W p i e r w s z e j z n a j d u j e s i
c a Bk o w i t y k o s z t o p t y m a l n e j t r a s y ; w d r u g i e j : w e k t o r i n d e k s w N m i a s t , k t r e k o l e j n o
w y s t p u j n a t r a s i e ( z u w z g l d n i e n i e m p o w r o t u d o p o c z t k o w e g o , d Bu g o [ w e k t o r a
N + 1 ) . K o l e j n e i n d e k s y s o d d z i e l o n e p r z e c i n k i e m i z n a k i e m s p a c j i ; w t r z e c i e j : c z a s
w y k o n a n i a a l g o r y t m u p o d a n y w m i l i s e k u n d a c h ; W a r t o [ c z w a r t e j l i n i i j e s t [c i [l e
z a l e |n a o d i m p l e m e n t a c j i i z a w i e r a l i c z b b d c w a r t o [c i l i c z n i k a u |y d a n y c h
z a p i s a n y c h p o p r z e d n i o w p a m i c i .
L i s t i n g 2 . P r z y k Ba d o w e r o z w i z a n i e p r o b l e m u
6 3
[ 0 , 1 , 3 , 2 , 0 ]
1 5
0
2
1 . 4 K r y t e r i u m o p t y m a l i z a c j i
Z a k r y t e r i u m o p t y m a l i z a c j i z o s t a Ba p r z y j t a m i n i m a l i z a c j a k o s z t u c y k l u H a m i l t o n a
w g r a f i e w e j [c i o w y m , c o j e s t r w n o w a |n e z n a l e z i e n i u n a j k r t s z e j d r o g i p r z e j [c i a
p r z e z g r a f .
2 . O p i s d z i a Ba n i a a l g o r y t m u
2 . 1 A l g o r y t m p r z e g l d u z u p e Bn e g o
M e t o d a p r z e g l d u z u p e Bn e g o z a s t o s o w a n a w p r z y p a d k u p r o b l e m u k o m i w o j a |e r a
p o l e g a n a z n a l e z i e n i u w s z y s t k i c h m o |l i w y c h c y k l i H a m i l t o n a w z a d a n y m g r a f i e ,
a n a s t p n i e w y b r a n i e s p o [r d n i c h t a k i e g o , k t r e g o o b l i c z o n y k o s z t j e s t n a j m n i e j s z y .
K r t k a a n a l i z a z Bo |o n o [c i o b l i c z e n i o w e j t e g o a l g o r y t m u :
W e zm y g r a f o N = 9 w i e r z c h o Bk a c h i p o l i c z m y i l e m a c y k l i H a m i l t o n a . Z p i e r w s z e g o
w i e r z c h o Bk a m o |e m y w y b r a 8 k r a w d z i , z d r u g i e g o 7 , z t r z e c i e g o 6 , & ,
z d z i e w i t e g o 1 k r a w d z. W e f e k c i e l i c z b a c y k l i H a m i l t o n a j e s t r w n a :
H = 8 * 7 * 6 * 5 * & * 1 = 8 ! = 4 0 3 2 0
Z a t e m d l a N w i e r z c h o Bk w l i c z b a c y k l i w y n i e s i e H = ( N - 1 ) ! . W y n i k t e n n a l e |y d o
w y k Ba d n i c z e j k l a s y z Bo |o n o [c i o b l i c z e n i o w e j O ( n ! ) .
2 . 2 A l g o r y t m p r o g r a m o w a n i a d y n a m i c z n e g o
A l g o r y t m p r o g r a m o w a n i a d y n a m i c z n e g o z o s t a B z a i m p l e m e n t o w a n y p r z e z e m n i e
w g z a s a d y d z i e l i z w y c i |a j ( a n g . d i v i d e & c o n q u e r ) , p o l e g a j c e j n a r e k u r e n c y j n y m
p o d z i a l e g B w n e g o p r o b l e m u n a p o d p r o b l e m y , t a k a b y r o z w i z y w a n a j p r o s t s z e
i n s t a n c j e p r o b l e m w , k t r y c h r o z w i z a n i a s p o t e m s c a l a n e . R o z w i z a n i a ( k o s z t
i [c i e |k a ) u z y s k a n e w k a |d y m z k r o k w s z a p i s y w a n e d o s t r u k t u r u m o |l i w i a j c y c h
i c h p r z e c h o w y w a n i e i i d e n t y f i k a c j d z i k i t e m u a l g o r y t m m o |e w y k o n y w a s i
s z y b c i e j , b o p r z e d r o z w i z a n i e m p o d p r o b l e m u s p r a w d z a , c z y n i e z o s t a B o n j u |
w c z e [n i e j r o z w i z a n y i j e [l i t a k , t o z w r a c a t o r o z w i z a n i e ( p o m i j a z b d n e o b l i c z e n i a ) .
D o p r z e c h o w y w a n i a r o z w i z a D p o [r e d n i c h w y k o r z y s t a Be m s p e c y f i c z n e s t r u k t u r y
d o s t p n e w j z y k u J a v a ( w i c e j w p k t . 4 ) . P o d p r o b l e m y , k t r e m o g b y r o z w i z a n e
w r a m a c h d a n e g o p r o b l e m u n a d r z d n e g o o k r e [l a t a b l i c a o r o z m i a r z e N z w p i s a n y m i
p o d o d p o w i e d n i e i n d e k s y w a r t o [c i a m i l o g i c z n y m i T R U E l u b F A L S E . J e [l i w p i s n a
i - t e j p o z y c j i t a b l i c y t o T R U E , a l g o r y t m b d z i e k o n t y n u o w a B d z i a Ba n i e b e z
w y w o By w a n i a r e k u r e n c j i d l a t e g o p o d r o b l e m u , w p r z e c i w n y m w y p a d k u r e k u r e n c j a
z o s t a n i e w y w o Ba n a . W p r z y p a d k u , w k t r y m w s z y s t k i e e l e m e n t y t a b l i c y m a j
w a r t o [c i T R U E , j a k o [c i e |k a z a p i s y w a n e j e s t m i a s t o p o c z t k o w e , a j a k o k o s z t
w a r t o [ n a p o z y c j i [ a k t u a l n e m i a s t o ] [ m i a s t o p o c z t k o w e ] w m a c i e r z y k o s z t w
3
i n s t a n c j i p r o b l e m u . S c a l a n i e w y n i k w p o d p r o b l e m w z o s t a Bo p r z e z e m n i e
z r e a l i z o w a n e w d w c h k r o k a c h :
w y z n a c z e n i e m i n i m u m z k o s z t w d l a k a |d e g o z p o d p r o b l e m w i z a p i s a n i e
n u m e r u p o d p r o b l e m u , d l a k t r e g o k o s z t b y B m i n i m a l n y ,
p o r o z w i z a n i u w s z y s t k i c h m o |l i w y c h p o d p r o b l e m w : s t w o r z e n i e t a b l i c y
z a w i e r a j c e j [c i e |k , s k Ba d a j c s i z n u m e r u p o d p r o b l e m u , d l a k t r e g o
k o s z t b y B m i n i m a l n y i [c i e |k i u z y s k a n e j w w y n i k u r o z w i z y w a n i a t e g o
p o d p r o b l e m u .
A b y a l g o r y t m d z i a Ba B p o p r a w n i e , k o n i e c z n e b y Bo w p r o w a d z e n i e o d p o w i e d n i e g o
s t e r o w a n i a w a r t o [c i a m i t a b l i c y u |y t y c h m i a s t ( r o z w i z a n y c h p o d p r o b l e m w ) .
P r z e d k a |d y m w y w o Ba n i e m r e k u r e n c j i n a p o z y c j i d a n e g o p o d p r o b l e m u w t a b l i c y
u s t a w i a n a j e s t w a r t o [ T R U E . P o w y k o n a n i u s i r e k u r e n c j i , w a r t o [ u s t a w i a n a j e s t
z p o w r o t e m n a F A L S E .
2 . 2 . 1 P s e u d o k o d a l g o r y t m u
P o n i |e j z a m i e s z c z a m p s e u d o k o d z a i m p l e m e n t o w a n e g o a l g o r y t m u p r o g r a m o w a n i a
d y n a m i c z n e g o . L i s t i n g p r z e d s t a w i a t r e [ f u n k c j i r e k u r e n c y j n e j l i c z K o s z t , p r z y
z a Bo |e n i u , |e i n s t a n c j a p r o b l e m u z o s t a Ba w c z y t a n a p o p r a w n i e , z o s t a Bo w y b r a n e
m i a s t o p o c z t k o w e m i a s t o S t a r t , n p . 0 , z o s t a Ba s t w o r z o n a t a b l i c a m i a s t u |y t y c h
m i a s t a U z y t e i w p i s a n a w a r t o [ T R U E n a p o z y c j i m i a s t o S t a r t , z o s t a Ba
s t w o r z o n a t a b l i c a l i s t a W y n i k , w k t r e j p r z e c h o w y w a n a b d z i e l i s t a w i e r z c h o Bk w
z n a j d u j c y c h s i n a o p t y m a l n e j [c i e |c e o r a z s t r u k t u r y k o s z t y i s c i e z k i , w k t r y c h
p r z e c h o w y w a n e b d w y n i k i u z y s k a n e d l a k o l e j n y c h p o d p r o b l e m w .
L i s t i n g 3 . P s e u d o k o d a l g o r y t m u D P d l a T S P
p r o c e d u r e l i c z K o s z t ( t a b l i c a , l i s t a W y n i k , a k t u a l n e M i a s t o , m i a s t o S t a r t , u z y t e M i a s t a )
b e g i n
w y n i k ! s t w o r z T a b l i c e ( p o b i e r z R o z m i a r ( u z y t e M i a s t a )
a k t u a l n e I D ! a k t u a l n e M i a s t o + t o S t r i n g ( u z y t e M i a s t a )
i f w s z y s t k i e U z y t e ( u z y t e M i a s t a ) t h e n
b e g i n
d o p i s z ( l i s t a W y n i k , m i a s t o S t a r t )
d o p i s z ( k o s z t y , a k t u a l n e I D , t a b l i c a [ a k t u a l n e M i a s t o ] [ m i a s t o S t a r t ] )
r e t u r n t a b l i c a [ a k t u a l n e M i a s t o ] [ m i a s t o S t a r t ]
e n d
e l s e
b e g i n
i f p o b i e r z ( k o s z t y , a k t u a l n e I D ) ! = n u l l t h e n
b e g i n
d o p i s z ( l i s t a W y n i k , p o b i e r z ( s c i e z k i , a k t u a l n e I D ) )
l i c z n i k ! l i c z n i k + 1
r e t u r n p o b i e r z ( k o s z t y , a k t u a l n e I D )
e n d
4
f o r i ! p o b i e r z R o z m i a r ( u z t e M i a s t a ) s t e p - 1 u n t i l 0 d o
b e g i n
i f u z y t e M i a s t a [ i ] c o n t i n u e
u z y t e M i a s t a [ i ] ! T R U E
k ! l i c z K o s z t ( t a b l i c a , w y n i k [ i ] , i , m i a s t o S t a r t , u z y t e M i a s t a )
u z y t e M i a s t a [ i ] ! F A L S E
k ! k + t a b l i c a [ a k t u a l n e M i a s t o ] [ i ]
i f k < m i n t h e n
b e g i n
M i n ! k
w y n i k I d x ! i
e n d
e n d
d o p i s z ( t e m p , w y n i k I d x )
d o p i s z ( t e m p , w y n i k [ w y n i k I d x ] )
d o p i s z ( l i s t a W y n i k , t e m p )
d o p i s z ( k o s z t y , a k t u a l n e I D , m i n )
d o p i s z ( s c i e z k i , a k t u a l n e I D , t e m p )
e n d
e n d
3 . P r z y k Ba d o w e r o z w i z a n i a d l a w y b r a n e j i n s t a n c j i
P o n i |e j z a m i e s z c z a m p r z y k Ba d o w e r o z w i z a n i e a l g o r y t m u d l a i n s t a n c j i
p r z e d s t a w i o n e j n a l i s t i n g u 1 . ( s t r 2 . ) . M a c i e r z k o s z t w j e s t m a c i e r z k w a d r a t o w
i a s y m e t r y c z n o r o z m i a r a c h 4 x 4 , r o z w a |a m w i c a s y m e t r y c z n y p r o b l e m k o m i w o j a |e r a
d l a N = 4 m i a s t .
9 9 9 9 9 9 3 1 3
4 2 9 9 9 9 8 8 1 6
[ ]
1 7 8 8 9 9 9 9 3 6
3 3 7 2 1 9 9 9 9
3 . 1 W y w o Ba n i e f u n k c j i l i c z K o s z t ( )
u z y t e M i a s t a = T , F , F , F
N i e w s z y s t k i e m i a s t a s o d w i e d z o n e i n i e m a o d p o w i e d n i e g o w p i s u w m a p i e
k o s z t w p r z e c h o d z i m y d o p t l i i w y w o Bu j e m y o d p o w i e d n i e r e k u r e n c j e
i = 3
3 . 1 . 1 R e k u r e n c j a , m i a s t o : 3 , l i s t a W y n i k : w y n i k [ 3 ]
u z y t e M i a s t a = T , F , F , T
N i e w s z y s t k i e m i a s t a s o d w i e d z o n e i n i e m a o d p o w i e d n i e g o w p i s u
w m a p i e k o s z t w p r z e c h o d z i m y d o p t l i i w y w o Bu j e m y o d p o w i e d n i e
r e k u r e n c j e
i = 3 u z y t e M i a s t a [ 3 ] = = T , w i c k o n t y n u u j e m y
i = 2
5
3 . 1 . 1 . 1 R e k u r e n c j a , m i a s t o : 2 , l i s t a W y n i k : w y n i k [ 2 ]
u z y t e M i a s t a = T , F , T , T
N i e w s z y s t k i e m i a s t a s o d w i e d z o n e i n i e m a o d p o w i e d n i e g o w p i s u
w m a p i e k o s z t w p r z e c h o d z i m y d o p t l i i w y w o Bu j e m y
o d p o w i e d n i e r e k u r e n c j e
i = 3 u z y t e M i a s t a [ 3 ] = = T , w i c k o n t y n u u j e m y
i = 2 u z y t e M i a s t a [ 2 ] = = T w i c k o n t y n u u j e m y
i = 1
3 . 1 . 1 . 1 . 1 R e k u r e n c j a , m i a s t o : 1 , l i s t a W y n i k : w y n i k [ 1 ]
u z y t e M i a s t a = T , T , T , T
W s z y s t k i e m i a s t a o d w i e d z o n e z a p i s w y n i k w
l i s t a W y n i k = 0 ;
k o s z t y + = ( 1 [ T , T , T , T ] ; t a b l i c a [ 1 , 0 ] = 4 2 )
k o s z t = 4 2 + t a b l i c a [ 2 ] [ 1 ] = 1 3 0
m i n = 1 3 0
w y n i k I d x = 1
i = 0 u z y t e M i a s t a [ 0 ] = = T , w i c k o n t y n u u j e m y
l i s t a W y n i k = 1 , 0
k o s z t y + = ( 1 [ T , F , T , T ] ) ; 1 3 0 )
s c i e z k i + = ( 1 [ T , F , T , T ) ; 1 , 0 )
k o s z t = 1 3 0 + t a b l i c a [ 3 ] [ 2 ] = 1 5 1
m i n = 1 5 1
w y n i k I d x = 2
i = 1
3 . 1 . 1 . 2 R e k u r e n c j a , m i a s t o : 1 , l i s t a W y n i k : w y n i k [ 1 ]
u z y t e M i a s t a = T , T , F , T
N i e w s z y s t k i e m i a s t a s o d w i e d z o n e i n i e m a o d p o w i e d n i e g o w p i s u
w m a p i e k o s z t w p r z e c h o d z i m y d o p t l i i w y w o Bu j e m y
o d p o w i e d n i e r e k u r e n c j e
i = 3 u z y t e M i a s t a [ 3 ] = = T , w i c k o n t y n u u j e m y
i = 2
3 . 1 . 1 . 2 . 1 R e k u r e n c j a , m i a s t o : 2 , l i s t a W y n i k : w y n i k [ 2 ]
u z y t e M i a s t a = T , T , T , T
W s z y s t k i e m i a s t a o d w i e d z o n e z a p i s w y n i k w
l i s t a W y n i k = 0 ;
6
k o s z t y + = ( 1 [ T , T , T , T ] ; t a b l i c a [ 2 ] [ 0 ] = 1 7 )
k o s z t = 1 7 + t a b l i c a [ 1 ] [ 2 ] = 1 0 5
m i n = 1 0 5
w y n i k I d x = 2
i = 1 u z y t e M i a s t a [ 1 ] = = T , w i c k o n t y n u u j e m y
i = 0 u z y t e M i a s t a [ 0 ] = = T , w i c k o n t y n u u j e m y
l i s t a W y n i k = 2 , 0
k o s z t y + = ( 1 [ T , T , F , T ] ) ; 1 0 5 )
s c i e z k i + = ( 1 [ T , T , F , T ) ; 2 , 0 )
k o s z t = 1 0 5 + t a b l i c a [ 2 ] [ 1 ] = 1 1 2
m i n = 1 1 2
w y n i k I d x = 1
i = 0 u z y t e M i a s t a [ 0 ] = = T , w i c k o n t y n u u j e m y
l i s t a W y n i k = 1 , 2 , 0
k o s z t y + = ( 3 [ T , F , F , T ] ) ; 1 1 2 )
s c i e z k i + = ( 1 [ T , F , F , T ) ; 1 , 2 , 0 )
k o s z t = 1 1 2 + t a b l i c a [ 0 ] [ 3 ] = 1 2 5
m i n = 1 2 5 ;
w y n i k I d x = 3 ;
i = 2
W y k o n u j e m y o p e r a c j e a n a l o g i c z n e d o p r z e d s t a w i o n y c h p o w y |e j .
W a r t o [ m i n i m a l n a s i n i e z m i e n i .
i = 1
W y k o n u j e m y o p e r a c j e a n a l o g i c z n i e d o p r z e d s t a w i o n y c h p o w y |e j . P o i c h
w y k o n a n i u w a r t o [ m i n i m u m w y n i e s i e 6 3 , a [c i e |k a b d z i e k o l e j n o p r z y j m o w a
w a r t o [c i : 0 ; 2 , 0 , n a s t p n i e : 3 , 2 , 0 . I n d e k s t a b l i c y [c i e |e k b d z i e r w n y 1 .
i = 0 u z y t e M i a s t a [ 0 ] = = T , w i c k o n t y n u u j e m y
l i s t a W y n i k = 1 , 3 , 2 , 0
k o s z t y + = ( 0 [ T , F , F , F ] ; 6 3 )
s c i e z k i + = ( 0 [ T , F , F , F ] ; 1 , 3 , 2 , 0 )
3 . 2 W y n i k i
6 3 k o s z t p r z e b y c i a d r o g i
[ 0 , 1 , 3 , 2 , 0 ] - d r o g a
1 5 0 0 0 0 0 c z a s w y k o n y w a n i a 2 5 m i n , z a j Bo m i p r z e l i c z e n i e n a k a r t k a c h
0 l i c z n i k w y k o r z y s t a D r o z w i z a D p o d p r o b l e m w
7
4 . S z c z e g By i m p l e m e n t a c y j n e
A l g o r y t m z o s t a B z a i m p l e m e n t o w a n y w j z y k u J a v a , w [r o d o w i s k u E c l i p s e .
C a By p r o g r a m j e s t r e p r e z e n t o w a n y p r z e z j e d n k l a s K o m i w o j a z e r D P , w k t r e j
z d e f i n i o w a n e s m e t o d y n i e z b d n e d o r o z w i z a n i a p r o b l e m u o r a z p o m o c n i c z e , n p .
m e t o d a o d p o w i e d z i a l n a z a k o n w e r s j t a b l i c y w a r t o [c i t y p u b o o l e a n n a Ba Dc u c h
t e k s t o w y , w k t r y m 1 o z n a c z a j T R U E a 0 - F A L S E . P r o g r a m , d o p r z e c h o w y w a n i a
r o z w i z a D p o d p r o b l e m w , k o r z y s t a z e s t r u k t u r H a s h M a p d o s t p n y c h d o m y [l n i e
w j z y k u J a v a . W y n i k i s p r z e c h o w y w a n e n a z a s a d z i e k l u c z = > w a r t o [, g d z i e k l u c z
t o w a r t o [ z m i e n n e j a k t u a l n e I D ( p k t . 2 . 2 . 1 ) . P o n i |e j z a m i e s z c z a m l i s t i n g
n a j w a |n i e j s z e j f u n k c j i l i c z K o s z t ( ) .
L i s t i n g 4 . M e t o d a l i c z K o s z t k l a s y K o m i w o j a z e r D P
p r i v a t e s t a t i c i n t l i c z K o s z t ( i n t [ ] [ ] t a b l i c a , A r r a y L i s t < I n t e g e r > l i s t a W y n i k , i n t
a k t u a l n e M i a s t o , i n t m i a s t o S t a r t , b o o l e a n [ ] u z y t e M i a s t a ) {
/ / T a b l i c a z e s c i e z k a w y n i k o w a
A r r a y L i s t < I n t e g e r > [ ] w y n i k = n e w A r r a y L i s t [ u z y t e M i a s t a . l e n g t h ] ;
S t r i n g a k t u a l n e I D = " " + a k t u a l n e M i a s t o + a r r a y T o S t r i n g ( u z y t e M i a s t a ) ;
S y s t e m . o u t . p r i n t l n ( " R e k u r e n c j a ( m i a s t o " + a k t u a l n e M i a s t o + " ) : " ) ;
/ / J e z e l i w s z y s t k i e m i a s t a p r z e b y t e
i f ( w s z y s t k i e U z y t e ( u z y t e M i a s t a ) ) {
l i s t a W y n i k . a d d ( m i a s t o S t a r t ) ;
i n t k o s z t = t a b l i c a [ a k t u a l n e M i a s t o ] [ m i a s t o S t a r t ] ;
k o s z t y . p u t ( a k t u a l n e I D , k o s z t ) ;
S y s t e m . o u t . p r i n t l n ( " \ t > W s z y s t k i e m i a s t a o d w i e d z o n e " ) ;
r e t u r n k o s z t ;
}
/ / J e z e l i n i e
e l s e {
i n t m i n = I n t e g e r . M A X _ V A L U E ;
i n t w y n i k I d x = - 1 ;
/ / J e z e l i p o d p r o b l e m j u z r o z w i a z a n y
i f ( k o s z t y . g e t ( a k t u a l n e I D ) ! = n u l l ) {
l i s t a W y n i k . a d d A l l ( s c i e z k i . g e t ( a k t u a l n e I D ) ) ;
l i c z n i k + + ;
S y s t e m . o u t . p r i n t l n ( " \ t > W y k o r z y s t a n i e w a r t o s c i o b l i c z o n e j
w c z e s n i e j " ) ;
r e t u r n k o s z t y . g e t ( a k t u a l n e I D ) ;
}
/ / J e z e l i n i e t o o b l i c z e n i a
S y s t e m . o u t . p r i n t l n ( " \ t > O b l i c z e n i a " ) ;
f o r ( i n t i = u z y t e M i a s t a . l e n g t h - 1 ; i > = 0 ; i - - ) {
i f ( u z y t e M i a s t a [ i ] ) c o n t i n u e ;
/ / R e k u r e n c j a
u z y t e M i a s t a [ i ] = t r u e ;
w y n i k [ i ] = n e w A r r a y L i s t < I n t e g e r > ( ) ;
i n t k o s z t = l i c z K o s z t ( t a b l i c a , w y n i k [ i ] , i , m i a s t o S t a r t ,
u z y t e M i a s t a ) ;
u z y t e M i a s t a [ i ] = f a l s e ;
k o s z t + = t a b l i c a [ a k t u a l n e M i a s t o ] [ i ] ;
/ / A k t u a l i z a c j a k o s z t u m i n i m a l n e g o
i f ( k o s z t < m i n ) {
m i n = k o s z t ;
w y n i k I d x = i ;
S y s t e m . o u t . p r i n t l n ( " \ t > U s t a w i e n i e m i n i m u m " ) ;
}
}
8
/ / Z a p i s w y n i k o w
S y s t e m . o u t . p r i n t l n ( " \ t > Z a p i s w y n i k o w " ) ;
A r r a y L i s t < I n t e g e r > t e m p = n e w A r r a y L i s t < I n t e g e r > ( ) ;
t e m p . a d d ( w y n i k I d x ) ;
t e m p . a d d A l l ( w y n i k [ w y n i k I d x ] ) ;
l i s t a W y n i k . a d d A l l ( t e m p ) ;
k o s z t y . p u t ( a k t u a l n e I D , m i n ) ;
s c i e z k i . p u t ( a k t u a l n e I D , t e m p ) ;
S y s t e m . o u t . p r i n t l n ( " \ t > P o w r o t p o z i o m w y z e j " ) ;
r e t u r n m i n ;
}
}
P o m i a r c z a s u w y k o n y w a n i a a l g o r y t m u w y k o n a n y z o s t a B z u |y c i e m f u n k c j i
S y s t e m . n a n o T i m e ( ) . K o m p u t e r , n a k t r y m t e s t o w a n y a l g o r y t m w y p o s a |o n y b y B
w p r o c e s o r I n t e l C o r e 2 D u o 2 , 2 G H z i 2 G B p a m i c i R A M . P r o g r a m u r u c h a m i a n y b y B
p o d s y s t e m e m W i n d o w s 7 P r o f e s s i o n a l 3 2 - b i t .
5 . P r z y k Ba d d z i a Ba n i a p r o g r a m u d l a w y b r a n e j i n s t a n c j i
P o n i |e j z a m i e s z o n y z o s t a B l i s t i n g z a w i e r a j c y p r z y k Ba d d z i a Ba n i a p r o g r a m u .
J e s t t o w y c i g z k o n s o l i p r o g r a m u E c l i p s e . P r o g r a m w y [w i e t l a k o l e j n e r e k u r e n c j e
i a k c j e , k t r e w r a m a c h n i c h p o d e j m u j e . I n f o r m u j e m . i n . o d o k o n y w a n i u o b l i c z e D,
p o m i j a n i u o b l i c z e D, u s t a w i a n i u m i n i m u m i z a p i s i e w y n i k w .
L i s t i n g 5 . P r z y k Ba d d z i a Ba n i a p r o g r a m u
P r o g r a m : A l g o r y t m D y n a m i c P r o g r a m m i n g d l a p r o b l e m u k o m i w o j a z e r a
P r z e d m i o t : P r o j e k t o w a n i e E f e k t y w n y c h A l g o r y t m w
A u t o r : M i c h a l K a c z a r a 1 8 1 1 3 2
> W c z y t y w a n i e d a n y c h z p l i k u d a t a 0 4 . t x t . . .
> S t a r t !
R e k u r e n c j a ( m i a s t o 0 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 3 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 2 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 1 ) :
> W s z y s t k i e m i a s t a o d w i e d z o n e
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> U s t a w i e n i e m i n i m u m
R e k u r e n c j a ( m i a s t o 1 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 2 ) :
> W s z y s t k i e m i a s t a o d w i e d z o n e
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> U s t a w i e n i e m i n i m u m
R e k u r e n c j a ( m i a s t o 2 ) :
> O b l i c z e n i a
9
R e k u r e n c j a ( m i a s t o 3 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 1 ) :
> W s z y s t k i e m i a s t a o d w i e d z o n e
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> U s t a w i e n i e m i n i m u m
R e k u r e n c j a ( m i a s t o 1 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 3 ) :
> W s z y s t k i e m i a s t a o d w i e d z o n e
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
R e k u r e n c j a ( m i a s t o 1 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 3 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 2 ) :
> W s z y s t k i e m i a s t a o d w i e d z o n e
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> U s t a w i e n i e m i n i m u m
R e k u r e n c j a ( m i a s t o 2 ) :
> O b l i c z e n i a
R e k u r e n c j a ( m i a s t o 3 ) :
> W s z y s t k i e m i a s t a o d w i e d z o n e
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> U s t a w i e n i e m i n i m u m
> Z a p i s w y n i k o w
> P o w r o t p o z i o m w y z e j
> S t o p !
6 3
[ 0 , 1 , 3 , 2 , 0 ]
3
0
6 . B a d a n i a e k s p e r y m e n t a l n e
B a d a n i a p r z e p r o w a d z i Be m d l a d z i e s i c i u r o z m i a r w i n s t a n c j i p r o b l e m u .
D a n e w e j [c i o w e j m a c i e r z y k o s z t w b y By g e n e r o w a n e l o s o w o . K a |d e p o l e m a c i e r z y
( o p r c z t y c h l e |c y c h n a d i a g o n a l i ) , m o g Bo p r z y j m o w a w a r t o [c i z z a k r e s u < 1 ; 1 0 0 > .
P o m i a r y c z a s u w y k o n y w a n i a a l g o r y t m u z o s t a By w y k o n a n e d l a 1 0 0 i n s t a n c j i d a n e g o
r o z m i a r u i u [r e d n i o n e ( [r e d n i a a r y t m e t y c z n a ) .
T a b e l a 1 . W y n i k i p o m i a r w c z a s u d z i a Ba n i a a l g o r y t m u w z a l e |n o [c i o d r o z m i a r u i n s t a n c j i .
R o z m i a r i n s t a n c j i N 2 4 6 8 1 0 1 2 1 4 1 6
Zr e d n i c z a s [ m s ] 0 , 0 1 0 , 0 2 0 , 1 2 2 , 2 7 2 0 , 4 3 1 8 6 , 7 3 1 2 7 1 , 2 1 6 7 8 8 , 4 3
P o m i a r w d l a i n s t a n c j i o r o z m i a r z e N = 1 8 n i e b y Be m w s t a n i e w y k o n a , z e w z g l d u n a
o g r a n i c z e n i e p a m i c i o w e w i r t u a l n e j m a s z y n y J a v a . P o z w i k s z e n i u l i m i t u p a m i c i z 2 5 6
1 0
n a 5 1 2 M B p r o g r a m p o l i c z y B r o z w i z a n i e , j e d n a k w c z a s i e r w n y m o k . 5 0 s . P r z y N = 2 0
i z w i k s z e n i u l i m i t u p a m i c i d o 1 G B p r o g r a m n i e p o t r a f i B p o l i c z y r o z w i z a n i a , w i k s z a
i l o [ p a m i c i n i e m o g Ba z o s t a p r z y d z i e l o n a z e w z g l d u n a o g r a n i c z o n i l o [ p a m i c i
z a i n s t a l o w a n e j w k o m p u t e r z e .
W y k r e s 1 . Z a l e |n o [ c z a s u w y k o n y w a n i a a l g o r y t m u o d r o z m i a r u i n s t a n c j i p r o b l e m u .
8 0 0 0
6 7 8 8 , 4 3
7 0 0 0
6 0 0 0
5 0 0 0
4 0 0 0
C z a s [ m s ]
3 0 0 0
2 0 0 0
1 2 7 1 , 2 1
1 0 0 0
1 8 6 , 7 3
0 , 0 1 0 , 0 2 0 , 1 2 2 , 2 7 2 0 , 4 3
0
2 4 6 8 1 0 1 2 1 4 1 6
R o z m i a r i n s t a n c j i N
7 . W n i o s k i
1 . K r z y w a w i d o c z n a n a w y k r e s i e 1 . p o k a z u j e , |e z a l e |n o [ c z a s u r o z w i z y w a n i a
p r o b l e m u w z a l e |n o [c i o d r o z m i a r u i n s t a n c j i r o [n i e w y k Ba d n i c z o , c z y l i z g o d n i e
z p r z e w i d y w a n i a m i ( a l g o r y t m p r o g r a m o w a n i a d y n a m i c z n e g o d l a p r o b l e m u
k o m i w o j a |e r a m a z Bo |o n o [ O ( n 2 2 n ) ) .
2 . N a j w i k s z a b a d a n a i n s t a n c j a p o s i a d a Ba N = 1 6 m i a s t . P r z y i n s t a n c j a c h w i k s z y c h ,
n p . N = 2 0 a l g o r y t m p r a c o w a B n i e p r z e r w a n i e p r z e z d Bu |s z y o k r e s c z a s u .
P o t w i e r d z a t o f a k t , |e a l g o r y t m p r o g r a m o w a n i a d y n a m i c z n e g o n a j l e p i e j s t o s o w a
d o m a By c h i n s t a n c j i p r o b l e m w . N i e b e z z n a c z e n i a m o g Bo b y w t y m w y p a d k u
l o s o w e g e n e r o w a n i e m a c i e r z y k o s z t w . I m w i k s z a i n s t a n c j a p r o b l e m u t y m
w i c e j p a m i c i o p e r a c y j n e j p o t r z e b o w a B p r o g r a m . D o r o z w i z a n i a p r o b l e m u
z N = 1 6 m i a s t a m i p o t r z e b n e b y Bo 2 6 5 M B p a m i c i , z N = 1 8 j u | 5 1 2 M B , a p r z y N = 2 0
w i c e j n i | 1 G B . D u |e u |y c i e p a m i c i R A M t o c e c h a a l g o r y t m w p r o g r a m o w a n i a
d y n a m i c z n e g o i z a r a z e m d u |a w a d a t e g o r o z w i z a n i a .
3 . Z a i m p l e m e n t o w a n y a l g o r y t m r o z w i z u j e p r o b l e m k o m i w o j a |e r a s p r a w n i e
i w y s t a r c z a j c o s z y b k o d l a N < 1 4 m i a s t . D z i a Ba w o l n i e j n i | a l g o r y t m B & B .
1 1
C z a s [ m s ]
4 . P r z y c z y n d u |e j z a j t o [c i p a m i c i i d u |e g o c z a s u r o z w i z y w a n i a p r o b l e m u j u |
p r z y i n s t a n c j a c h z a w i e r a j c y c h N > 1 5 m i a s t , j e s t p r a w d o p o d o b n i e s p o s b
p r z e c h o w y w a n i a p o [r e d n i c h r o z w i z a D s o n e i n d e k s o w a n e p o k l u c z a c h
b d c y c h Ba Dc u c h a m i t e k s t o w y m i . P r o b l e m e m j e s t t e | p r z e s z u k i w a n i e s t r u k t u r ,
k t r e t e r o z w i z a n i a p r z e c h o w u j .
1 2
8 . B i b l i o g r a f i a
[ 1 ] A l f r e d V . A h o , J o h n E . H o p c r o f t , J e f f r e y D . U l l m a n , P r o j e k t o w a n i e i a n a l i z a
a l g o r y t m w , W y d . H e l i o n , 2 0 0 3 , s t r . 4 1 - 4 7
[ 2 ] P o l i t e c h n i k a W r o c Ba w s k a , P r o g r a m o w a n i e d y n a m i c z n e ( D y n a m i c P r o g r a m m i n g -
D P ) [ o n l i n e ] . [ D o s t p 1 7 g r u d n i a 2 0 1 1 ] . D o s t p n y w I n t e r n e c i e :
< f t p : / / s i t h . i c t . p w r . w r o c . p l / I n f o r m a t y k a / P E A / P D _ w s t e p . p d f >
[ 3 ] M a r i a J o s e S e r n a I g l e s i a s , D y n a m i c P r o g r a m m i n g [ o n l i n e ] . [ D o s t p 1 7 g r u d n i a
2 0 1 1 ] . D o s t p n y w I n t e r n e c i e :
< h t t p : / / w w w . l s i . u p c . e d u / ~ m j s e r n a / d o c e n c i a / a l g o f i b / P 0 7 / d y n p r o g . p d f >
1 3
Wyszukiwarka
Podobne podstrony:
DP Miscallenous wnt5 x86 32sprawozdanie felixa2Sprawozdanie Konduktometriazmiany w sprawozdaniach finErrata do sprawozdania2009 03 BP KGP Niebieska karta sprawozdanie za 2008rid&657Sprawozdanie nr 3 inzSprawozdanie FundacjaBioEdu20076 dp!3 konspekt cukrzyca 09Sprawozdanie Ćw 2sprawozdanie 4Fanuc 0T DP [TTT] L567 85sprawozdanie 2009więcej podobnych podstron