{"id":{"repo_id":"brazil-ufpe","oai_identifier":"oai:repositorio.ufpe.br:123456789/46303"},"canonical_url":"https://search.dev.ndltd.org/etd/brazil-ufpe/oai:repositorio.ufpe.br:123456789/46303","repository":{"repo_id":"brazil-ufpe","name":"Brazil UFPE","base_url":"https://repositorio.ufpe.br/oai/request"},"display":{"title":"Algoritmos para resolução do problema do corte máximo : abordagem exata e meta-heurísticas","abstract":"O problema do corte máximo é um dos problemas de natureza combinatória amplamente abordados na literatura. Neste problema dado um grafo não direcionado e ponderado G = (V, A), busca-se particionar o conjunto de vértices em dois subconjuntos, tal que a soma dos pesos das arestas que conectam os dois subconjuntos seja maximizada. Apesar da simplicidade da sua definição, o problema do corte máximo é NP-Completo, sendo classificado também como NP- Difícil, ou seja, uma classe de problemas para a qual, até o momento, não foi definido um método para encontrar uma solução ótima em tempo polinomial de maneira determinística. Para resolver esses problemas com alta complexidade são usadas, na maioria das vezes, abordagens meta-heurísticas. Desta forma, diferente dos algoritmos já propostos na literatura e visando explorar a possibilidade de uma nova abordagem exata, capaz de explorar o espaço de soluções e encontrar a solução ótima para o problema, este estudo propõe um algoritmo de árvore de busca e desenvolve cinco algoritmos meta-heurísticos para solução do problema do max-cut. Esta pesquisa foi dividida em quatro fases: (i) desenvolvimento e implementação da abordagem exata para a solução do problema; (ii) implementação de cinco meta-heurísticas; (iii) execução de experimentos computacionais com diferentes tipos de instâncias de grafos; (iv) realização de análises estatísticas. Os resultados mostraram que para a solução do max-cut o método exato proposto é eficaz e preferível em casos de pequeno porte, já os métodos meta-heurísticos existentes, em casos de grande porte, apresentam um melhor trade-off entre encontrar uma boa solução e o tempo necessário para tal, pois, nessa primeira versão do algoritmo Árvore de Busca Binária (ABB), a complexidade ainda é muito elevada para solucionar instâncias de grafos mais densos. A fim de resolver esse desafio da complexidade são necessárias explorações mais aprofundadas no algoritmo para encontrar um novo critério de contradição, para assim ser viável encontrar a solução ótima do problema em tempos aceitáveis para qualquer grafo.","abstract_html":"O problema do corte máximo é um dos problemas de natureza combinatória amplamente abordados na literatura. Neste problema dado um grafo não direcionado e ponderado G = (V, A), busca-se particionar o conjunto de vértices em dois subconjuntos, tal que a soma dos pesos das arestas que conectam os dois subconjuntos seja maximizada. Apesar da simplicidade da sua definição, o problema do corte máximo é NP-Completo, sendo classificado também como NP- Difícil, ou seja, uma classe de problemas para a qual, até o momento, não foi definido um método para encontrar uma solução ótima em tempo polinomial de maneira determinística. Para resolver esses problemas com alta complexidade são usadas, na maioria das vezes, abordagens meta-heurísticas. Desta forma, diferente dos algoritmos já propostos na literatura e visando explorar a possibilidade de uma nova abordagem exata, capaz de explorar o espaço de soluções e encontrar a solução ótima para o problema, este estudo propõe um algoritmo de árvore de busca e desenvolve cinco algoritmos meta-heurísticos para solução do problema do max-cut. Esta pesquisa foi dividida em quatro fases: (i) desenvolvimento e implementação da abordagem exata para a solução do problema; (ii) implementação de cinco meta-heurísticas; (iii) execução de experimentos computacionais com diferentes tipos de instâncias de grafos; (iv) realização de análises estatísticas. Os resultados mostraram que para a solução do max-cut o método exato proposto é eficaz e preferível em casos de pequeno porte, já os métodos meta-heurísticos existentes, em casos de grande porte, apresentam um melhor trade-off entre encontrar uma boa solução e o tempo necessário para tal, pois, nessa primeira versão do algoritmo Árvore de Busca Binária (ABB), a complexidade ainda é muito elevada para solucionar instâncias de grafos mais densos. A fim de resolver esse desafio da complexidade são necessárias explorações mais aprofundadas no algoritmo para encontrar um novo critério de contradição, para assim ser viável encontrar a solução ótima do problema em tempos aceitáveis para qualquer grafo.","abstract_has_math":false,"creators":["LIMA, Gabriel Lopes"],"institution":"Universidade Federal de Pernambuco","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["LINS, Isis Didier"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-03-03","date_published":"2022-03-03","updated_at":"2026-07-24T01:18:58Z","subjects":["Engenharia de Produção","Problema do Max-Cut","Abordagem exata","Árvore de busca binária","Meta-heurísticas"],"languages":["por"],"rights":["openAccess"],"rights_urls":["http://creativecommons.org/licenses/by-nc-nd/3.0/br/"],"identifier_entries":[]},"links":{"outbound_url":"https://repositorio.ufpe.br/handle/123456789/46303","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["LINS, Isis Didier"]},{"key":"dc:creator","label":"Author","values":["LIMA, Gabriel Lopes"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-09-09T12:41:35Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-09-09T12:41:35Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-03-03"]},{"key":"dc:publisher","label":"Institution","values":["Universidade Federal de Pernambuco"]},{"key":"dc:type","label":"Dc Type","values":["masterThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engenharia de Produção","Problema do Max-Cut","Abordagem exata","Árvore de busca binária","Meta-heurísticas"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["por"]},{"key":"dc:rights","label":"Dc Rights","values":["openAccess"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-nc-nd/3.0/br/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://repositorio.ufpe.br/handle/123456789/46303"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["O problema do corte máximo é um dos problemas de natureza combinatória amplamente abordados na literatura. Neste problema dado um grafo não direcionado e ponderado G = (V, A), busca-se particionar o conjunto de vértices em dois subconjuntos, tal que a soma dos pesos das arestas que conectam os dois subconjuntos seja maximizada. Apesar da simplicidade da sua definição, o problema do corte máximo é NP-Completo, sendo classificado também como NP- Difícil, ou seja, uma classe de problemas para a qual, até o momento, não foi definido um método para encontrar uma solução ótima em tempo polinomial de maneira determinística. Para resolver esses problemas com alta complexidade são usadas, na maioria das vezes, abordagens meta-heurísticas. Desta forma, diferente dos algoritmos já propostos na literatura e visando explorar a possibilidade de uma nova abordagem exata, capaz de explorar o espaço de soluções e encontrar a solução ótima para o problema, este estudo propõe um algoritmo de árvore de busca e desenvolve cinco algoritmos meta-heurísticos para solução do problema do max-cut. Esta pesquisa foi dividida em quatro fases: (i) desenvolvimento e implementação da abordagem exata para a solução do problema; (ii) implementação de cinco meta-heurísticas; (iii) execução de experimentos computacionais com diferentes tipos de instâncias de grafos; (iv) realização de análises estatísticas. Os resultados mostraram que para a solução do max-cut o método exato proposto é eficaz e preferível em casos de pequeno porte, já os métodos meta-heurísticos existentes, em casos de grande porte, apresentam um melhor trade-off entre encontrar uma boa solução e o tempo necessário para tal, pois, nessa primeira versão do algoritmo Árvore de Busca Binária (ABB), a complexidade ainda é muito elevada para solucionar instâncias de grafos mais densos. A fim de resolver esse desafio da complexidade são necessárias explorações mais aprofundadas no algoritmo para encontrar um novo critério de contradição, para assim ser viável encontrar a solução ótima do problema em tempos aceitáveis para qualquer grafo."]},{"key":"dc:title","label":"Title","values":["Algoritmos para resolução do problema do corte máximo : abordagem exata e meta-heurísticas"]}]}],"canonical_facts":{"dc:contributor.advisor":["LINS, Isis Didier"],"dc:creator":["LIMA, Gabriel Lopes"],"dc:date.accessioned":["2022-09-09T12:41:35Z"],"dc:date.available":["2022-09-09T12:41:35Z"],"dc:date.issued":["2022-03-03"],"dc:description.abstract":["O problema do corte máximo é um dos problemas de natureza combinatória amplamente abordados na literatura. Neste problema dado um grafo não direcionado e ponderado G = (V, A), busca-se particionar o conjunto de vértices em dois subconjuntos, tal que a soma dos pesos das arestas que conectam os dois subconjuntos seja maximizada. Apesar da simplicidade da sua definição, o problema do corte máximo é NP-Completo, sendo classificado também como NP- Difícil, ou seja, uma classe de problemas para a qual, até o momento, não foi definido um método para encontrar uma solução ótima em tempo polinomial de maneira determinística. Para resolver esses problemas com alta complexidade são usadas, na maioria das vezes, abordagens meta-heurísticas. Desta forma, diferente dos algoritmos já propostos na literatura e visando explorar a possibilidade de uma nova abordagem exata, capaz de explorar o espaço de soluções e encontrar a solução ótima para o problema, este estudo propõe um algoritmo de árvore de busca e desenvolve cinco algoritmos meta-heurísticos para solução do problema do max-cut. Esta pesquisa foi dividida em quatro fases: (i) desenvolvimento e implementação da abordagem exata para a solução do problema; (ii) implementação de cinco meta-heurísticas; (iii) execução de experimentos computacionais com diferentes tipos de instâncias de grafos; (iv) realização de análises estatísticas. Os resultados mostraram que para a solução do max-cut o método exato proposto é eficaz e preferível em casos de pequeno porte, já os métodos meta-heurísticos existentes, em casos de grande porte, apresentam um melhor trade-off entre encontrar uma boa solução e o tempo necessário para tal, pois, nessa primeira versão do algoritmo Árvore de Busca Binária (ABB), a complexidade ainda é muito elevada para solucionar instâncias de grafos mais densos. A fim de resolver esse desafio da complexidade são necessárias explorações mais aprofundadas no algoritmo para encontrar um novo critério de contradição, para assim ser viável encontrar a solução ótima do problema em tempos aceitáveis para qualquer grafo."],"dc:identifier.uri":["https://repositorio.ufpe.br/handle/123456789/46303"],"dc:language.iso":["por"],"dc:publisher":["Universidade Federal de Pernambuco"],"dc:rights":["openAccess"],"dc:rights.uri":["http://creativecommons.org/licenses/by-nc-nd/3.0/br/"],"dc:subject":["Engenharia de Produção","Problema do Max-Cut","Abordagem exata","Árvore de busca binária","Meta-heurísticas"],"dc:title":["Algoritmos para resolução do problema do corte máximo : abordagem exata e meta-heurísticas"],"dc:type":["masterThesis"]},"updated_at":"2026-07-24T01:18:58Z"}