Um Framework Computacional para o Jogo de Coloração Harmoniosa: Método Exato e Heurísticas Adversariais

O jogo de coloração harmoniosa (HCG) é um problema adversarial em grafos no qual dois agentes alternam a coloração de vértices sob restrições de distância-2 e de unicidade dos pares de cores nas arestas. Como as variantes do problema são PSPACE-completas, a determinação do número cromático harmonioso de jogo representa um desafio computacional. Neste trabalho, é proposto um arcabouço algorítmico para o HCG, o qual combina um método exato, baseado no algoritmo Minimax com poda Alpha-Beta, aplicado a instâncias de pequeno porte, e heurísticas adversariais para instâncias de maior escala, o que inclui estratégias baseadas no método DSATUR. Por meio de experimentos computacionais, foi indicada a influência da topologia e da estratégia adversarial sobre o número de cores requerido: os grafos split figuraram entre os casos desafiadores. As heurísticas apresentaram desvio absoluto médio inferior a uma cor em relação aos valores de referência, e o tempo computacional foi reduzido.