27
                           

distancia de edição

Embed Size (px)

Citation preview

Page 1: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 1/26

 

U n i v e r s i d a d e F e d e r a l d e M i n a s G e r a i s  

D e p a r t a m e n t o d e C i ê n c i a d a C o m p u t a ç ã o  

P r o j e t o e A n á l i s e d e A l g o r i t m o s    

T r a b a l h o P r á t i c o I I d i s p o n í v e l e m :  

h t t p : / / w w w . d c c . u f m g . b r /  ∼

d e n i s / p a a / d e n i s - p a a 0 6 t p 2 . p d f  

C ó d i g o f o n t e d i s p o n í v e l e m :  

h t t p : / / w w w . d c c . u f m g . b r /  ∼

d e n i s / p a a / d e n i s - p a a 0 6 t p 2 . t a r . g z  

D e n i s P i n t o P i n h e i r o  

M o n i t o r : F a b i a n o C . B o t e l h o  

P r o f e s s o r : N i v i o Z i v i a n i  

B e l o H o r i z o n t e  

2 d e m a i o d e 2 0 0 6  

Page 2: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 2/26

 

S u m á r i o      

1 D i s t â n c i a d e E d i ç ã o 1  

1 . 1 A l g o r i t m o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1  

1 . 2 C o m p l e x i d a d e d e T e m p o e E s p a ç o . . . . . . . . . . . . . . . . . . . . 2  

1 . 3 I m p l e m e n t a ç ã o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2  

1 . 4 E x e m p l o P r á t i c o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5  

2 C o n j u n t o I n d e p e n d e n t e d e V é r t i c e s 6  

2 . 1 S o l u ç ã o Ó t i m a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6  

2 . 2 R e d u ç ã o d o C l i q u e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7  

2 . 3 A l g o r i t m o A p r o x i m a d o . . . . . . . . . . . . . . . . . . . . . . . . . . 9  

A C ó d i g o F o n t e d o a l g o r i t m o d e D . E . 1 1  

B C ó d i g o F o n t e d a i m p l e m e n t a ç ã o d o G r a f o 1 4  

B . 1 A r q u i v o c a b e ç a l h o   g r a f o m a t r i z . h   . . . . . . . . . . . . . . . . . . . . . 1 4  

B . 2 P r o g r a m a   g r a f o m a t r i z . c   . . . . . . . . . . . . . . . . . . . . . . . . . 1 5  

C C ó d i g o F o n t e d o s A l g o r i t m o s p a r a o P C I 1 8  

Page 3: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 3/26

 

1 D i s t â n c i a d e E d i ç ã o      

O a l g o r i t m o a s e g u i r é ú t i l p a r a s e r u s a d o e m c o r r e t o r e s o r t o g r á c o s . S e j a m d a d a s  

d u a s c a d e i a s d e c a r a c t e r e s :  

X  = x1, x2,...,xm e 

Y  = y1, y2,...,yn . O n ú m e r o  

kd e 

o p e r a ç õ e s d e s u b s t i t u i ç ã o , i n s e r ç ã o e r e t i r a d a d e c a r a c t e r e s n e c e s s á r i o p a r a t r a n s -  

f o r m a r   X  e m  Y  é c o n h e c i d o c o m o d i s t â n c i a d e e d i ç ã o . A s s i m , a d i s t â n c i a d e e d i ç ã o  

d e e d ( X , Y ) c o r r e s p o n d e a o n ú m e r o  k

d e o p e r a ç õ e s n e c e s s á r i a s p a r a c o n v e r t e r  X 

e m 

Y . P o r e x e m p l o , s e  

X  = matrandae 

Y  = saturadase n t ã o e d ( X Y ) = 4 . A s e q u ê n c i a  

d e o p e r a ç õ e s é : ( i ) s u b s t i t u i  

x1 p o r 

y1 ( ' s ' ) , ( i i ) i n s e r e  

y4 ( ' u ' ) a p ó s  

x3 , ( i i i ) r e t i r a  

x6

( ' n ' ) e ( i v ) i n s e r e  y9 ( ' s ' ) a p ó s  

x8 . 

1 . 1 A l g o r i t m o      

A D i s t â n c i a d e E d i ç ã o ( L e v e n s h t e i n , 1 9 6 5 ) e n t r e d o i s " s t r i n g s " ( d u a s s e q u ê n c i a s d e  

c a r a c t e r e s ) é d a d a p e l o n ú m e r o m í n i m o d e o p e r a ç õ e s n e c e s s á r i a s p a r a t r a n s f o r m a r  

u m s t r i n g n o o u t r o . E n t e n d e m o s p o r " o p e r a ç õ e s " a i n s e r ç ã o , d e l e ç ã o o u s u b s t i t u i ç ã o  

d e u m c a r á c t e r . É m u i t o ú t i l p a r a a p l i c a ç õ e s q u e p r e c i s a m d e t e r m i n a r q u ã o s e m e -  

l h a n t e s d o i s s t r i n g s s ã o , c o m o é p o r e x e m p l o o c a s o c o m o s v e r i c a d o r e s o r t o g r á c o s .  

P r o g r a m a ç ã o D i n â m i c a  

A P r o g r a m a ç ã o D i n â m i c a ( P D ) é u m m é t o d o p a r a a c o n s t r u ç ã o d e a l g o r i t m o s p a r a a  

r e s o l u ç ã o d e p r o b l e m a s c o m p u t a c i o n a i s , e m e s p e c i a l o s d e o t i m i z a ç ã o c o m b i n a t ó r i a .  

A P D é a p l i c á v e l a p r o b l e m a s o n d e a s o l u ç ã o ó t i m a p o d e s e r c o m p u t a d a a p a r t i r d a  

s o l u ç ã o ó t i m a p r e v i a m e n t e c a l c u l a d a e m e m o r i z a d a - d e f o r m a a e v i t a r r e c á l c u l o -  

d e o u t r o s s u b p r o b l e m a s q u e , s o b r e p o s t o s , c o m p õ e m o p r o b l e m a o r i g i n a l [ 5 , 2 ] .  

O A l g o r i t m o 1 a p r e s e n t a u m a s o l u ç ã o q u e u s a p r o g r a m a ç ã o d i n â m i c a p a r a r e -  

s o l v e r o p r o b l e m a d a d i s t â n c i a d e e d i ç ã o , e n c o n t r a d o e m [ 3 ] :  

O a l g o r i t m o r e c e b e c o m o e n t r a d a d o i s s t r i n g s  

str1e 

str2d e t a m a n h o s  

me 

n, 

r e s p e c t i v a m e n t e . P r i m e i r a m e n t e , i n i c i a l i z a - s e u m a m a t r i z  D(m+1)×(n+1) , o n d e s e r ã o  

a r m a z e n a d o s o s c u s t o s d e e d i ç ã o d o s t r i n g  

str1n o s t r i n g  

str2( l i n h a 2 ) . O s d o i s  

p r i m e i r o s   l o o p s   i n i c i a l i z a m a p r i m e i r a l i n h a e a p r i m e i r a c o l u n a d e  D

c o m o s í n d i c e s  

ie 

jd a s m e s m a s ( l i n h a s 4 a 9 ) . D a l i n h a 1 0 a 1 9 , o s   l o o p s   a n i n h a d o s p e r c o r r e m  

a m a t r i z  D

, a r m a z e n a n d o e m  D[i][ j]

o c u s t o d e t r a n s f o r m a r  str1[1..i]

e m str2[1..j]

( l i n h a 1 8 ) . A c a d a p a s s o ,  

D[i][ j]r e c e b e o m e n o r c u s t o e n t r e o s s e g u i n t e s c a s o s :  

• s e é p o s s í v e l t r a n s f o r m a r  

str1[1..i]a 

str2[1..j−1]e m 

ko p e r a ç õ e s , e n t ã o p o d e - s e  

s i m p l e s m e n t e a d i c i o n a r  

str[ j]d e p o i s p a r a o b t e r  

str2[1..j]e m 

k + 1o p e r a ç õ e s ;  

•s e é p o s s í v e l t r a n s f o r m a r  

str1[1..i−1]a 

str2[1..j]e m 

ko p e r a ç õ e s , e n t ã o p o d e -  

s e f a z e r a s m e s m a s o p e r a ç õ e s e m  

str1[1..i]e d e p o i s r e m o v e r o  

str1[i]o r i g i n a l  

a o m d e  k + 1

o p e r a ç õ e s .  

•s e é p o s s í v e l t r a n s f o r m a r  

str1[1..i − 1]a 

str2[1..j − 1]e m 

ko p e r a ç õ e s , e n t ã o  

p o d e - s e f a z e r o m e s m o c o m  

str1[1..i]s e 

str1[i]f o r i g u a l a  

str2[ j], c a s o c o n t r á r i o ,  

f a z - s e u m a s u b s t i t u i ç ã o d e  str2[ j]

p o r str1[i]

, r e q u e r i n d o  k + 1

o p e r a ç õ e s n o  

n a l p a r a t r a n s f o r m a r  

str1[1..i]a 

str2[1..j]. 

Page 4: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 4/26

 

A l g o r i t m o 1   A l g o r i t m o p a r a c a l c u l a r a D i s t â n c i a d e E d i ç ã o .  

1 :  D i s t a n c i a E d i c a o   (  c h a r  

str1[1..m],  c h a r  

str2[1..n]) 

2 :  i n t D =

i n t [0..m][0..n]

3 :  i n t 

i,j,t; 

4 :  f o r i = 0

a t é m

d o 

5 :  D[i][0] = i; 

6 :  e n d f o r  

7 : 

f o r 

 j = 0a t é 

nd o 

8 : 

D[0][ j] = j; 

9 :  e n d f o r  

1 0 :  f o r i = 1

a t é i <= n

d o 

1 1 :  f o r  j = 1

a t é j <= m

d o 

1 2 :  i f 

str1[i] == str2[ j]t h e n  

1 3 : 

t = 0; 

1 4 :  e l s e  

1 5 :  t = 1; 

1 6 : 

e n d i f  

1 7 :  e n d f o r  

1 8 : 

D[i][ j] = min(D[i][ j − 1] + 1, D[i − 1][ j] + 1, D[i − 1][ j − 1] + t); 

1 9 :  e n d f o r  

2 0 :  r e t u r n  D[m][n]

A s o p e r a ç õ e s r e q u i r i d a s p a r a t r a n s f o r m a r  str1[1..n]

e m str2[1..m]

é o c u s t o n e -  

c e s s á r i o p a r a t r a n s f o r m a r t o d o s o s c a r a c t e r e s d e  

str1e m t o d o s o s c a r a c t e r e s d e  

str2, 

e l o g o  D[m][n]

c o n t é m o r e s u l t a d o d e s e j a d o ( r e t o r n a d o n a l i n h a 2 0 ) .  

1 . 2 C o m p l e x i d a d e d e T e m p o e E s p a ç o      

P a r a c a l c u l a r o v a l o r d e  

D[i][ j], s o m e n t e a s c é c u l a s  

D[i − 1][ j − 1], 

D[i − 1][ j]e 

D[i][ j − 1]s ã o e x a m i n a d a s , a l é m d o s d o i s c a r a c t e r e s  

str1[i]e 

str2[ j]. A o t o d o s ã o  

c a l c u l a d o s  

m×nc é l u l a s d e  

D, p e l o f a t o d e o b l o c o d o   l o o p   a n i n h a d o e x e c u t a r s e m p r e  

m × n. D e s t a f o r m a p o d e m o s a r m a r q u e a c o m p l e x i d a d e d e t e m p o é  

O(mn). 

O e s p a ç o u t i l i z a d o p e l o a l g o r i t m o s ã o d u a s s e q u e n c i a s d e t a m a n h o  

me 

n, a s 

q u a i s a r m a z e n a m a s d u a s p a l a v r a s p a r a o c á l c u l o d a d i s t â n c i a d e e d i ç ã o e u m a  

m a t r i z d e t a m a n h o  

(m + 1)

×(n + 1)

q u e a r m a z e n a o s c u s t o s d e e d i ç ã o . A s s i m ,  

p o d e - s e a r m a r q u e a c o m p l e x i d a d e d e e s p a ç o d o a l g o r i t m o é t a m b é m   O(mn). 

1 . 3 I m p l e m e n t a ç ã o      

A i m p l e m e n t a ç ã o d o a l g o r i t m o d o p r o b l e m a d e d i s t â n c i a d e e d i ç ã o f o i f e i t a u t i l i z a n d o  

a l i n g u a g e m C e o c ó d i g o f o n t e é a p r e s e n t a d o n o A p e n d i c e A . A b a i x o é a p r e s e n t a d o  

u m a e x p l a n a ç ã o s u c i n t a s o b r e e s t a i m p l e m e n t a ç ã o .  

O t r e c h o d e c ó d i g o a s e g u i r a p r e s e n t a a p a r t e d a i m p l e m e n t a ç ã o ( p a r t e i n i c i a l )  

q u e c o r r e s p o n d e n t e a o c á l c u l o d a d i s t â n c i a d e e d i ç ã o .  

t y p e d e f s t r u c t D C e l l {  

i n t c o s t ;  

Page 5: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 5/26

 

i n t o p ;  

} D C e l l ;  

v o i d g e r a S a i d a D E ( c h a r * s 1 , c h a r * s 2 )  

i n t m = s t r l e n ( s 1 ) ;  

i n t n = s t r l e n ( s 2 ) ;  

D C e l l D [ m + 1 ] [ n + 1 ] ;  

i n t t , i , j , v 1 , v 2 , v 3 ;  

f o r ( i = 0 ; i < = m ; i + + ) {  

D [ i ] [ 0 ] . c o s t = i ;  

D [ i ] [ 0 ] . o p = D E L E T I O N ;  

f o r ( j = 0 ; j < = n ; j + + ) {  

D [ 0 ] [ j ] . c o s t = j ;  

D [ 0 ] [ j ] . o p = I N S E R T I O N ;  

f o r ( i = 1 ; i < = m ; i + + ) {  

f o r ( j = 1 ; j < = n ; j + + ) {  

t = ( s 1 [ i - 1 ] ! = s 2 [ j - 1 ] ) ;  

v 1 = D [ i - 1 ] [ j ] . c o s t + 1 ; / / d e l e t i o n  

v 2 = D [ i ] [ j - 1 ] . c o s t + 1 ; / / i n s e r t i o n  

v 3 = D [ i - 1 ] [ j - 1 ] . c o s t + t ; / / s u b s t i t u t i o n  

i f ( v 1 < v 2 & & v 1 < v 3 ) {  

D [ i ] [ j ] . c o s t = v 1 ;  

D [ i ] [ j ] . o p = D E L E T I O N ;  

e l s e i f ( v 2 < = v 1 & & v 2 < = v 3 ) {  

D [ i ] [ j ] . c o s t = v 2 ;  

D [ i ] [ j ] . o p = I N S E R T I O N ;  

e l s e i f ( v 3 < = v 1 & & v 3 < v 2 ) {  

D [ i ] [ j ] . c o s t = v 3 ;  

i f ( t ) D [ i ] [ j ] . o p = S U B S T I T U T I O N ;  

e l s e D [ i ] [ j ] . o p = M A T C H ;  

f p r i n t f ( s t d o u t , " % d \ n " , D [ m ] [ n ] . c o s t ) ;  

F o i d e n i d o u m r e g i s t r o (  DCell

) q u e p o s s u i d o i s v a l o r e s : o c u s t o (  cost

) e a o p e r a ç ã o  

( op

) . E s t e r e g i s t r o s e r á o c o n t e ú d o d e c a d a c é l u l a d a m a t r i z q u e a r m a z e n a o s c u s t o s d e  

e d i ç ã o (  D

) . E s t e r e g i s t r o é n e c e s s á r i o , p o i s p a r a c a d a c a l c u l o d e e d i ç ã o r e a l i z a d o , d e v e - s e  

a r m a z e n a r q u a l f o i a o p e r a ç ã o q u e g e r o u o c u s t o a t u a l .  

O p r o c e d i m e n t o   g e r a S a i d a D E ( . . )   r e c e b e d o i s s t r i n g s (  s1 e  s2) c o m o p a r â m e t r o s f o r -  

m a i s . I n i c i a l m e n t e , d e c l a r a - s e d o i s i n t e i r o s  m

e n

e a t r i b u i a e l e s o s t a m a n h o s d o s r e s p e c -  

Page 6: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 6/26

 

t i v o s s t r i n g s (  m = length(s1)

e n = length(s2)

) . C r i a u m a m a t r i z  D

d e r e g i s t r o s  DCell

d e 

d i m e n s õ e s  m × n

. E m s e g u i d a s ã o i n i c i a l i z a d o s v á r i a s v a r i á v e i s i n t e i r a s a u x i l i a r e s (  t

, i

, j

v1, 

v2e 

v3) . 

N o s d o i s p r i m e i r o s  f or

' s , o c u s t o d a s c é l u l a s d a p r i m e i r a l i n h a e d a p r i m e i r a c o l u n a  

s ã o i n i c i a l i z a d a s c o m v a l o r e s i n t e i r o s c r e s e n t e s (  D[i][0] = i

e D[0][ j] = j

, p a r a  0 ≤ i, j ≤

m, nr e s p e c t i v a m e n t e ) . P a r a a p r i m e i r a l i n h a , t o d a s a s c é l u l a s r e g i s t r a m o p e r a ç õ e s d e  

r e m o ç ã o   ( DELETION 

) , p o i s p a r a t r a n s f o r m a r u m s t r i n g  s1[1..m]

e m u m s t r i n g  s2[1..0]

s ã o n e c e s s á r i a s  m

r e m o ç õ e s . P a r a a p r i m e i r a c o l u n a , t o d a s a s c é l u l a s r e g i s t r a m o p e r a ç õ e s  

d e  i n s e r ç ã o   ( INSERTION 

) , a n a l o g a m e n t e , p a r a t r a n s f o r m a r u m s t r i n g  s1[1..0]

e m u m  

s t r i n g  s2[1..n]

, s ã o n e c e s s á r i a s  n

, i n s e r ç õ e s .  

O s d o i s  f or

' s a n i n h a d o s p e r c o r r e m c a d a c é l u l a d a m a t r i z d e r e g i s t r o s c a l c u l a n d o o s  

c u s t o s e a s r e s p e c t i v a s o p e r a ç õ e s . P r i m e i r a m e n t e , é v e r i c a d o s e o c a r a c t e r  s1[i]

c a s a c o m  

o c a r a c t e r  s2[ j]

, a t r i b u i n d o a  t

, 1 , s e h o u v e o c a s a m e n t o , e 0 , c a s o c o n t r á r i o . O c u s t o a s e r  

a t r i b u i d o a o r e g i s t r o d a c é c u l a a t u a l , é o m e n o r c u s t o e n t r e u m a   r e m o ç ã o   ( 

D[i − 1][ j] + 1) , 

u m a  i n s e r ç ã o   ( D[i − 1][ j] + 1

) e u m a   s u b s t i t u i ç ã o   ( D[i − 1][ j − 1 ] + 1

) , s e n a u m h o u v e u m  

c a s a m e n t o , o u u m   c a s a m e n t o   ( D[i

−1][ j

−1]

) , c a s o c o n t r á r i o . A s o p e r a ç õ e s r e g i s t r a d a s  

s ã o r e s p e c t i v a m e n t e   DELETION ,  INSERTION ,  SUBSTITUTION  o u  MATCH . A 

o r d e m d e p r i o r i d a d e , d a m a i o r p a r a a m e n o r , é a s e g u i n t e :  INSERTION 

( v2 ≤ v1

v2 ≤ v3) , 

SUBSTITUTION o u 

MATCH ( v3 ≤ v2

e v3 ≤ v1

) e , p o r m ,  DELETION 

( v1 < v2

e v1 < v3

) . 

A s e g u i r é a p r e s e n t a d o o c ó d i g o f o n t e d a p a r t e q u e i m p l e m e n t a a i m p r e s s ã o d a s o p e -  

r a ç õ e s :  

/ / g e r a l i s t a d e o p e r a ç õ e s  

f o r ( i = m , j = n ; ( i > = 0 & & j > 0 ) | | ( i > 0 & & j > = 0 ) ; ) {  

s w i t c h ( D [ i ] [ j ] . o p ) {  

c a s e I N S E R T I O N : {  

/ / c o l o q u e 1  

f p r i n t f ( s t d o u t , " % d " , 1 ) ;  

j - - ;  

b r e a k ;  

c a s e D E L E T I O N : {  

/ / c o l o q u e 2 n a s t r i n g  

f p r i n t f ( s t d o u t , " % d " , 2 ) ;  

i - - ;  

b r e a k ;  

c a s e S U B S T I T U T I O N : {  

/ / c o l o q u e 3  

f p r i n t f ( s t d o u t , " % d " , 3 ) ;  

i - - ; j - - ;  

b r e a k ;  

c a s e M A T C H : {  

i - - ; j - - ;  

b r e a k ;  

f p r i n t f ( s t d o u t , " \ n " ) ;  

Page 7: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 7/26

 

A s o p e r a ç õ e s s ã o i m p r e s s a s e m o r d e m i n v e r s a . O p r o c e s s a m e n t o c o m e ç a n a c é l u l a  

D[m][n]. D a í , e n q u a n t o n ã o p r o c e s s a r t o d o o c a m i n h o d e e d i ç ã o , i . e .  

ie 

jd i f e r e n t e s d e  

0, a e x e c u ç ã o n ã o p á r a . P a r a c a d a c é c u l a , s e f o i r e g i s t r a d o u m a o p e r a ç ã o q u e g e r o u u m  

c u s t o , o u s e j a , u m a   i n s e r ç ã o   , u m a   r e m o ç ã o   o u u m a   s u b s t i t u i ç ã o   , s ã o i m p r e s s o s o s v a l o r e s  

1, 

2o u 

3, r e s p e c t i v a m e n t e , n o a r q u i v o d e s a í d a .  

1 . 4 E x e m p l o P r á t i c o      

C o m o e x e m p l o p r á t i c o , a e x e c u ç ã o d o a l g o r i t m o d e d i s t â n c i a d e e d i ç ã o a p r e s e n m t a d o g e r a  

a s e g u i n t e m a t r i z d e c u s t o s p a r a a t r a n s f o r m a ç ã o d e   m a t r a n d a   e m  s a t u r a d a s  . E m c a d a ,  

c é l u l a é r e g i s t r a d o o c u s t o d e e d i ç ã o a t u a l e a o p e r a ç ã o q u e g e r o u o v a l o r d o c u s t o (  I 

i n s e r ç ã o ,  D

: r e m o ç ã o ,  S 

: s u b s t i t u i ç ã o e  M 

: c a s a m e n t o ) . A o p e r a ç ã o r e g i s t r a d a e m c a d a  

c é l u l a d i r e c i o n a o c a m i n h a m e n t o p a r a i m p r e s s ã o d a s o p e r a ç õ e s .  

s a t u r a d a s0 1I  2I  3I  4I  5I  6I  7I  8I  9I m 1D 1S  2I  3I  4I  5I  6I  7I  8I  9I a 2D 2S  1M  2I  3I  4I  5I  6I  7I  8I t 3D 3S  2D 1M  2I  3I  4I  5I  6I  7I r 4D 4S  3D 2D 2S  2M  3I  4I  5I  6I a 5D 5S  4M  3D 3S  3S  2M  3I  4I  5I n 6D 6S  5D 4D 4S  4S  3D 3S  4I  5I d 7D 7S  6D 5D 5S  5S  4D 3M  4I  5I a 8D 8S  7M  6D 6S  6S  5M  3D 3M  4I 

O c a m i n h a m e n t o i n i c i a - s e , c o m o j á d i t o a n t e s , n a c é l u l a  D[m][n]

. D u r a n t e o c a m i -  

n h a m e n t o , c o m o e s p e c i c a d o p a r a a s a i d a d e s t e e x e r c í c i o , s e f o r e n c o n t r a d o u m a i n s e r ç ã o  

( S 

) , s e r á i m p r e s s o n o a r q u i v o d e s a í d a o v a l o r 1 e o c a m i n h a m e n t o s e g u e p a r a a c o l u n a  

a n t e r i o r ( c é l u l a  D[i][ j − 1]

) . S e f o r e n c o n t r a d o u m a r e m o ç ã o (  D

) , s e r á i m p r e s s o o v a l o r 2 e  

o c a m i n h a m e n t o s e g u e p a r a a l i n h a a n t e r i o r ( c é l u l a  

D[i − 1][ j]) . C a s o f o r e n c o n t r a d o u m a  

s u b s t i t u i ç ã o (  S 

) , s e r á i m p r e s s o o v a l o r 3 n o a r q u i v o d e s a í d a e o c a m i n h a m e n t o s e g u e p e l a  

d i a g o n a l ( c é l u l a  D[i−1][ j −1]

) . F i n a l m e n t e , s e f o r e n c o n t r a d o u m a o p e r a ç ã o d e c a s a m e n t o  

( M 

) , s i m p l e s m e n t e o c a m i n h a m e n t o a n d a p e l a d i a g o n a l (  D[i][ j]

) . 

P a r a e s t e e x e m p l o , o c a m i n h o d e i m p r e s s ã o f e i t o é o s e g u i n t e : I M M D M M I M M S . P a r a  

e s t e c a m i n h o é g e r a d o a s e g u i n t e s a í d a : 1 2 1 3 . O s i g n i c a d o d e s t a s a í d a é a s e g u i n t e :  

•i n s i r a ' s ' n a ú l t i m a p o s i ç ã o ( m a t r a n d a S ) ;  

•r e m o v a ' n ' d a s e x t a p o s i ç ã o ( m a t r a D A S ) ;  

•i n s i r a ' u ' n a q u a r t a p o s i ç ã o ( m a t U R A D A S ) ;  

•s u b s t i t u a ' m ' p o r ' s ' n a p r i m e i r a p o s i ç ã o ( S A T U R A D A S ) ;  

Page 8: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 8/26

 

2 C o n j u n t o I n d e p e n d e n t e d e V é r t i c e s    

O  c o n j u n t o i n d e p e n d e n t e d e V é r t i c e s   ( C I ) d e u m g r a f o  

G = (V, A)é c o n s t i t u i d o d o s u b -  

c o n j u n t o  V  ⊆ V 

, t a l q u e  v, w ∈ V  ⇒ (v, w) ∈ A

, i s t o é , t o d o p a r d e v é r t i c e s d e  V 

é n ã o  

a d j a c e n t e ( i . e .  V 

é u m s u b g r a f o t o t a l m e n t e d e s c o n e c t a d o ) [ 5 ] .  

U m  c o n j u n t o i n d e p e n d e n t e   é  m a x i m a l   q u a n d o n ã o e x i s t e n e n h u m o u t r o c o n j u n t o i n d e -  

p e n d e n t e q u e o c o n t e n h a ( i . e . u m c o n j u n t o q u e n ã o p o d e s e r c o m p l e t a d o ) . E s t e é   m á x i m o  

s e t o d o s o s o u t r o s c o n j u n t o s i n d e p e n d e n t e s t ê m c a r d i n a l i d a d e m e n o r o u i g u a l . P o r e x e m -  

p l o , o c o n j u n t o   {2, 3} n a F i g u r a 1 n ã o é u m C I m a x i m a l e m q u a n t o o s c o n j u n t o s { 0 , 1 } e  

{ 2 , 3 , 4 } s ã o c o n j u n t o s m a x i m a i s , s e n d o q u e o c o n j u n t o  {2, 3, 4}

é u m C I m á x i m o .  

F i g u r a 1 : G r a f o e x e m p l o :  G(V, A)

c o m V  = {0, 1, 2, 3, 4}

e A =

{(0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4)}

E s t e p r o b l e m a t e m v á r i a s a p l i c a ç õ e s p r á t i c a s , c o m o p o r e x e m p l o : ( i ) r e u n i r o m a i o r  

n ú m e r o p o s s í v e l d e p e s s o a s d o s e u c í r c u l o d e a m i z a d e s q u e n ã o s e c o n h e c e m ; ( i i ) o c o n j u n t o  

m a x i m a l d e p r o j e t o s q u e p o d e m s e r e x e c u t a d o s e m p a r a l e l o e m u m ú n i c o p e r í o d o d e t e m p o ;  

e ( i i i ) r e s o l v e r o p r o b l e m a d a s  n

r a i n h a s .  

O p r o b l e m a d e e n c o n t r a r o C I m á x i m o d e u m g r a f o ( P C I ) é   N P - C o m p l e t o  , p o i s n ã o  

e x s t e u m a l g o r i t m o d e t e r m i n i s t a q u e o r e s o l v a e m t e m p o p o l i n o m i a l e o p r o b l e m a d o c l i q u e  

( P C ) p o d e s e r r e d u z i d o p o l i n o m i a l m e n t e a o P C I .  

N a s p r ó x i m a s s e ç õ e s s ã o a p r e s e n t a d o s a l g o r i t m o s q u e r e s o l v e m o P C I d e m a n e i r a ó t i m a  

( S e ç ã o 2 . 1 ) e a p r o x i m a d a ( S e ç ã o 2 . 3 ) , u m a l g o r i t m o d e r e d u c a o p o l i n o m i a l d o P C a o P C I  

( S e ç ã o 2 . 2 ) , u m a a n á l i s e d a s o l u ç ã o a p r o x i m a d a ( S e ç ã o  ? ? 

) e , p o r m , u m a a n á l i s e d o s  

r e s u l t a d o s e m p í r i c o s é a p r e s e n t a d a ( S e ç ã o  ? ? 

) . 

T o d o s o s a l g o r i t m o s a p r e s e n t a d o s n a s s e ç õ e s a s e g u i r u t i l i z a m a i m p l e m e n t a ç ã o d e g r a f o  

p o r m a t r i z d e a d i j a c ê n c i a s a p r e s e n t a d o p o r [ 5 ] c u j o c ó d i g o f o n t e é l i s t a d o n o A p ê n d i c e  ? ? 

2 . 1 S o l u ç ã o Ó t i m a      

O p s e u d o - c ó d i g o d e u m a l g o r i t m o f o r ç a b r u t a q u e g e r a u m a s o l u ç ã o ó t i m a p a r a o p r o b l e m a  

d o c o n u j u n t o i n d e p e n d e n t e ( P C I ) é a p r e s e n t a d o a b a i x o e m A l g o r i t m o 2 ( C ó d i g o f o n t e  

d i s p o n í v e l n o A p ê n d i c e C ) . A i d é i a é e n u m e r a r t o d o s o s c o n j u n t o s  

S  ⊆ V , v e r i c a n d o s e  

Page 9: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 9/26

 

c a d a u m é c o n j u n t o i n d e p e n d e n t e e a r m a z e n a n d o o m a i o r d e l e s e m  S max ( i . e . o m a i o r C I  

m a x i m a l ) .  

A l g o r i t m o 2   A l g o r i t m o f o r ç a b r u t a p a r a o P C I .  

1 :  C I n d e p F B   ( G

2 :  S, S max; { c o n j u n t o s d e v é r t i c e s }  

3 : 

S max = ∅; 

4 :  { v e r i c a t o d o s o s s u b c o n j u n t o s d e V }  

5 :  f o r a l l  S  ⊆ V 

d o 

6 :  i f  i s C I n d e p  (G, S )

A N D |S | > |S max| t h e n  

7 : 

S max = S ; 

8 : 

e n d i f  

9 :  e n d f o r  

1 0 :  p r i n t  (S max)

I n i c i a l m e n t e ,   S max i n i c i a - s e c o m o v a z i o ( l i n h a 3 ) . A s s i m ,   |S max| = 0. N a l i n h a 5  

e n u m e r a m - s e t o d o s o s s u b c o n j u n t o s  S 

d e V 

. O a l g o r i t m o q u e f a z e s t a e n u m e r a ç ã o é s i m -  

p l e s m e n t e u m q u e g e r a t o d a s a s c o m b i n a ç õ e s d e v é r t i c e s p o s s í v e i s . P o r e x e m p l o , d a d o  

o c o n j u n t o d e v é r t i c e s  {0, 1, 2, 3, 4}

, a l g u m a s c o m b i n a ç õ e s p o s s í v e i s s ã o  {0, 1, 2}

, {1, 3, 4}

{0, 2, 4}, 

{2, 3, 4}e t c . E n t ã o , p a r a c a d a  

S  ⊆ V , é v e r i c a d o s e  

S é u m c o n j u n t o i n d e -  

p e n d e n t e d e v é r t i c e s e s e  S 

c o n t é m m a i s v é r t i c e s q u e  S max ( 

|S | > |S max| ) . C a s o s e j a ,  

S max = S , o u s e j a , s e t o r n a o m a i o r c o n j u n t o i n d e p e n d e n t e m a x i m a l e n c o n t r a d o a t é e n -  

t ã o . A t é o n a l d o p r o c e s s a m e n t o , t o d o s o s c o n j u n t o s i n d e p e n d e n t e s m a x i m a i s t e r ã o s i d o s  

d e s c o b e r t o s e o m a i o r d e l e s s e r á c o n h e c i d o .  

A c o m p l e x i d a d e d e s t e a l g o r i t m o é e x p o n e n c i a l , p o i s s ã o g e r a d o s  2N 

c o m b i n a ç õ e s d e  

v é r t i c e s , o n d e  N 

é o n ú m e r o d e v é r t i c e s d o G r a f o . P o r e s s a r a z ã o , a e x e c u ç ã o d e s t e  

a l g o r i t m o é v i á v e l s o m e n t e p a r a o s c a s o s e m q u e   N  é p e q u e n o .  

E m t e s t e s r e a l i z a d o s c o m e s t e a l g o r i t m o , o m a i o r p r o b l e m a q u e s e c o n s e g u i u a s o l u ç ã o  

ó t i m a f o i u m d e t a m a n h o  N  = 34

e l e v o u c e r c a d e 1 , 5 h p a r a t e r m i n a r ! F a z e n d o u m  

e s t i m a t i v a i n t e r e s s a n t e : c a s o o t a m a n h o d o p r o b l e m a f o s s e d e z v e z e s m a i o r , i . e .  N  = 340

t e m o s o s e g u i n t e :  

2N  5400s

210N  (5400)10s

2, 108325193e + 37s

O u s e j a , e s t e a l g o r i t m o d e f o r ç a b r u t a l e v a r i a c e r c a d e  1029

a n o s p a r a r e s o l v ê - l o !  

2 . 2 R e d u ç ã o d o C l i q u e    

S e g u n d o [ 5 ] ,   c l i q u e   d e u m g r a f o  

G = (V, A)é c o n s t i t u i d o d o s u b c o n j u n t o  

V  ⊆ V , t a l  

q u e v, w ∈ V  ⇒ (v, w) ∈ A

, i s t o é , t o d o p a r d e v é r t i c e s d e  V 

é a d j a c e n t e (  V 

é u m 

s u b g r a f o c o m p l e t o ) . N o g r a f o e x e m p l o a p r e s e n t a d o n a F i g u r a 1 ,  V  = {1, 2}

é u m e x e m p l o  

d e c a r d i n a l i d a d e 2 .  

U m a  t r a n s f o r m a ç ã o p o l i n o m i a l   é u m c o n c e i t o i m p o r t a n t e n a t e o r i a   N P  - c o m p l e t o . E s t e  

c o n c e i t o d i z q u e s e j a m  Π1 e 

Π2 p r o b l e m a s " s i m / n ã o " . S u p o n h a q u e e x i s t a u m a l g o r i t m o  

A2 p a r a r e s o l v e r  Π2 . S e f o r p o s s í v e l t r a n s f o r m a r  

Π1 e m Π2 e s e n d o c o n h e c i d o u m p r o c e s s o  

d e t r a n s f o r m a r a s o l u ç ã o d e  Π2 e m u m a s o l u ç ã o d e  

Π1 , e n t ã o o a l g o r i t m o  A2 , p o d e s e r  

Page 10: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 10/26

 

u t i l i z a d o p a r a r e s o l v e r  Π1 . S e a s t r a n s f o r m a ç õ e s n o s d o i s s e n t i d o s p u d e r e m s e r r e a l i z a d a s  

e m t e m p o p o l i n o m i a l , e n t ã o  Π1 é  p o l i n o m i a l m e n t e t r a n s f o r m á v e l   e m 

Π2 , o u s e j a ,  Π1 ∝ Π2 . 

C o n s i d e r e  Π1 o p r o b l e m a d o c l i q u e e  

Π2 o p r o b l e m a d o c o n j u n t o i n d e p e n d e n t e d e v é r t i -  

c e s . A i n s t â n c i a  I 

d o c l i q u e c o n s i s t e e m u m g r a f o  G(V, A)

e u m i n t e i r o  k > 0

. A i n s t â n c i a  

f (I )d e c o n j u n t o i n d e p e n d e n t e p o d e s e r o b t i d a c o n s i d e r a n d o - s e o g r a f o c o m p l e m e n t a r  

Gd e 

Ge o m e s m o i n t e i r o  

k. A f u n ç ã o  

f (I )é u m a t r a n s f o r m a ç ã o p o l i n o m i a l p o r q u e :  

• Gp o d e s e r o b t i d o a p a r t i r d e G e m t e m p o p o l i n o m i a l .  

• Gp o s s u i c l i q u e d e t a m a n h o  

≥ K s e e s o m e n t e  

Gp o s s u i c o n j u n t o i n d e p e n d e n t e d e  

v é r t i c e s d e t a m a n h o  ≥ k

P o r t a n t o , p o d e m o s u t i l i z a r o a l g o r i t m o a p r e s e n t a d o n a s e ç ã o a n t e r i o r , q u e g e r a a s o l u -  

ç ã o ó t i m a d o c o n j u n t o i n d e p e n d e n t e p a r a o b t e r a s o l u ç ã o , t a m b é m ó t i m a , p a r a o c l i q u e .  

O p r i m e i r o p a s s o é o b t e r o g r a f o c o m p l e m e n t a r  G

d e G

. O A l g o r i t m o 3 a p r e s e n t a u m  

p r o c e d i m e n t o p a r a s e o b t e r  G

a p a r t i r d e  G

A l g o r i t m o 3   A l g o r i t m o p a r a o b t e r  

G. 

1 : 

G C o m p l e m e n t a r  ( 

G(V, A)) 

2 : 

G(V , A); { g r a f o c o m p l e m e n t a r v a z i o }  

3 : 

V  = V ; 

4 :  { v e r i c a t o d a s a s a r e s t a s d e A }  

5 :  f o r a l l  (u, v) ∈ A

d o 

6 :  i f (u, v) ∈ A

t h e n  

7 : 

A = A + (u, v); 

8 :  e n d i f  

9 :  e n d f o r  

1 0 : 

r e t u r n  

G; 

A i m p l e m e n t a ç ã o d e s t e a l g o r i t m o é a p r e s e n t a d o n o n o A p ê n d i c e C . E s t e a l g o r i t m o g e r a  

u m g r a f o  G

d e G

. P a r a o g r a f o d a F i g u r a 1 , e s t e a l g o r i t m o g e r a o o g r a f o c o m p l e m e n t a r  

a p r e s e n t a d o n a F i g u r a 2 .  

F i g u r a 2 : G r a f o c o m p l e m e n t a r  G(V , A)

Page 11: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 11/26

 

2 . 3 A l g o r i t m o A p r o x i m a d o      

I n i c i a l m e n t e , p a r e c e - n o s i n t u i t i v o q u e , d a d o u m v e r t i c e  v

, p r o c u r a r o s v e r t i c e s n ã o a d -  

 j a c e n t e s n o c o n j u n t o d o s v e r t i c e s n ã o v i z i n h o s a  v

, l e v a - n o s a u m a s o l u ç ã o d o c o n j u n t o  

i n d e p e n d e n t e d e u m g r a f o . S e g u n d o [ 1 ] , a r á p i d a a c u m u l a ç ã o p e l a p e s q u i s a r e c u r s i v a n o s  

n ã o v i z i n h o s p a r e c e s e r a t r a t i v a . P o r é m , e s t a h e u r í s t i c a p o d e i g n o r a r c o n j u n t o s i n d e p e n -  

d e n t e s m a i o r e s q u e p o d e m e s t a r c o n t i d o s n a v i z i n h a n ç a d e  v

, o q u e p o d e g e r a r n o p i o r c a s o  

u m a s o l u ç ã o m u i t o r u i m .  

U m a p o s s í v e l s o l u ç ã o p a r a e s t a d e c i ê n c i a , s e r i a b u s c a r c o n j u n t o s i n d e p e n d e n t e s n a  

v i n z i n h a n ç a d e  v

e n a n ã o - v i z i n h a n ç a d e  v

, s e l e c i o n a n d o c o m o r e u l t a d o o m a i o r . E s t a  

é a i d é i a b á s i c a d o a l g o r i t m o d e   R a m s e y  , a p r e s e n t a d o a s e g u i r ( V e j a i m p l e m e n t a ç ã o n o  

A p ê n d i c e C ) .  

A l g o r i t m o 4   A l g o r i t m o d e   R a m s e y  

1 :  R a m s e y  ( 

G) 

2 :  i f G = ∅

t h e n  

3 : 

r e t u r n  

(∅, ∅); 

4 :  e n d i f  

5 :  c h o o s e s o m e  v ∈ G

6 : 

(C 1, I 1) ←R a m s e y  

(N (v)); 

7 : 

(C 2, I 2) ←R a m s e y  

(N (v)); 

8 :  r e t u r n   l a r g e r o f  (C 1 ∪ {v}

C 2), l a r g e r o f  

(I 1, I 2 ∪ {v}); 

S e o l h a r m o s o c o m p o r t a m e n t o d o a l g o r i t m o , v e r e m o s q u e e s t e q u e b r a o p r o b l e m a e m  

u m a á r v o r e d e s u b p r o b l e m a s , o u s e j a , o a l g o r i t m o t r a n s f o r m a o g r a f o e m u m a á r v o r e  

b i n á r i a o n d e c a d a n o d o i n t e r n o é a d j a c e n t e a t o d o s o s s e u s d e s c e n d e n t e s e s q u e r d o s e n ã o  

a d j a c e n t e s a t o d o s o s s e u s d e s c e n d e n t e s d i r e i t o s . D e s t a f o r m a , o r e s u l t a d o e n c o n t r a d o  

p o r e s t e a l g o r i t m o e s t á r e l a c i o n a d o c o m o c a m i n h o d e s t a á r v o r e c o m m a i o r n ú m e r o d e  

a r e s t a s ã d i r e i t a . P o r t a n t o , o t a m a n h o d o c o n j u n t o i n d e p e n d e n t e d e v e r t i c e s e n c o n t r a d o é  

o t a m a n h o d o m a i o r c a m i n h o c o m a r e s t a s a d i r e i t a n a a r v o r e m a i s u m . O c l i q u e d o g r a f o  

é e n c o n t r a d o d e m a n e i r a a n á l o g a p e r c o r r e n d o a s a r e s t a s à e s q u e r d a .  

A s s u m a , p o r e x e m p l o , u m g r a f o  G

q u e n ã o c o n t é m t r i â n g u l o s . D e s t a f o r m a , o a l g o r i t m o  

n a u m é c a p a z d e e n c o n t r a r n e n h u m c l i q u e d e t a m a n h o m e n o r o u i g u a l a 2 , e n e n h u m  

c a m i n h o n a á r v o r e g e r a d a p e l o a l g o r i t m o p o s s u i m a i s q u e u m a a r e s t a a e s q u e r d a .  

D e a c o r d o c o m [ 1 ] , o u o c a m i n h o m a i s a d i r e i t a t e m  

√n

n o d o s , o u e x i s t e m m e n o s q u e  √n

c a m i n h o s n a á r v o r e , o n d e u m d e s s e s c a m i n h o s t e m m a i s q u e  

√n

n o d o s . D e s t a f o r m a , o  

a l g o r i t m o   R a m s e y   e n c o n t r a u m c o n j u n t o i n d e p e n d e n t e c o m t a m a n h o n o m í n i m o  

√n

. E s t e  

a l g o r i t m o f u n c i o n a b e m p a r a g r a f o s q u e n ã o p o s s u e m g r a n d e s c l i q u e s . C a s o c o n t r á r i o , n ã o  

s e p o d e f a z e r n e h u m a a r m a t i v a a c e r c a d e s u a p e r f o r m a c e . U m a p r o p o s t a é l i v r a r - s e d o s  

g r a n d e s c l i q u e s e a p l i c a r o   R a m s e y   s o b r e o g r a f o r e s u l t a n t e . O A l g o r i t m o 5 a p r e s e n t a e s t a  

s o l u ç ã o p r o p o s t a p o r [ 1 ] .  

O a l g o r i t m o   C l i q u e R e m o v a l   c h a m a r e p e t i d a m e n t e o   R a m s e y   e r e m o v e o s c l i q u e s e n -  

c o n t r a d o s d o g r a f o a t é q u e e l e s e t o r n e v a z i o . F i n a l m e n t e , e l e r e t o r n a o m a i o r c o n j u n t o  

i n d e p e n d e n t e e n c o n t r a d o j u n t a m e n t e c o m u m c o n j u n t o d e c l i q u e s d i s j u n t o s q u e f o r m a m  

u m a p a r t i ç ã o e m  G

A p r o v a d e q u e a r a z ã o d e a p r o x i m a ç ã o d o   C l i q u e R e m o v a l  , e n c o n t r a d a e m [ 4 ] , é a p r e -  

s e n t a d a a s e g u i r :  

T e o r e m a :  

A r a z ã o d e a p r o x i m a ç ã o d o   C l i q u e R e m o v a l   é O(n/log2n)

P r o v a :  

S e j a  

CC o n ú m e r o d e c l i q u e s e n c o n t r a d o s p o r   C l i q u e R e m o v a l   e s e j a  

CC 0o 

n ú m e r o d e c l i q u e s r e m o v i d o s a n t e s d o g r a f o c h e g a r a  n0 = n

log2n. S e j a  

to t a m a n h o d o m e n o r  

Page 12: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 12/26

 

A l g o r i t m o 5   A l g o r i t m o d o   C l i q u e R e m o v a l  

1 :  C l i q u e R e m o v a l  ( 

G) 

2 : 

i ← 1; 

3 : 

(C i, I i) ←R a m s e y  

(G); 

4 :  w h i l e  G

=

∅d o 

5 :  G ← G − C i ; 

6 : 

i ← i + 1; 

7 : 

(C i, I i) ←R a m s e y  

(G); 

8 :  e n d w h i l e  

9 :  r e t u r n  ((maxi

 j=1I i), {C 1, C 2,...,C i}); 

d e s t e s c l i q u e s , q u e g e r a l m e n t e é p e l o m e n o s  log2n

. E n t ã o  CC 1 ≤ n

t e CC  ≤ n

t− n0 ≤ 2n

t . 

S e I 

é o c o n j u n t o d e v é r t i c e s r e t o r n a d o , t e m - s e q u e  |I | ≥ 4log2n/t ≥ 2log2n/t

. C o n -  

s i d e r e o p r o d u t o d a s d u a s r a z õ e s d e a p r o x i m a ç ã o d e   C l i q u e R e m o v a l  , ρα p a r a c o n j u n t o s  

i n d e p e n d e n t e s d e v é r t i c e e  

ρχp a r a p a r t i ç ã o d e c l i q u e s :  

ρα · ρχ =CC 

χ· α

|I | ≤ n

log2n· α

χ≤ n

log2n

o n d e  n

é o n ú m e r o d e v é r t i c e s ,  α

é o t a m a n h o d o c o n j u n t o i n d e p e n d e n t e m á x i m o e  χ

é o 

t a m a n h o d a p a r t i ç ã o d e  G

e m c l i q u e s .  

1 0 

Page 13: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 13/26

 

A C ó d i g o F o n t e d o a l g o r i t m o d e D . E .    

A b a i x o é a p r e n s e n t a d o o c ó d i g o f o n t e d a i m p l e m e n t a ç ã o d o a l g o r i t m o q u e c a l c u l a a d i s t â n -  

c i a d e e d i ç ã o j u n t o c o m o a l g o r i t m o q u e i m p r i m e a s o p e r a ç õ e s n e c e s s á r i a s p a r a t r a n s f o r m a r  

u m a p a l a v r a e m o u t r a (   f u n ç ã o g e r a S a i d a D E ( . . )  ) . 

# i n c l u d e < s t r i n g . h >  

# i n c l u d e " m o d u l e d i s t e d . h "  

# d e f i n e I N S E R T I O N 1  

# d e f i n e D E L E T I O N 2  

# d e f i n e S U B S T I T U T I O N 3  

# d e f i n e M A T C H 0  

t y p e d e f s t r u c t D C e l l {  

i n t c o s t ;  

i n t o p ;  

} D C e l l ;  

v o i d g e r a S a i d a D E ( c h a r * s 1 , c h a r * s 2 )  

i n t m = s t r l e n ( s 1 ) ;  

i n t n = s t r l e n ( s 2 ) ;  

D C e l l D [ m + 1 ] [ n + 1 ] ;  

i n t t , i , j , v 1 , v 2 , v 3 ;  

f o r ( i = 0 ; i < = m ; i + + ) {  

D [ i ] [ 0 ] . c o s t = i ;  

D [ i ] [ 0 ] . o p = D E L E T I O N ;  

f o r ( j = 0 ; j < = n ; j + + ) {  

D [ 0 ] [ j ] . c o s t = j ;  

D [ 0 ] [ j ] . o p = I N S E R T I O N ;  

f o r ( i = 1 ; i < = m ; i + + ) {  

f o r ( j = 1 ; j < = n ; j + + ) {  

t = ( s 1 [ i - 1 ] ! = s 2 [ j - 1 ] ) ;  

v 1 = D [ i - 1 ] [ j ] . c o s t + 1 ; / / d e l e t i o n  

v 2 = D [ i ] [ j - 1 ] . c o s t + 1 ; / / i n s e r t i o n  

v 3 = D [ i - 1 ] [ j - 1 ] . c o s t + t ; / / s u b s t i t u t i o n  

i f ( v 1 < v 2 & & v 1 < v 3 ) {  

D [ i ] [ j ] . c o s t = v 1 ; / / D E L E T I O N  

D [ i ] [ j ] . o p = D E L E T I O N ;  

e l s e i f ( v 2 < = v 1 & & v 2 < = v 3 ) {  

D [ i ] [ j ] . c o s t = v 2 ; / / I N S E R T I O N  

D [ i ] [ j ] . o p = I N S E R T I O N ;  

1 1 

Page 14: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 14/26

 

e l s e i f ( v 3 < = v 1 & & v 3 < v 2 ) {  

D [ i ] [ j ] . c o s t = v 3 ; / / S U B S T I T U T I O N O R M A T C H  

i f ( t ) D [ i ] [ j ] . o p = S U B S T I T U T I O N ;  

e l s e D [ i ] [ j ] . o p = M A T C H ;  

f p r i n t f ( s t d o u t , " % d \ n " , D [ m ] [ n ] . c o s t ) ;  

/ / g e r a l i s t a d e o p e r a ç õ e s  

f o r ( i = m , j = n ; ( i > = 0 & & j > 0 ) | | ( i > 0 & & j > = 0 ) ; ) {  

s w i t c h ( D [ i ] [ j ] . o p ) {  

c a s e I N S E R T I O N : {  

/ / c o l o q u e 1  

f p r i n t f ( s t d o u t , " % d " , 1 ) ;  

j - - ;  

b r e a k ;  

c a s e D E L E T I O N : {  

/ / c o l o q u e 2 n a s t r i n g  

f p r i n t f ( s t d o u t , " % d " , 2 ) ;  

i - - ;  

b r e a k ;  

c a s e S U B S T I T U T I O N : {  

/ / c o l o q u e 3  

f p r i n t f ( s t d o u t , " % d " , 3 ) ;  

i - - ; j - - ;  

b r e a k ;  

c a s e M A T C H : {  

i - - ; j - - ;  

b r e a k ;  

f p r i n t f ( s t d o u t , " \ n " ) ;  

v o i d g e r a S a i d a D i s t E d ( F I L E * A r q A v a l )  

/ * P r o c e s s a o a r q u i v o A r q A v a l d e a l g u m a f o r m a * /  

c h a r * p a l a v r a = ( c h a r * ) m a l l o c ( 2 0 * s i z e o f ( c h a r ) ) ;  

c h a r * s 1 = ( c h a r * ) m a l l o c ( 2 0 * s i z e o f ( c h a r ) ) ;  

c h a r * s 2 = ( c h a r * ) m a l l o c ( 2 0 * s i z e o f ( c h a r ) ) ;  

i n t i ;  

f s c a n f ( A r q A v a l , " % s \ n " , p a l a v r a ) ;  

f o r ( i = 1 ; ! f e o f ( A r q A v a l ) ; i + + )  

1 2 

Page 15: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 15/26

 

f p r i n t f ( s t d e r r , " % s \ n " , p a l a v r a ) ;  

i f ( i % 2 ) s t r c p y ( s 1 , p a l a v r a ) ;  

e l s e {  

s t r c p y ( s 2 , p a l a v r a ) ;  

/ * G e r a a s a i d a * /  

g e r a S a i d a D E ( s 1 , s 2 ) ;  

f s c a n f ( A r q A v a l , " % s \ n " , p a l a v r a ) ;  

i f ( i % 2 ) {  

f p r i n t f ( s t d e r r , " E r r o a o l e r a r q u i v o : n u m e r o d e p a l a v r a s d e v e s e r p a r ! " ) ;  

e l s e {  

f p r i n t f ( s t d e r r , " % s \ n " , p a l a v r a ) ;  

s t r c p y ( s 2 , p a l a v r a ) ;  

/ * G e r a a s a i d a * /  

g e r a S a i d a D E ( s 1 , s 2 ) ;  

1 3 

Page 16: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 16/26

 

B C ó d i g o F o n t e d a i m p l e m e n t a ç ã o d o G r a f o      

E m [ 5 ] é a p r e s e n t a d o a i m p l e m e n t a ç ã o d e u m G r a f o p o r m a t r i z d e a d j a c ê n c i a s . A s e g u i r é  

a p r e s e n t a d o o c o n t e ú d o s d o s a r q u i v o s   g r a f o m a t r i z . h   B . 1 e   g r a f o m a t r i z . c   B . 2 .  

B . 1 A r q u i v o c a b e ç a l h o      g r a f o m a t r i z . h  

I m p l e m e n t a ç ã o d o t i p o a b s t r a t o d e d a d o s g r a f o u t i l i z a d o e a l i s t a g e m d e s u a s o p e r a ç õ e s :  

# i f n d e f M O D U L E M A T R I Z _ H  

# d e f i n e M O D U L E M A T R I Z _ H  

# i n c l u d e < s t d l i b . h >  

# i n c l u d e < s t d i o . h >  

# d e f i n e M a x N u m V e r t i c e s 1 0 0  

# d e f i n e M a x N u m A r e s t a s 4 5 0 0  

# d e f i n e T R U E 1  

# d e f i n e F A L S E 0  

t y p e d e f i n t T i p o V a l o r V e r t i c e ;  

t y p e d e f i n t T i p o P e s o ;  

t y p e d e f s t r u c t T i p o G r a f o {  

T i p o P e s o M a t [ M a x N u m V e r t i c e s + 1 ] [ M a x N u m V e r t i c e s + 1 ] ;  

i n t N u m V e r t i c e s ;  

i n t N u m A r e s t a s ;  

} T i p o G r a f o ;  

t y p e d e f i n t P o i n t e r ;  

v o i d F G V a z i o ( T i p o G r a f o * G r a f o ) ;  

v o i d I n s e r e A r e s t a ( T i p o V a l o r V e r t i c e * V 1 , T i p o V a l o r V e r t i c e * V 2 ,  

T i p o P e s o * P e s o , T i p o G r a f o * G r a f o ) ;  

s h o r t E x i s t e A r e s t a ( T i p o V a l o r V e r t i c e V e r t i c e 1 ,  

T i p o V a l o r V e r t i c e V e r t i c e 2 , T i p o G r a f o * G r a f o ) ;  

/ * - - O p e r a d o r e s p a r a o b t e r a l i s t a d e a d j a c e n t e s - - * /  

s h o r t L i s t a A d j V a z i a ( T i p o V a l o r V e r t i c e * V e r t i c e , T i p o G r a f o * G r a f o ) ;  

P o i n t e r P r i m e i r o L i s t a A d j ( T i p o V a l o r V e r t i c e * V e r t i c e , T i p o G r a f o * G r a f o ) ;  

v o i d P r o x A d j ( T i p o V a l o r V e r t i c e * V e r t i c e , T i p o G r a f o * G r a f o ,  

T i p o V a l o r V e r t i c e * A d j , T i p o P e s o * P e s o , P o i n t e r * P r o x ,  

s h o r t * F i m L i s t a A d j ) ;  

v o i d R e t i r a A r e s t a ( T i p o V a l o r V e r t i c e * V 1 , T i p o V a l o r V e r t i c e * V 2 ,  

1 4 

Page 17: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 17/26

 

T i p o P e s o * P e s o , T i p o G r a f o * G r a f o ) ;  

v o i d L i b e r a G r a f o ( T i p o G r a f o * G r a f o ) ;  

v o i d I m p r i m e G r a f o ( T i p o G r a f o * G r a f o ) ;  

v o i d G r a f o T r a n s p o s t o ( T i p o G r a f o * G r a f o , T i p o G r a f o * G r a f o T ) ;  

# e n d i f  

B . 2 P r o g r a m a      g r a f o m a t r i z . c  

I m p l e m e n t a ç ã o d a s o p e r a ç õ e s s o b r e o g r a f o d i s p o n í v e i s :  

# i n c l u d e < s t d l i b . h >  

# i n c l u d e < s t d i o . h >  

# i n c l u d e " g r a f o m a t r i z . h "  

P o i n t e r A u x ;  

i n t i ;  

T i p o V a l o r V e r t i c e V 1 , V 2 , A d j ;  

T i p o P e s o P e s o ;  

T i p o G r a f o G r a f o , G r a f o t ;  

T i p o V a l o r V e r t i c e N V e r t i c e s ;  

s h o r t N A r e s t a s ;  

s h o r t F i m L i s t a A d j ;  

v o i d F G V a z i o ( T i p o G r a f o * G r a f o )  

s h o r t i , j ;  

f o r ( i = 0 ; i < = G r a f o - > N u m V e r t i c e s ; i + + ) {  

f o r ( j = 0 ; j < = G r a f o - > N u m V e r t i c e s ; j + + )  

G r a f o - > M a t [ i ] [ j ] = 0 ;  

v o i d I n s e r e A r e s t a ( T i p o V a l o r V e r t i c e * V 1 , T i p o V a l o r V e r t i c e * V 2 ,  

T i p o P e s o * P e s o , T i p o G r a f o * G r a f o )  

G r a f o - > M a t [ * V 1 ] [ * V 2 ] = * P e s o ;  

} / * I n s e r e A r e s t a * /  

s h o r t E x i s t e A r e s t a ( T i p o V a l o r V e r t i c e V e r t i c e 1 ,  

T i p o V a l o r V e r t i c e V e r t i c e 2 , T i p o G r a f o * G r a f o )  

r e t u r n ( G r a f o - > M a t [ V e r t i c e 1 ] [ V e r t i c e 2 ] > 0 ) ;  

} / * E x i s t e A r e s t a * /  

1 5 

Page 18: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 18/26

 

/ * - - O p e r a d o r e s p a r a o b t e r a l i s t a d e a d j a c e n t e s - - * /  

s h o r t L i s t a A d j V a z i a ( T i p o V a l o r V e r t i c e * V e r t i c e , T i p o G r a f o * G r a f o )  

P o i n t e r A u x = 0 ;  

s h o r t L i s t a V a z i a = T R U E ;  

w h i l e ( A u x < G r a f o - > N u m V e r t i c e s & & L i s t a V a z i a ) {  

i f ( G r a f o - > M a t [ * V e r t i c e ] [ A u x ] > 0 )  

L i s t a V a z i a = F A L S E ;  

e l s e  

A u x + + ;  

r e t u r n ( L i s t a V a z i a = = T R U E ) ;  

} / * L i s t a A d j V a z i a * /  

P o i n t e r P r i m e i r o L i s t a A d j ( T i p o V a l o r V e r t i c e * V e r t i c e , T i p o G r a f o * G r a f o )  

T i p o V a l o r V e r t i c e R e s u l t ;  

P o i n t e r A u x = 0 ;  

s h o r t L i s t a V a z i a = T R U E ;  

w h i l e ( A u x < G r a f o - > N u m V e r t i c e s & & L i s t a V a z i a ) {  

i f ( G r a f o - > M a t [ * V e r t i c e ] [ A u x ] > 0 ) {  

R e s u l t = A u x ;  

L i s t a V a z i a = F A L S E ;  

} e l s e  

A u x + + ;  

i f ( A u x = = G r a f o - > N u m V e r t i c e s )  

p r i n t f ( " E r r o : L i s t a a d j a c e n c i a v a z i a ( P r i m e i r o L i s t a A d j ) \ n " ) ;  

r e t u r n R e s u l t ;  

} / * P r i m e i r o L i s t a A d j * /  

v o i d P r o x A d j ( T i p o V a l o r V e r t i c e * V e r t i c e , T i p o G r a f o * G r a f o ,  

T i p o V a l o r V e r t i c e * A d j , T i p o P e s o * P e s o , P o i n t e r * P r o x ,  

s h o r t * F i m L i s t a A d j )  

{ / * - - R e t o r n a A d j a p o n t a d o p o r P r o x - - * /  

* A d j = * P r o x ;  

* P e s o = G r a f o - > M a t [ * V e r t i c e ] [ * P r o x ] ;  

( * P r o x ) + + ;  

w h i l e ( * P r o x < G r a f o - > N u m V e r t i c e s & & G r a f o - > M a t [ * V e r t i c e ] [ * P r o x ] = = 0 )  

( * P r o x ) + + ;  

i f ( * P r o x = = G r a f o - > N u m V e r t i c e s )  

* F i m L i s t a A d j = T R U E ;  

} / * P r o x A d j - * /  

v o i d R e t i r a A r e s t a ( T i p o V a l o r V e r t i c e * V 1 , T i p o V a l o r V e r t i c e * V 2 ,  

T i p o P e s o * P e s o , T i p o G r a f o * G r a f o )  

i f ( G r a f o - > M a t [ * V 1 ] [ * V 2 ] = = 0 )  

1 6 

Page 19: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 19/26

 

p r i n t f ( " A r e s t a n a o e x i s t e \ n " ) ;  

e l s e {  

* P e s o = G r a f o - > M a t [ * V 1 ] [ * V 2 ] ;  

G r a f o - > M a t [ * V 1 ] [ * V 2 ] = 0 ;  

} / * R e t i r a A r e s t a * /  

v o i d L i b e r a G r a f o ( T i p o G r a f o * G r a f o )  

{ / * N a o f a z n a d a n o c a s o d e m a t r i z e s d e a d j a c e n c i a * /  

} / * L i b e r a G r a f o * /  

v o i d I m p r i m e G r a f o ( T i p o G r a f o * G r a f o )  

s h o r t i , j ;  

p r i n t f ( " " ) ;  

f o r ( i = 0 ; i < = G r a f o - > N u m V e r t i c e s - 1 ; i + + )  

p r i n t f ( " % 3 d " , i ) ;  

p r i n t f ( " \ n " ) ;  

f o r ( i = 0 ; i < = G r a f o - > N u m V e r t i c e s - 1 ; i + + ) {  

p r i n t f ( " % 3 d " , i ) ;  

f o r ( j = 0 ; j < = G r a f o - > N u m V e r t i c e s - 1 ; j + + )  

p r i n t f ( " % 3 d " , G r a f o - > M a t [ i ] [ j ] ) ;  

p r i n t f ( " \ n " ) ;  

} / * I m p r i m e G r a f o * /  

v o i d G r a f o T r a n s p o s t o ( T i p o G r a f o * G r a f o , T i p o G r a f o * G r a f o T )  

T i p o V a l o r V e r t i c e v , A d j ;  

T i p o P e s o P e s o ;  

P o i n t e r A u x ;  

F G V a z i o ( G r a f o T ) ;  

G r a f o T - > N u m V e r t i c e s = G r a f o - > N u m V e r t i c e s ;  

G r a f o T - > N u m A r e s t a s = G r a f o - > N u m A r e s t a s ;  

f o r ( v = 0 ; v < = G r a f o - > N u m V e r t i c e s - 1 ; v + + ) {  

i f ( ! L i s t a A d j V a z i a ( & v , G r a f o ) ) {  

A u x = P r i m e i r o L i s t a A d j ( & v , G r a f o ) ;  

F i m L i s t a A d j = F A L S E ;  

w h i l e ( ! F i m L i s t a A d j ) {  

P r o x A d j ( & v , G r a f o , & A d j , & P e s o , & A u x , & F i m L i s t a A d j ) ;  

I n s e r e A r e s t a ( & A d j , & v , & P e s o , G r a f o T ) ;  

} / * G r a f o T r a n s p o s t o * /  

/ * E n d . * /  

1 7 

Page 20: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 20/26

 

C C ó d i g o F o n t e d o s A l g o r i t m o s p a r a o P C I    

A s e g u i r é a p r e s e n t a d o o c ó d i g o f o n t e d o a r q u i v o   m o d u l e i n d e p . c   q u e c o n t e m o a l g o r i t m o  

q u e e n c o n t r a a s o l u ç ã o ó t i m a p a r a o P C I ( f u n ç ã o   C I n d e p F B   ) , o a l g o r i t m o d e r e d u ç ã o d o  

C l i q u e p a r a o C I ( f u n ç ã o   C l i q u e R e d C I n d e p   ) e o q u e e n c o n t r a a s o l u ç ã o a p r o x i m a d a p a r a  

o P C I ( f u n ç ã o   R a m s e y   e  C l i q u e R e m o v a l  ) . 

# i n c l u d e < s y s / t i m e . h >  

# i n c l u d e " m o d u l e i n d e p . h "  

# i n c l u d e " g r a f o m a t r i z . h "  

/ * A l g o r i t m o F o r ç a B r u t a p a r a o P C I * /  

/ * B E G I N P C I F B * /  

s h o r t i s C I n d e p ( T i p o G r a f o * G , i n t * S , i n t k )  

s h o r t h a s A d j = F A L S E ;  

i n t i , j ;  

f o r ( i = 1 ; i < = k & & ! h a s A d j ; i + + ) {  

f o r ( j = 1 ; j < = k & & ! h a s A d j ; j + + ) {  

i f ( j ! = i )  

h a s A d j = E x i s t e A r e s t a ( S [ i ] , S [ j ] , G ) ;  

r e t u r n ! h a s A d j ;  

v o i d p r i n t C I n d e p ( i n t * S , i n t n )  

i n t i , j ;  

f o r ( i = 0 ; i < n ; i + + ) {  

f p r i n t f ( s t d o u t , " % d " , S [ i ] ) ;  

f p r i n t f ( s t d e r r , " % d " , S [ i ] ) ;  

v o i d C I n d e p F B ( T i p o G r a f o * G )  

i n t * S , * S _ m a x ;  

i n t i , k , N , l , l _ m a x ;  

N = G - > N u m V e r t i c e s ;  

S = ( i n t * ) m a l l o c ( ( N + 1 ) * s i z e o f ( i n t ) ) ;  

S _ m a x = ( i n t * ) m a l l o c ( N * s i z e o f ( i n t ) ) ;  

S [ 0 ] = - 1 ;  

k = 0 ;  

1 8 

Page 21: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 21/26

 

l _ m a x = 0 ;  

w h i l e ( T R U E ) {  

i f ( S [ k ] < ( N - 1 ) ) {  

S [ k + 1 ] = S [ k ] + 1 ;  

k + = 1 ;  

e l s e {  

S [ k - 1 ] + = 1 ;  

k - = 1 ;  

i f ( k = = 0 ) b r e a k ;  

i f ( k > l _ m a x & & i s C I n d e p ( G , S , k ) ) {  

f o r ( i = 1 ; i < = k ; i + + ) {  

S _ m a x [ i - 1 ] = S [ i ] ;  

l _ m a x = k ;  

p r i n t C I n d e p ( S _ m a x , l _ m a x ) ;  

/ * E n d P C I F B * /  

/ * A l g o r i t m o p a r a r e d u ç ã o p o l i n o m i a l d o C l i q u e a o C I * /  

/ * B e g i n R E D U C A O * /  

v o i d C l i q u e R e d C I n d e p ( T i p o G r a f o * G )  

T i p o G r a f o _ G ;  

T i p o V a l o r V e r t i c e u , v ;  

T i p o P e s o p ;  

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *  

T r a s n f o r m a c a o p o l i n o m i a l d a e n t r a d a d o  

c l i q u e n a e n t r a d a d o C I , i . e . c a l c u l a  

g r a f o _ G c o m p l e m e n t a r d e G :  

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /  

/ * S e j a G ( V , A ) e _ G ( _ V , _ A ) , _ V = V * /  

F G V a z i o ( & _ G ) ;  

_ G . N u m V e r t i c e s = G - > N u m V e r t i c e s ;  

p = 1 ;  

/ * P a r a t o d o u , v e m V * /  

f o r ( u = 0 ; u < _ G . N u m V e r t i c e s ; u + + ) {  

f o r ( v = 0 ; v < _ G . N u m V e r t i c e s ; v + + ) {  

1 9 

Page 22: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 22/26

 

/ * S e ( u ! = v ) e ( u , v ) n a o e s t a e m A * /  

i f ( u ! = v ) & & ( ! E x i s t e A r e s t a ( u , v , G ) ) {  

/ * _ A = _ A + ( u , v ) * /  

I n s e r e A r e s t a ( & u , & v , & p , & _ G ) ;  

/ / s o l u c a o d o C I = s o l u c a o d o C l i q u e  

C I n d e p F B ( & _ G ) ;  

/ * E n d R E D U C A O * /  

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * \  

A l g o r i t m o a p r o x i m a d o  

\ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /  

/ * B e g i n A P P R X * /  

v o i d p r i n t _ V ( s h o r t * S , i n t n )  

i n t i , j ;  

f o r ( i = 0 ; i < n ; i + + ) {  

i f ( S [ i ] ) {  

f p r i n t f ( s t d o u t , " % d " , i ) ;  

f p r i n t f ( s t d e r r , " % d " , i ) ;  

s h o r t v a z i o _ V ( s h o r t * V , s h o r t n )  

i n t v ;  

f o r ( v = 0 ; v < n ; v + + ) {  

i f ( V [ v ] ) r e t u r n F A L S E ;  

r e t u r n T R U E ;  

s h o r t * p u t v _ V ( T i p o V a l o r V e r t i c e v , s h o r t * V )  

V [ v ] = 1 ;  

r e t u r n V ;  

s h o r t * l a r g e r _ o f ( s h o r t * V 1 , s h o r t * V 2 , i n t n )  

i n t i , s 1 , s 2 ;  

s 1 = s 2 = 0 ;  

2 0 

Page 23: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 23/26

 

f o r ( i = 0 ; i < n ; i + + ) {  

s 1 + = V 1 [ i ] ;  

s 2 + = V 2 [ i ] ;  

r e t u r n ( ( s 1 > s 2 ) ? V 1 : V 2 ) ;  

s h o r t * n e i g h _ V ( T i p o G r a f o * G , T i p o V a l o r V e r t i c e v , s h o r t * V )  

s h o r t * _ V ;  

i n t u ;  

_ V = ( s h o r t * ) m a l l o c ( s i z e o f ( s h o r t ) * G - > N u m V e r t i c e s ) ;  

f o r ( u = 0 ; u < G - > N u m V e r t i c e s ; u + + ) {  

_ V [ u ] = ( ( u ! = v ) & & V [ u ] & & E x i s t e A r e s t a ( v , u , G ) ) ? 1 : 0 ;  

r e t u r n _ V ;  

s h o r t * n o n _ n e i g h _ V ( T i p o G r a f o * G , T i p o V a l o r V e r t i c e v , s h o r t * V )  

s h o r t * _ V ;  

i n t u ;  

_ V = ( s h o r t * ) m a l l o c ( s i z e o f ( s h o r t ) * G - > N u m V e r t i c e s ) ;  

f o r ( u = 0 ; u < G - > N u m V e r t i c e s ; u + + ) {  

_ V [ u ] = ( ( u = = v ) | | ! V [ u ] | | E x i s t e A r e s t a ( v , u , G ) ) ? 0 : 1 ;  

r e t u r n _ V ;  

v o i d n o n _ N ( T i p o G r a f o * G , T i p o V a l o r V e r t i c e v , s h o r t * V )  

i n t u , n ;  

n = G - > N u m V e r t i c e s ;  

f o r ( u = 0 ; u < n ; u + + ) {  

V [ u ] = ( ( u = = v ) | | ( ! V [ u ] | | E x i s t e A r e s t a ( v , u , G ) ) ) ? 0 : 1 ;  

T i p o V a l o r V e r t i c e c h o o s e _ v ( s h o r t * V , i n t N )  

s t r u c t t i m e v a l t ;  

/ * e s c o l h e a l e a t o r i a m e n t e u m v e r t i c e e m V * /  

T i p o V a l o r V e r t i c e v = 0 ;  

2 1 

Page 24: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 24/26

 

g e t t i m e o f d a y ( & t , N U L L ) ;  

s r a n d ( ( u n s i g n e d i n t ) t . t v _ u s e c ) ;  

v = ( i n t ) r a n d ( ) % N ;  

r e t u r n v ;  

s h o r t * * R a m s e y _ V ( T i p o G r a f o * G , s h o r t * V ) {  

T i p o V a l o r V e r t i c e v ;  

s h o r t * * C I , * * C I 1 , * * C I 2 ;  

i n t n ;  

n = G - > N u m V e r t i c e s ;  

C I = ( s h o r t * * ) m a l l o c ( 2 * s i z e o f ( s h o r t * ) ) ;  

i f ( v a z i o _ V ( V , n ) ) {  

C I = ( s h o r t * * ) m a l l o c ( 2 * s i z e o f ( s h o r t * ) ) ;  

C I [ 0 ] = ( s h o r t * ) m a l l o c ( n * s i z e o f ( s h o r t * ) ) ;  

C I [ 1 ] = ( s h o r t * ) m a l l o c ( n * s i z e o f ( s h o r t * ) ) ;  

r e t u r n C I ;  

v = c h o o s e _ v ( V , n ) ;  

C I 1 = R a m s e y _ V ( G , n e i g h _ V ( G , v , V ) ) ;  

C I 2 = R a m s e y _ V ( G , n o n _ n e i g h _ V ( G , v , V ) ) ;  

C I [ 0 ] = l a r g e r _ o f ( p u t v _ V ( v , C I 1 [ 0 ] ) , C I 2 [ 0 ] , n ) ;  

C I [ 1 ] = l a r g e r _ o f ( C I 1 [ 1 ] , p u t v _ V ( v , C I 2 [ 1 ] ) , n ) ;  

r e t u r n C I ;  

v o i d R a m s e y ( T i p o G r a f o * G )  

s h o r t * V , * * C I ;  

i n t i ;  

V = ( s h o r t * ) m a l l o c ( s i z e o f ( s h o r t ) * G - > N u m V e r t i c e s ) ;  

f o r ( i = 0 ; i < G - > N u m V e r t i c e s ; i + + ) {  

V [ i ] = 1 ;  

C I = R a m s e y _ V ( G , V ) ;  

p r i n t _ V ( C I [ 1 ] , G - > N u m V e r t i c e s ) ;  

2 2 

Page 25: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 25/26

 

v o i d r e m o v e _ c l i q u e ( T i p o G r a f o * G , s h o r t * * C I , s h o r t * V ) {  

i n t v ;  

f o r ( v = 0 ; v < G - > N u m V e r t i c e s ; v + + ) {  

i f ( C I [ 0 ] [ v ] & & V [ v ] ) V [ v ] = 0 ;  

v o i d C l i q u e R e m o v a l ( T i p o G r a f o * G ) {  

s h o r t * I S , * * C I i ;  

s h o r t * V ;  

i n t i ;  

V = ( s h o r t * ) c a l l o c ( G - > N u m V e r t i c e s , s i z e o f ( s h o r t ) ) ;  

f o r ( i = 0 ; i < G - > N u m V e r t i c e s ; i + + ) {  

V [ i ] = 1 ;  

C I i = R a m s e y _ V ( G , V ) ;  

w h i l e ( ! v a z i o _ V ( V , G - > N u m V e r t i c e s ) ) {  

r e m o v e _ c l i q u e ( G , C I i , V ) ;  

I S = l a r g e r _ o f ( C I i [ 1 ] , I S , G - > N u m V e r t i c e s ) ;  

C I i = R a m s e y _ V ( G , V ) ;  

p r i n t _ V ( I S , G - > N u m V e r t i c e s ) ;  

/ * B e g i n A P P R X * /  

v o i d g e r a S a i d a I n d e p ( F I L E * A r q A v a l )  

/ * P r o c e s s a o a r q u i v o A r q A v a l d e a l g u m a f o r m a * /  

T i p o G r a f o G ;  

i n t n , u , v , p ;  

f s c a n f ( A r q A v a l , " % d \ n " , & n ) ;  

G . N u m V e r t i c e s = n ;  

G . N u m A r e s t a s = 0 ;  

p = 1 ;  

F G V a z i o ( & G ) ;  

w h i l e ( ! f e o f ( A r q A v a l ) )  

f s c a n f ( A r q A v a l , " % d % d \ n " , & u , & v ) ;  

G . N u m A r e s t a s + + ;  

I n s e r e A r e s t a ( & u , & v , & p , & G ) ; / * 1 c h a m a d a g - d i r e c i o n a d o * /  

I n s e r e A r e s t a ( & v , & u , & p , & G ) ; / * 2 c h a m a d a s g - n a o d i r e c i o n a d o * /  

/ * G e r a a s a i d a * /  

C I n d e p F B ( & G ) ;  

2 3 

Page 26: distancia de edição

5/11/2018 distancia de edição - slidepdf.com

http://slidepdf.com/reader/full/distancia-de-edicao 26/26

 

f p r i n t f ( s t d o u t , " \ n " ) ;  

/ * C l i q u e R e d C I n d e p ( & G ) ;  

f p r i n t f ( s t d o u t , " \ n " ) ; * /  

/ * G r e d y I S ( & G ) ;  

f p r i n t f ( s t d o u t , " \ n " ) ;  

f p r i n t f ( s t d e r r , " \ n " ) ; * /  

/ * R a m s e y ( & G ) ;  

f p r i n t f ( s t d o u t , " \ n " ) ;  

f p r i n t f ( s t d e r r , " \ n " ) ; * /  

/ * C l i q u e R e m o v a l ( & G ) ;  

f p r i n t f ( s t d o u t , " \ n " ) ;  

f p r i n t f ( s t d e r r , " \ n " ) ; * /  

R e f e r ê n c i a s    

[ 1 ] R a v i B o p p a n a a n d M a g n ú s M . H a l l d ó r s o n . A p p r o x i m a t i n g m a x i m u m i n d e p e n d e n t s e t s  

b y e x p l u d i n g s u b g r a p h s .   S W A T 9 0 2 n d S c a n d i n a v i a n W o r k s h o p o n A l g o r i t h m T e o r y  , 

4 4 7 : 1 3 2 5 , 1 9 9 0 .  

[ 2 ] T h o m a s H . C o r m e n e t . a l .   A l g o r i t m o s : T e o r i a e P r á t i c a  . C a m p u s , R i o d e J a n e i r o , 2 n d  

e d i t i o n , 2 0 0 2 .  

[ 3 ] D a n G o s e l d .   A l g o r i t h m s o n s t r i n g s , t r e e s a n d s e q u e n c e s  . C a m b r i d g e U n i v e r c i t y P r e s s ,  

1 9 9 7 .  

[ 4 ] M a g n ú s M . H a l l d ó r s o n . A p p r o x i m a t i n g m a x i m u m i n d e p e n d e n t s e t s i n g r a p h s . I n  

S p r i n g e r - V e r l a g , e d i t o r ,   I n A P R O X ' 9 8 : P r o c c e d i n g s o f t h e I n t e r n a t i o n a l W o r k s h o p o n  

A p p r o x i m a t i n g A l g o r i t h m s f o r C o m b i n a t o r i a l O p t i m i z a t i o n   , p a g e s 1 1 3 , L o n d o n , U K ,  

1 9 9 8 .  

[ 5 ] N i v i o Z i v i a n i .   P r o j e t o d e A l g o r i t m o s c o m i m p l e m e n t a ç õ e s e m P a s c a l e C   . T h o m s o n ,  

S ã o P a u l o , 2 n d e d i t i o n , 2 0 0 4 .  

2 4