Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Menor caminho utilizando algoritmo

0 votos
12 visitas
perguntada Nov 8 em Ciência da Computação por Renan Abrantes (16 pontos)  
editado Nov 8 por Renan Abrantes

Utilizando o pseudocódigo abaixo resolva o problema do caixeiro viajante, em python, de acordo com a matriz de custos citada, sendo (x,y) o custo de ir de x para y e os vértices visitados dado pelo conjunto V = {0,1,2,3,4,5,6,7,8,9}.

Pseudocódigo:
A imagem será apresentada aqui.

Sendo a função B responsável pelo cálculo do custo dos caminhos parciais.

Matrix de custos:

A imagem será apresentada aqui.

  • Exercício 4.7 do Livro Combinatorial Algorithms: Generation, Enumeration, and Search (Capítulo: Backtracking Algorithms)
Compartilhe

1 Resposta

0 votos
respondida Nov 8 por Renan Abrantes (16 pontos)  
editado Nov 8 por Renan Abrantes

O problema do caixeiro viajante consiste em encontrar o menor caminho, isto é, com menor custo para percorrer todos os vértices possíveis e retornar para a origem. Para a solução foi utilizado como referência o livro da questão problema: Combinatorial Algorithms: Generation, Enumeration, and Search

Para iniciar o algoritmo, primeiramente vamos iniciar as variáveis a serem utilizada:

inf = float('inf') # Infinito
V = [0,1,2,3,4,5,6,7,8,9] # Vertices

Custo =[[inf,22,0,72,56,17,57,13,38,63], # Matriz de custo informada pela questão
    [22,inf,95,29,84,75,39,19,26,12],
    [0,95,inf,87,78,70,39,99,21,12],
    [72,29,87,inf,95,90,82,33,60,76],
    [56,84,78,95,inf,39,93,35,2,59],
    [17,75,70,90,39,inf,36,81,98,25],
    [57,39,39,82,93,36,inf,28,47,88],
    [13,19,99,33,35,81,28,inf,78,13],
    [38,26,21,60,2,98,47,78,inf,72],
    [63,12,12,76,59,25,88,13,72,inf]]

def gerar_matriz (n_linhas, n_colunas):               # Gera uma matriz nula
    return [[0]*n_colunas for _ in range(n_linhas)]

n = 10 # Número de linhas e colunas
B = 0 # Custo parcial
C = gerar_matriz(n,n) # Matrix de caminho
C[0] = V.copy() # Caminho inicial com todos os vertices
X = [0,0,0,0,0,0,0,0,0,0] # Variável de caminho
M = gerar_matriz(n,n) # Matriz de custo parcial

optC = inf # Melhor custo
optX = [] # Melhor caminho

O valor infinito na matrix foi atribuído ao custo de sair e ir para mesma cidade, este valor alto foi definido para que o algoritmo desconsidere esse caminho.
A variável de caminho "C" foi utilizada para que armazene os vértices passados a cada iteração do algoritmo que veremos a seguir.

Implementação do pseudocódigo, algoritmo 4.13 descrito no livro de referência, na linguagem Python:

def TSP2(l):
    global optC
    global X
    global C
    global n
    global optX

    if (l == n): # Fim de um bloco de iteracao
        CurCost = cost(X) # Calculo do custo do caminho
        if (CurCost < optC): # Se for melhor que o definido
            optC=CurCost # Custo
            optX = X.copy() # Caminho
        return 
    else:
        if(l == 1):
            C[l] = V[1:] # Caminho parcial inicial
        else:
            C[l] = C[l-1].copy() 
            C[l].remove(X[l-1]) # Remove o vertice ja percorrido

        B = ReduceBound(l) # Calcula o custo parcial

        for x in C[l]:
            if(B >= optC): return # Encerra o caminho se o custo do caminho parcial ja exceder o menor custo definido
            X[l]=x
            TSP2(l+1) # Iteracao

Este algoritmo recebe como entrada 'l' o número de vértices visitado até o momento, desta forma assim que o número de vértices visitados for igual ao total do número de vértices encontramos o custo desta rota, e este valor só é tido como útil se for menor que o menor custo de uma rota já percorrida. Enquanto não for percorrido rota alguma, o menor custo é tido como infinito.

Como medida de otimização, caso o custo parcial da rota percorrida já seja maior que o menor custo, da rota completa, o algoritmo não prossegue até completar a rota e é passado para o próximo vértice.

Vale ressaltar que o algoritmo sempre parte do vértice 0 e prossegue por meio de iteração para os próximos vértices.

Para o cálculo da rota parcial foi utilizada a função ReduceBound, esta realiza a soma dos custos do caminho parcial X e da matriz dos custos parciais M. Sua implementação, algoritmo 4.12 descrito no livro de referência, foi realizada da seguinte forma:

def ReduceBound(m): # Algoritmo 4.12
    global M
    global X
    global n
    _M = [] # Caminho a ser explorado
    for i in range(m):
        _M.append(X[i])
    out = 0
    if (m==n): # Quando não há mais caminho para explorar
        return cost(X)
    #Inicio da construção da matriz parcial do caminho não explorado da coluna 0 e linha 0
    M[0][0] = inf
    j = 1
    for y in range(n):
        if y not in _M: 
            M[0][j] = Custo[X[m-1]][y]
            j += 1
    i = 1
    for x in range(n):
        if x not in _M:
            M[i][0] = Custo[x][X[0]]
            i += 1
    # Construcao do restante do caminho não explorado
    i = 1
    for x in range(n):
        if x not in _M:
            j = 1
            for y in range(n):
                if y not in _M:
                     M[i][j] = Custo[x][y]   
                     j += 1
            i += 1
    out = Reduce(n-m+1) # Calcula a soma dos custos mínimos da matriz parcial
    #Realiza a soma dos custos do caminho parcial X e do retorno de Reduce
    for i in range (1,m):
        out += Custo[X[i-1]][X[i]]
    return out

A função acima tem o objetivo de partir da matriz de custos e ir atualizando os custos dos caminhos na matriz auxiliar M. No caso do caminho já ter percorrido todos os vértices é chamada a função cost que é responsável pelo cálculo do custo deste caminho. Esta função tem a implementação da seguinte forma:

def cost(X): # Calcula o circuito Hamiltoniano do caminho parcial X
    x = 0
    for i in range(1,len(X)):
        x += Custo[X[i-1]][X[i]]
    x += Custo[X[n-1]][X[0]] # Fecha o circuito
    return x

Já no caso de ainda existir vértices a serem visitados, é utilizada a matriz de custo parcial M como base para o cálculo realizado pela função Reduce, esta função tem por objetivo transformar a matriz M em uma matriz reduzida. (Matriz reduzida é aquela na qual todos elementos são positivos e toda linha e toda coluna possui ao menos uma elemento igual a zero )

Implementação da função Reduce, algoritmo 4.11 descrito no livro de referência:

def Reduce(m): # Algoritmo 4.11 
    global M
    valor = 0
    for i in range(m):
        min = M[i][0]
        for j in range(1,m):
            if(M[i][j] < min):
                min = M[i][j]
        for j in range(m):
            M[i][j] -= min
        valor += min
    for j in range(m):
        min = M[0][j]
        for i in range(1,m):
            if(M[i][j] < min):
                min = M[i][j]
        for i in range(m):
            M[i][j] -= min
        valor += min # Soma dos custos minimos das linhas e colunas
    return valor

A vizualização do menor caminho e menor custo pode ser observado da seguinte forma:

TSP2(1)

print("Menor custo: " + str(optC)) 
print("Caminho: " + str(optX[0]) + " --> " + str(optX[1]) + " --> " + str(optX[2]) + " --> " + 
str(optX[3])
 + " --> " + str(optX[4]) + " --> " + str(optX[5]) + " --> " + str(optX[6]) + " --> " + str(optX[7])
 + " --> " + str(optX[8]) + " --> " + str(optX[9]))

O resultado obtido para esta matriz de custo foi:

Menor custo: 219
Caminho: 0 --> 2 --> 9 --> 1 --> 3 --> 7 --> 6 --> 8 --> 4 --> 5

...