Question:

I am trying to implement the Hill Climbing algorithm and this algorithm should return the sequence of cities considered good (with the shortest distance between cities) of the traveling salesman problem based on an adjacency matrix, however, I am having difficulty implementing the avaliar() and sucessor() methods, I don't know what approach I should take to make these methods work as expected.

The implementation is in 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;
}

This algorithm consists of examining the successors of the current state and going to the first state that is greater than the current one. However, it is necessary to implement the avaliar() and sucessor() methods, the successor method will make a switch between states and the evaluate method will return a value given a sequence.

Question

So, how could I implement the avaliar() and sucessor() method of the Hill Climb algorithm?

Answer:

If I understand correctly, the sucessor() method gives you a list of cities to be evaluated by the avaliar() method, which should return the cost of your solution, that is, the distance that would be covered if we visited the cities in a certain order and if that distance is better than what we currently have, we'll use this new sequence as our optimal solution, so all that avaliar() evaluate needs to do is traverse the list by summing the distances from the distance matrix D (or adjacency, as prefer) being that

D[x][y] = distância entre x e y 

Suppose you have the sequence [2,1,3] , your total distance is therefore D[2][1]+D[1][3] i.e. the cost of going from city 2 to city 1 and after city 1 through city 3, this logic can be implemented with a for loop on top of the list of cities returned by sucessor() .

The job of the sucessor() method is to use a previous list of cities to generate a new candidate solution, this can be done in several ways, depending on the specification of the problem, as it is the PCV, the simplest suggestion is to add the first unvisited city you find at the end of the list since it can be reached from the last city, suppose you have 6 cities (1 to 6) and your list looks something like this: [4,2,3] , the next city unvisited is city 1, if in your matrix D[3][1] > 0 (that is, there is a path from 3 to 1) your new list would be [4,2,3,1] , if there is none city ​​without visiting, you check if you can go back to the first city (problem constraint).