аЯрЁБс>ўџ *,ўџџџ)џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№ПbjbjqPqP< :: џџџџџџЄРРРРРРРдXXXXt д=юŒŒŒŒŒŒ2ОкМОООООО$+ h“ hтРъŒŒъътРРŒŒїътРŒРŒМъМРРŒ€ єMeеXЬ"Ј 0=ћ юћ ћ Р”ъъъъъъътт  ъъъ=ъъъъддд„XдддXдддРРРРРРџџџџ Resumo: A сrvore geradora de custo mэnimo de um grafo G nуo direcionado, conexo e com custos nas arestas щ uma сrvore geradora onde o somatѓrio dos custos das arestas щ mэnimo. O diтmetro dessa сrvore щ definido como o nњmero mсximo de arestas dentre todos os caminhos da сrvore. O problema da сrvore geradora mэnima com diтmetro limitado (Bounded-Diameter Minimum Spanning Tree Problem – BDMSTP) consiste em encontrar uma сrvore geradora para G cujo diтmetro nуo exceda a um limite D, 2 ( D ( n – 1, onde n щ o nњmero de vщrtices de G, e que tenha custo mэnimo. Esse problema щ NP-difэcil para 4 ( D < n – 1. Aplicaчѕes da сrvore geradora de custo mэnimo com diтmetro limitado surgem em problemas de engenharia, como projetos de redes de telecomunicaчѕes e de fibra ѓtica, problemas de compressуo de dados e projeto de sistemas distribuэdos, quando considerada a exclusуo mњltipla. Mщtodos exatos para resolver o BDMSTP sѓ conseguem resolver pequenas instтncias do problema, com no mсximo 161 vщrtices e diтmetro menor ou igual a oito. Desse modo, heurэsticas construtivas e heurэsticas baseadas em metaheurэsticas tentam encontrar uma soluчуo prѓxima do ѓtimo para o problema em um tempo aceitсvel. Se os vщrtices do grafo de entrada estуo associados a pontos no plano Cartesiano, temos o Euclidean Bounded-Diameter Minimum Spanning Tree Problem – EBDMSTP. Esta tese apresenta e analisa as heurэsticas mais conhecidas na literatura para o EBDMSTP, propѕe uma nova heurэstica construtiva para o problema, e ainda outra heurэstica baseada no mщtodo Iterated Local Search (ILS), analisando os seus resultados com os existentes na literatura. Palavras-chave: Сrvore geradora, Сrvore geradora Euclidiana de custo mэnimo com diтmetro limitado, Iterated Local Search, ILS, Heurэsticas. Abstract: The minimum spanning tree of an undirected graph G is a spanning tree where the sum of the edge costs is minimum. The diameter of this tree is set as the maximum number of edges in a path of the tree. The Bounded-Diameter Minimum Spanning Tree Problem (BDMSTP) consists of finding a spanning tree for G whose diameter does not exceed a limit D, 2 ( D ( n - 1, where n is the number of vertices of G, and has minimum cost. This problem is NP-hard for 4 ( D < n – 1. Applications of the bounded-diameter minimum spanning tree arise in engineering problems, such as projects of telecommunication networks and optical fibers, data compression problems, and design of distributed systems, when considering multiple exclusion. Exact methods to solve the BDMST can only deal with small instances, up to 161 vertices and diameter less or equal to 8. Thus, constructive heuristics and heuristic-based metaheuristics try to find solutions close to the optimal in an acceptable time. If the vertices of the input graph are associated with points in the Cartesian plane, we have the Euclidean Bounded-Diameter Minimum Spanning Tree Problem (EBDMSTP). This thesis presents and analyzes the best known heuristics in the literature for the EBDMSTP, proposes a new constructive heuristic for the problem, and a new heuristic based on the Iterated Local Search (ILS) method, comparing the results with those existing in the literature. Keywords: Spanning trees, Euclidean bounded-diameter minimum spanning tree, Iterated Local Search, ILS, Heuristics.  78U ƒ † Œ Н О ф х щ ъ ы ь э ю я № ћ ќ §   V W X Y \ ьлЦИЇ“Ї“Ї~Ї“Ї“ЇjЇ“ЇjЇ“Ї“SЇ“ЇjЇ“Ї,hЂ'юhђT56CJOJQJ\]^JaJ& jЃ№hЂ'юhђTCJOJQJ^JaJ)hЂ'юhђTB*CJOJQJ^JaJph&hЂ'юhђT6CJOJQJ]^JaJ hЂ'юhђTCJOJQJ^JaJhЂ'юCJOJQJ^JaJ)hЂ'юhђT5;CJOJQJ\^JaJ hЂ'ю5CJOJQJ\^JaJ&hЂ'юhЂ'ю5CJOJQJ\^JaJ  jkјљ‘юццккЩИцццкЊ „dЄШ`„gdan$„dрЄh`„a$gdЂ'ю$„dрЄh`„a$gdan „dр`„gdandрgdan$„dЄШ`„a$gdЂ'ю §\ ] “ ™ D H O #kz{ŒЬіјљњьлЦльлЦльлДлЦлЦлЂŒt_F1hЂ'юhђT5;CJOJQJ\^JaJmH sH (hЂ'ю5CJOJQJ\^JaJmH sH .hЂ'юhЂ'ю5CJOJQJ\^JaJmH sH +hЂ'юhђT;CJOJQJ^JaJmH sH #hЂ'юhђT;CJOJQJ^JaJ#hЂ'юhђT5CJOJQJ^JaJ)hЂ'юhђTB*CJOJQJ^JaJph hЂ'юhђTCJOJQJ^JaJ&hЂ'юhђT6CJOJQJ]^JaJ67в23[\`abcdefgst’“ЩЪЫЬ4l‘š›ыгыгыгыгыПыгыПыгыгыгыПыгыгыЉыы1hЂ'юhђTB*CJOJQJ^JaJmH phsH +hЂ'юhђT5CJOJQJ^JaJmH sH & jЃ№hЂ'юhђTCJOJQJ^JaJ.hЂ'юhђT6CJOJQJ]^JaJmH sH (hЂ'юhђTCJOJQJ^JaJmH sH :&P 1hP:pA9А‚. АЦA!АЅ"Аn#Ѕ$n%ААХАХ Ф†œ 666666666666666666666666666666666666666666 6666666666 666666666666 666666666666666666666666666666666666666666666666666666666666666666\@ёџ\ 1ЦNormal$„Хdh`„Хa$ CJOJQJ_HaJmHsHtH >AђџЁ> 0Fonte parсg. padrуoTiѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista   џџџџ jkјљ ‘   ˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€\    џџ_GoBackTexto1Texto3 j‘  Uefmnvw{|ƒDNM\ &'./78<=D#Южну   nuТ д  33љ  хђTgz )9/A9†BђFF­I"hUИ/b[canrr№'uќ`yыvЂ Б~xГ“М1Ц#]Ш"nЪ„kе@оеcшЂ'ю:Eяњ$№y{№~cђМ%ј  џ@€  4Y>РР   @@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArial7&џрџЌ@ŸCalibri"Aˆ№ФЉє*rGj2v‡ў ў !№ЅЅДД24d №ќџ(№џ$Pџџџџџџџџџџџџџџџџџџџџџ1Ц2џџRESUMOGabriella NepomucenoHelioўџр…ŸђљOhЋ‘+'Гй0|˜ЈДдрьќ  8 D P\dltфRESUMOGabriella NepomucenoNormalHelio3Microsoft Office Word@FУ#@hYbНд@œэ;eеў ўџеЭеœ.“—+,љЎ0№ hp|„Œ” œЄЌД М Яф ц RESUMO Tэtulo ўџџџўџџџ ўџџџ"#$%&'(ўџџџ§џџџ+ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РFРјMeе-€1TableџџџџџџџџWordDocumentџџџџџџџџ< SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџ!CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq