Estou tentando implementar o algoritmo Subida de Encosta (Hill Climbing) e este algoritmo deve retornar a sequencia das cidades considerada boa (com a menor distancia entre as cidades) do problema do caixeiro viajante com base em uma matriz de adjacência, no entanto, estou tendo dificuldade na implementação dos métodos avaliar()
e sucessor()
, não sei qual abordagem eu deveria tomar para que esses métodos funcionem da forma esperada.
A implementação esta sendo em JavaScript:
let matrizAdjacente = [
[0, 1, 2, 3, 4, 5],
[2, 0, 5, 2, 1, 1],
[1, 8, 0, 2, 3, 4],
[2, 2, 1, 0, 6, 3],
[4, 2, 3, 1, 0, 4],
[3, 1, 3, 2, 2, 0]
];
let sequenciaCidades = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6];
let solucaoInicial = function() {
return [4, 5, 1, 6, 3, 2];
}
let avaliar = function(estado) {
}
let sucessor = function(atual, novo) {
}
let hillClimbing = function() {
let novo = null;
let atual = solucaoInicial();
let valorAvaliadoAtual = avaliar(atual);
let valorAvaliadoNovo = 0;
while (1) {
novo = sucessor(atual, novo);
valorAvaliadoNovo = avaliar(novo);
if (valorAvaliadoNovo < valorAvaliadoAtual) {
atual = novo;
valorAvaliadoAtual = valorAvaliadoAtual;
} else break;
}
return atual;
}
Este algoritmo consiste em examinar os sucessores do estado atual e seguir para o primeiro estado que for maior que o atual. Porém, é necessário implementar os métodos avaliar()
e sucessor()
, o método sucessor ira fazer uma troca entre os estados e o método avaliar vai retornar um valor dada uma sequencia.
Pergunta
Sendo assim, como eu poderia implementar o método avaliar()
e sucessor()
do algoritmo Subida de Encosta?
sequenciaCidades
? Cada cidade não teria o seu posicionamento x,y e distancia calculada através de distância euclidiana ou distância manhattan ?avaliar
é um dos argumentos da meta-heurística. Em cima disso, o hill climbing toma a decisão de continuar ou de voltar um passo e tentar de novo