ࡱ> .0-5bjbjUU >??5`` 8'))))))^L))>''IICT0,))` i:Resumo: O conceito de similaridade entre objetos fundamental na rea de reconhecimento de padres. Na chamada "abordagem estrutural", grafos so frequentemente utilizados para representar objetos. Assim sendo, preciso definir um meio de medir a similaridade entre dois grafos. Uma das ferramentas mais utilizadas para realizar essa medio a distncia de edio, que consiste em medir a distncia entre dois grafos de acordo com o grau de distoro necessrio para transformar um grafo no outro. O grafo mediano generalizado de um conjunto de grafos S aquele que minimiza a soma das distncias dos grafos de S a ele e que melhor captura as informaes desse conjunto de grafos, podendo ser considerado um representante deste conjunto. O conceito de grafo mediano j foi aplicado com sucesso em reas como reconhecimento de smbolos grficos, identificao biomtrica e clusterizao de imagens, entre outros. No entanto, computar o grafo mediano generalizado de um conjunto de grafos uma tarefa complexa. Por si s, a verso de deciso do problema de clculo da distncia de edio entre dois grafos NP-Completo. Algoritmos exatos lidam apenas com grafos de tamanho relativamente pequeno, sendo de pouca utilidade prtica. Nesta tese so propostos trs algoritmos aproximados para o problema, um deles baseado em uma estratgia gulosa e os outros dois baseados nas meta-heursticas GRASP e BRKGA, alm de dois novos resultados tericos, um deles servindo de base para uma variao do algoritmo BRKGA. Os resultados obtidos indicam que os algoritmos podem ser utilizados para encontrar solues aproximadas de boa qualidade em tempos computacionais razoveis. Palavras-chave: Reconhecimento de padres, correspondncia entre grafos, distncia de edio, algoritmos gulosos, GRASP, BRKGA, grafo mediano. Abstract: Structural approaches for pattern recognition frequently make use of graphs to represent objects. The concept of object similarity is of great importance in pattern recognition. Therefore, it is necessary to define a way to measure the similarity between two graphs. One of the most used tools to perform this similarity comparison is the graph edit distance, which consists of measuring the distance between two graphs by the amount of distortion necessary to transform one graph into the other. The generalized median graph of a set S of graphs is the graph that minimizes the sum of the distances to the graphs in S and it is the graph that best captures the information contained in S, and may be regarded as a representative of this set. The median graph concept has been succesfully applied in areas such as graphic symbol recognition, biometric identification and image clustering, among others. However, computing the generalized median graph of a set of graphs is a complex task. By itself, the decision version of the problem of computing the graph edit distance between two graphs is NP-Complete. Exact algorithms deal only with graphs of relatively small size, which makes them of not much use in practical situations. In this thesis three approximate algorithms for the generalized median graph problem are proposed, one of them based on a greedy strategy and the other two based on the GRASP and BRKGA metaheuristics. Also, two new theoretical results are presented, one of them serving as the basis for a variant of the BRKGA heuristic. The results obtained indicate that the algorithms can be used to find approximate solutions of good quality in reasonable computational times. Keywords: Pattern recognition, graph matching, edit distance, greedy algorithms, GRASP, BRKGA, median graph.  #%3ϾϾxcxcJ.x7heh7m5B*CJOJQJ\^JaJmH phsH 1h7m5B*CJOJQJ\^JaJmH phsH (heh7mCJOJQJ^JaJmH sH 1heh7mB*CJOJQJ^JaJmH phsH /heh7m5B*CJOJQJ\^JaJph)heh7mB*CJOJQJ^JaJph heh7mCJOJQJ^JaJ,h7m5>*B*CJOJQJ\^JaJph2heh7m5>*B*CJOJQJ\^JaJph $%45$a$gdegde 35heh7mmH sH <P1h:p7m. A!"#$% Dp^ 666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtH@`@ NormalCJ_HaJmHsHtHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List e@ e0HTML Preformatted7 2( Px 4 #\'*.25@9CJOJQJ^JaJX/X  0HTML Preformatted CharCJOJQJ^JaJPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] 535 5 erL>7m57@5@@UnknownG*Ax Times New Roman5Symbol3" Arial?= *Cx Courier NewACambria Math"i'i'8 !0$P5e!xxResumo:HelioHelioOh+'0x  4 @ LX`hpResumo:HelioNormal_WordconvHelio1Microsoft Office Outlook@G@ C@aǐC8 ՜.+,0 hp|   Resumo: Title  !"#$&'()*+,/Root Entry FRC11TableWordDocument>SummaryInformation(DocumentSummaryInformation8%CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q