аЯрЁБс>ўџ %'ўџџџ$џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№П?bjbjqPqP.::?џџџџџџЄ"ІІІІ В "э ЪЪЪЪЪЪЪЪlnnnnnn$љ ha 4’ЪЪЪЪЪ’ЪЪЇLLLЪ.ЪЪlLЪlLLLЪО z <‰ŠеІј"LlН0эL• • L• L LЪЪЪ’’6ЪЪЪэЪЪЪЪ"""„І"""І"""џџџџ Resumo: Dados um grafo nуo direcionado com pesos nas arestas e um conjunto de pares de arestas conflitantes, a Сrvore de Geradora Mэnima com Restriчѕes de Conflito (AGMRC) consiste em encontrar сrvore uma geradora com no mсximo uma aresta de cada par conflitante e custo mэnimo. O problema щ NP-difэcil e foi introduzido recentemente na literatura. Este trabalho propѕe uma nova abordagem para a soluчуo do AGMRC, o mщtodo щ baseado na meta-heurэstica GRASP com uso de uma memѓria adaptativa. A heurэstica proposta foi avaliada nas instтncias da literatura com milhares de conflitos. Os resultados indicam que o algoritmo proposto foi capaz de encontrar todas as soluчѕes ѓtimas conhecidas e superar as heurэsticas da literatura para o AGMRC. Palavras chaves: Сrvore Geradora Mэnima, Restriчѕes de Conflitos, GRASP. Abstract: Given an undirected graph with weights on the edges and a set of conflicting edge pairs, the Minimum Spanning Tree Under Conflict Constraints (MSTCC) consists in finding minimum spanning tree with at most one edge of each conflicting pair and minimum cost. The problem is N P-hard and was introduces recently at literature. This paper proposes a new approach for solving MSTCC, our method is based on the GRASP metaheuristic coupled with adaptive memory programming. We test the proposed heuristic on literature’s instances with thousands of conflicts. The results indicate that the proposed algorithm was able to find all known optimal solutions and outperform the best-known heuristics for the MSTCC. Keywords: Spanning Tree Problem, Conflict Constraints, GRASP.  & ( щ ъ љ 4 5 = ? A  ?ьлЪлЖлЂьлu`K`3u`.hуwhуw5CJOJQJ\^JaJmH sH (hуwhуwCJOJQJ^JaJmH sH (hуwhЗ?џCJOJQJ^JaJmH sH .hуwhЗ?џ5CJOJQJ\^JaJmH sH (hуw5CJOJQJ\^JaJmH sH &hуwhуw5CJOJQJ\^JaJ&hуwhЗ?џ6CJOJQJ]^JaJ hуwhуwCJOJQJ^JaJ hуwhЗ?џCJOJQJ^JaJ&hуwhЗ?џ5CJOJQJ\^JaJ  щ ъ 3 4 5 @ A ?їїїїїїїїїїїї$dha$ ?§,1hА‚. АЦA!Аn"Аn#n$n%ААаАа а†œf@ёџf Normal 1$*$A$3B*OJQJCJmHnHsHKHPJtH^JaJ_H9>A@ђџЁ> Fonte parсg. padrуoXi@ѓџГX  Tabela normal :V і4ж4ж laі ,k@єџС, Sem lista NўON Tэtulo1 Є№Єx$OJQJCJPJ^JaJFB@F Corpo de textodЄЄŒ*/@* Lista^JH"@"H Legenda ЄxЄx $CJ6^JaJ]0ўO20 Эndice $^J?џџџџ щъ345@AA˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€?? ? &05=мщA5?ДЙA35?AA5=AхуwЗ?џџ@€55”ZА55?@@џџUnknownџџџџџџџџџџџџG‡: џTimes New Roman5€Symbol3& ‡: џArialIџрџxP!ПLiberation SerifyNoto Sans CJK SC RegularTimes New RomanILohit DevanagariG& џрџxP!ПLiberation Sans"Aˆ Хh5-x'dУz‡љFƒ љF  24<< P №џџџџџџџџџџџџџџџџџџџџџуwВџџHelioўџр…ŸђљOhЋ‘+'Гй0d˜ЄАМШи шє   , 8DLT\фNormalHelio2Microsoft Office Word@@@‹щшKе@˜@‰ŠељFўџеЭеœ.“—+,љЎ0ш hp|„Œ” œЄЌД М Щф <ц  Tэtulo ўџџџ ўџџџўџџџ !"#ўџџџ§џџџ&ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РF§ <‰Šе(€1Tableџџџџџџџџ WordDocumentџџџџџџџџ.SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџCompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq