Uma nova técnica de resolução para o Problema da Régua de Golomb

Abstract

Uma Régua de Golomb difere de uma régua comum por cada par de marcas possuir uma distância única, ou seja, nenhum outro par de marcas deve obter a distância já encontrada anteriormente. Este trabalho apresenta uma nova abordagem para resolução do Problema da Régua de Golomb. O método proposto inicia-se com uma heurística construtiva para encontrar uma solução inicial para o problema. Em seguida, aplica-se uma heurística de melhoria baseada no Fix and Optimize. Os resultados desta abordagem são comparados com as respostas obtidas por meio da resolução do modelo matemático. Verificou-se que, para régua com até 35 marcas, o método proposto encontrou uma solução viável para o problema, enquanto a resolução do modelo matemático não obteve solução para os casos acima de 10 marcas.