How to implement the "evaluate ()" and "successor ()" method of the Hill Rise algorithm?

Question

How to implement the "evaluate ()" and "successor ()" method of the Hill Rise algorithm?

Navigation

#1 by (3 votes)

8

I'm trying to implement the Hill Climbing algorithm and this algorithm should return the sequence of cities considered good (with the smallest distance between cities) from the traveling salesman problem based on an adjacency array, however, I'm having difficulty implementing the avaliar() and sucessor() methods, I do not 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 moving to the first state that is larger 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 given value a sequence.

Question

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

javascript algoritmo

asked by anonymous 17.04.2018 / 01:16

1 answer

Error compiling Angular project 5 "is missing from the TypeScript compilation." VBA - SQL - Filter with SELECT

score 3 · Answer 1

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 traveled if we visited cities in a certain order, and if that distance is better than the one we have now, we will use this new sequence as our optimal solution, so all that% compile% needs to do is go through the list by distancing the distances D adjacency, as you prefer) where

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

Suppose you have the string avaliar() , its total distance is therefore [2,1,3] , ie the cost of going from city 2 to city 1 and then city 1 to city 3, this logic can be implemented with a for loop over the list of cities returned by D[2][1]+D[1][3] .

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