A GRASP Approach for The Minimum Spanning Tree Under Conflict Constraints - Barros, Bruno; Pinheiro, Rian; Ochi, Luiz; Ramos, Geymerson (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2019: Anais do XVI Encontro Nacional de Inteligência Artificial e ComputacionalDO - 10.5753/eniac.2019.9281, 2019)
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 geradora com no máximo uma aresta de cada par conflitante e custo mı́nimo. O problema é N P-difı́cil e foi introduzido recentemente na literatura. Este artigo 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.