Um Algoritmo Iterativo para a Solução do Problema da k-Partição de Números
Alexandre Frias Faria1; Sérgio Ricardo de Souza1; Carlos Alexandre Silva2; Moacir Felizardo de França Filho1
1 CEFET-MG; 2 IFMG
doi:10.20906/CPS/CILAMCE2015-0702
Resumo
Este artigo apresenta um algoritmo iterativo para a solução da versão de otimização do Problema da k-Partição de Números. Este problema consiste em distribuir os elementos de um conjunto dado em k subconjuntos disjuntos, de modo que as somas dos elementos de cada subconjunto fiquem no menor intervalo possível. O método consiste em aplicar a meta-heurística ILS (Iterated Local Search) na solução gerada por um algoritmo aproximado. A estratégia é aplicar método guloso em todas as fases do algoritmo, tanto na inicialização quanto na escolha de movimentos do ILS. Usando um algoritmo heurístico para o Problema da Partição de Números em 2 subconjuntos, pode-se construir um algoritmo polinomial iterativo para o Problema da Partição de Números em k subconjuntos. Realiza-se um estudo comparativo com outros dois algoritmos da literatura usando a análise de complexidade dos mesmos e instâncias geradas aleatoriamente. Mostra-se que o desempenho do algoritmo melhora quando a solução inicial é mais próxima do ótimo.
Palavras-chave: Problema da Partição de Números; Iterated Local Search; Metaheurísticas