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

Como usar a técnica de Branch & Bound para resolver o problema do Caixeiro Viajante?

+1 voto
996 visitas
perguntada Mai 27, 2016 em Ciência da Computação por PRosa (61 pontos)  
editado Mai 29, 2016 por PRosa

O custo computacional para resolver o problema do caixeiro viajante pode ser bastante elevado para soluções por força bruta, em que são analisadas (n-1)! permutações de caminhos possíveis. Por exemplo, para n=11 cidades, são analisadas 3.628.800 combinações.

O uso de algoritmos Branch & Bound otimiza a seleção do melhor caminho, eliminando subsets de soluções não interessantes.

Compartilhe

2 Respostas

+1 voto
respondida Mai 27, 2016 por PRosa (61 pontos)  
editado Mai 29, 2016 por PRosa

O algoritmo Branch & Bound abaixo, conforme a vídeo-aula do Indian Institute of Technology, utiliza a redução da matriz de custos (distâncias) para a seleção de nós para realizar os sucessivos branchs.

Em resumo, o procedimento trata de, a partir de um dado nó, gerar os nós do nível seguinte, calculando os respectivos custos mínimos e, ao alcançar uma solução temporária (circuito completo), eliminar os nós já gerados cujo custo seja superior ao custo da solução temporária.

Os detalhes estão comentados no código abaixo, pré-configurado para resolver o caminho para 11 cidades do circuito. A execução é rápida:

import numpy as np
import Queue
global matCustos

# Os objetos Ponto (melhor seria Nó, mas não é permitido acento na sintaxe)
# armazenam os dados de cada nó da árvore: cidades já percorridas, nível do nó,
# e o custo mínimo a partir desse nó (isso servirá para o Bound).
class Ponto:
    def __init__(self,nivel,cidadeOrigem,cidadeAtual,cidadesVisitadas):
        self.nivel     = nivel
        self.origem    = cidadeOrigem
        self.atual     = cidadeAtual
        cidadesVisitadas.append(cidadeAtual)        
        self.cidadesVisitadas = cidadesVisitadas
        self.explorar  = True      
        if nivel > 0:  
           self.custo  = calculaCusto(self)  # calcula a distância
        else:
           self.custo  = np.Inf              # ponto inicial do circuito

# Esta função calcula a distância mínima a ser percorrida nesse ramo da árvore
def calculaCusto(ponto):
    global matCustos
    copiaMatCustos = []
    visitadas = ponto.cidadesVisitadas
    vlrXij = 0
    #copiaMatCustos = matCustos[:]  não funcionou, copiou por referência
    copiaMatCustos = [row[:] for row in matCustos] # assim ok
    n = len(copiaMatCustos)

    # Faz a redução da ordem da matriz: atribui zero para as linhas e colunas
    # das cidades já percorridas no ramo (vetor visitadas), para onde não voltará
    for i in range(len(visitadas)-1):
        # Guarda o custo referente ao deslocamento Xij (realizado)
        vlrXij += matCustos[visitadas[i]][visitadas[i+1]]
        # zera linha da cidade 'i' e coluna da cidade 'i+1' da matriz
        for aux in range(1,n):
            copiaMatCustos[visitadas[i]][aux] = 0
            copiaMatCustos[aux][visitadas[i+1]] = 0

    # zera também o elemento Xij que fecharia um subTour, impedindo, assim,
    # de se voltar para o ponto inicial antes de passar por todas as cidades
    if ponto.nivel < n-2:    
       copiaMatCustos[ponto.atual][visitadas[0]] = 0
    # acha o menor custo por cidades a visitar futuramente
    custoTotal = 0    
    for i in range(1,n):
        menor = copiaMatCustos[i][1]
        for j in range(2,n):
            # como a cópia da matriz de custos contém muitos zeros (procedimento acima),
            # trata isso aqui
            if (copiaMatCustos[i][j] < menor and copiaMatCustos[i][j] > 0) or (menor == 0):
               menor = copiaMatCustos[i][j]
        custoTotal += menor       

    return vlrXij + custoTotal   # custo percorrido (vlrXij) + a percorrer (CustoTotal)

# Função para realizar o Branch em cada nó selecionado para exploração
def criaPontosFilhos(ponto,nNiveis):
    visitadas = ponto.cidadesVisitadas
    filhos=[]    
    if ponto.nivel==nTotCidades-1:  # fecha o tour, voltando para 1a. cidade ...
       filhos.append(Ponto(ponto.nivel+1,ponto.atual,visitadas[0],visitadas[:]))
    else:       # ... ou gera todos os nós possíveis (continuação do ramo)
        for i in range(1,nNiveis+1):    
           if naoVisitado(i,visitadas):
               novoPonto = Ponto(ponto.nivel+1,ponto.atual,i,visitadas[:])           
               filhos.append(novoPonto)
    return filhos

# Função para verificar se uma cidade já foi visitada no ramo
def naoVisitado(cidade, cidadesVisitadas):
    for visitou in cidadesVisitadas:
        if visitou == cidade:
            return False
    return True

# Função para guardar a melhor solução encontrada até o momento
def guardaMelhorSolucao(f,solucao):
    if f.custo < solucao.custo :
       print "Melhor temporária:", f.cidadesVisitadas, " distância:", f.custo
       solucao = f

    return solucao

# Gera a matriz utilizada como exemplo em https://www.youtube.com/watch?v=-cLsEHP0qt0 
def matrizVideoAula():
    global matCustos
    # Não usa a linha 0 e a coluna 0 da matriz, para deixar os índices iguais aos números das cidades (1 a 5)
    matCustos = [ [None,None,None,None,None,None], 
                  [None,   0,  10,   8,   9,   7],
                  [None,  10,   0,  10,   5,   6],
                  [None,   8,  10,   0,   8,   9],
                  [None,   9,   5,   8,   0,   6],
                  [None,   7,   6,   9,   6,   0] ]
    return

# Gera uma matriz aleatória de ordem "n"
def matrizAleatoria(n):
    global matCustos
    matCustos = [ [None]*n for i in range(n) ]
    for i in range(1,n):
        matCustos[i][i]=0
        for j in range(i+1,n):
            matCustos[i][j]=matCustos[j][i]=int(np.random.uniform()*100)
    return

if __name__ == '__main__':
    global matCustos

#    np.random.seed(0)

    # Gerar matriz de custos aleatória ...
    matrizAleatoria(11)   
    # ... ou carregar a matriz de custos da video-aula
    #matrizVideoAula()    

    nTotCidades  = len(matCustos[0])-1

    # Usa a fila prioritária para auomaticamente explorar primeiro os nós 
    # com potencial para baixo custo em seu ramo
    listaNos   = Queue.PriorityQueue() 

    pontoInicio = Ponto(0,0,1,[])    # Inicia pela cidade 1 
    listaNos.put((0,pontoInicio))    # inicializa a fila

    solucaoCandidata = pontoInicio
    lAchouSolucao = False
    nTotalDeNosAvaliados=0            # contador de nós gerados na solução
    while (not lAchouSolucao):
        # Pega próximo nó para o BRANCH, na fila prioritária (menor custo)
        ponto=listaNos.get()[1]       # elemento 1 contém o objeto ponto

        # Faz o branch do nó, gerando todos os nós do nível abaixo dele
        filhos = criaPontosFilhos(ponto,nTotCidades)
        for f in filhos:
            nTotalDeNosAvaliados += 1
            if f.custo < solucaoCandidata.custo:  # nó com custo viável?
                # prioriza os nós de ramos mais adiantados para a busca
                prioridade = 1/float(f.nivel) + f.custo/1000000.0   
                listaNos.put((prioridade,f))  # coloca o novo nó na fila

                if f.nivel == nTotCidades:   # chegou em solução alternativa?
                    solucaoCandidata = guardaMelhorSolucao(f,solucaoCandidata)                    

                    # Faz o BOUND, eliminando os nós cujo caminho tenha custo maior que a solução temporária
                    listaAux = []   # como vai tirar todos os nós da fila prioritária
                                    # para fazer a "poda" ,
                                    # usa um vetor auxiliar para depois reconstruir
                                    # a fila prioritária            
                    while not listaNos.empty():
                        pontoCandidato=listaNos.get()[1]
                        # Voltam para a fila somente os nós 
                        # cujo custo potencial não supere o custo da solução temporária
                        if  pontoCandidato.custo < solucaoCandidata.custo:
                           listaAux.append(pontoCandidato)

                    # Recarrega a fila prioritária, após o filto acima
                    for ponto in listaAux:
                       prioridade = 1/float(ponto.nivel) + ponto.custo/10000.0
                       listaNos.put((prioridade,ponto))

        if listaNos.empty():  # Tour concluído!
            lAchouSolucao = True

    # Fim:
    print "Total de Nós Avaliados na Árvore:", nTotalDeNosAvaliados                
    print "Melhor caminho para o Caixeiro  :", solucaoCandidata.cidadesVisitadas
    print "Distância percorrida:", solucaoCandidata.custo
comentou Mai 28, 2016 por danielcajueiro (5,661 pontos)  
Paulo, talvez vc possa documentar um pouco mais sobre a especificidade da solução. Embora esteja no link que você mencionou, não sabemos sobre a estabilidade do link até mesmo em curto prazo.
comentou Mai 28, 2016 por PRosa (61 pontos)  
editado Mai 29, 2016 por PRosa
Olá Prof. Cajueiro, fiz uma correção no algoritmo postado anteriormente, que estava eliminando os nós prematuramente, antes de obter um parâmetro seguro, isto é, o custo de uma solução candidata, com caminho completo.
+1 voto
respondida Jun 5, 2016 por PRosa (61 pontos)  

Da mesma forma que ocorre com o algoritmo por força-bruta, o tempo de execução aumenta consideravelmente com o aumento do número de cidades no circuito do caixeiro.

O código abaixo combina a técnica do Branch & Bound com a abordagem de Divide & Conquer, utilizando múltiplos nós de processamento na rede.

Para os testes, foram utilizados um computador com processador de 1,5 GHz (A) e outro com 1,90 GHz (B). No computador B foram ativadas até 3 sessões do componente "servidor" da solução, alcançando os seguintes resultados:

A imagem será apresentada aqui.

Para reduzir o espaço de busca, os nós processadores cooperam uns com os outros informando sobre os menores custos encontrados.

CaixeiroBBLocalv2_var.py: (protocolo)

import numpy as np

menorCustoRemoto=np.Inf

MSG_REQUISICAO_CAMINHO = 1
MSG_RESPOSTA_CAMINHO   = 2
MSG_INFORMACAO         = 3

CaixeiroBBLocalv2.py: (Cliente)

import numpy as np
import Queue
import time
import threading
import socket, pickle
import CaixeiroBB_Local_v2_var as comunic

global matCustos

# Os objetos Ponto (Nó)
# armazenam os dados de cada nó da árvore: cidades já percorridas, nível do nó,
# e o custo mínimo a partir desse nó (isso servirá para o Bound).
class Ponto:
    def __init__(self,nivel,cidadeOrigem,cidadeAtual,cidadesVisitadas):
        self.nivel     = nivel
        self.origem    = cidadeOrigem
        self.atual     = cidadeAtual
        cidadesVisitadas.append(cidadeAtual)        
        self.cidadesVisitadas = cidadesVisitadas
        self.explorar  = True      
        if nivel > 0:  
           self.custo  = calculaCusto(self)  # calcula a distância
        else:
           self.custo  = np.Inf              # ponto inicial do circuito

# Esta função calcula a distância mínima a ser percorrida nesse ramo da árvore
def calculaCusto(ponto):
    global matCustos
    copiaMatCustos = []
    visitadas = ponto.cidadesVisitadas
    vlrXij = 0
    #copiaMatCustos = matCustos[:]  não funcionou, copiou por referência
    copiaMatCustos = [row[:] for row in matCustos] # assim ok
    n = len(copiaMatCustos)

    # Faz a redução da ordem da matriz: atribui zero para as linhas e colunas
    # das cidades já percorridas no ramo (vetor visitadas), para onde não voltará
    for i in range(len(visitadas)-1):
        # Guarda o custo referente ao deslocamento Xij (realizado)
        vlrXij += matCustos[visitadas[i]][visitadas[i+1]]
        # zera linha da cidade 'i' 
        copiaMatCustos[visitadas[i]][0] = np.Inf
        # zera colunas da cidade 'i+1' da matriz
        for aux in range(1,n):
            copiaMatCustos[aux][visitadas[i+1]] = np.Inf

    # zera também o elemento Xij que fecharia um subTour, impedindo, assim,
    # de se voltar para o ponto inicial antes de passar por todas as cidades
    if ponto.nivel < n-2:    
       copiaMatCustos[ponto.atual][visitadas[0]] = np.Inf
    # acha o menor custo por cidades a visitar futuramente
    custoTotal = 0    
    for i in range(1,n):
        if copiaMatCustos[i][0] != np.Inf:
            menor = copiaMatCustos[i][2]
            for j in range(2,n):
                if (copiaMatCustos[i][j] < menor): 
                   menor = copiaMatCustos[i][j]
            if menor != np.Inf:
              custoTotal += menor       

    return vlrXij + custoTotal   # custo percorrido (vlrXij) + a percorrer (CustoTotal)

# Função para realizar o Branch em cada nó selecionado para exploração
def criaPontosFilhos(ponto,nNiveis):
    visitadas = ponto.cidadesVisitadas
    filhos=[]    
    if ponto.nivel==nNiveis-1:  # fecha o tour, voltando para 1a. cidade ...
       filhos.append(Ponto(ponto.nivel+1,ponto.atual,visitadas[0],visitadas[:]))
    else:       # ... ou gera todos os nós possíveis (continuação do ramo)
        for i in range(1,nNiveis+1):    
           if naoVisitado(i,visitadas):
               novoPonto = Ponto(ponto.nivel+1,ponto.atual,i,visitadas[:])           
               filhos.append(novoPonto)
    return filhos

# Função para verificar se uma cidade já foi visitada no ramo
def naoVisitado(cidade, cidadesVisitadas):
    for visitou in cidadesVisitadas:
        if visitou == cidade:
            return False
    return True

# Função para guardar a melhor solução encontrada até o momento
def guardaMelhorSolucao(f,solucao):
    if f.custo < solucao.custo :
#       print "Melhor temporaria:", f.cidadesVisitadas
       print "Distancia:", f.custo
       solucao = f

    return solucao

# Gera uma matriz aleatória de ordem "n"
def matrizAleatoria(n):
    global matCustos
    n += 1 # uma coluna será None

    # Gera uma matriz 50x50 para servir de base para qualquer outra de ordem n
    # para não variar as distâncias conforme aumente n
    mat50x50  = [ [None]*50 for i in range(50) ]
    for i in range(50):
        for j in range(50):
           mat50x50[i][j] = int(np.random.uniform()*100)

    matCustos = [ [None]*n for i in range(n) ]
    for i in range(1,n):
        matCustos[i][i]=np.Inf
        for j in range(i+1,n):
            matCustos[i][j]=matCustos[j][i]=mat50x50[i][j]
    return

# Exibe na tela as informações recebidas dos servidores
def informaResultadoThread(retorno, numThread):

    print "recebi:", retorno[1], " custo:", retorno[2] , " Thread:", numThread

# Gera as threads para cada servidor disponível
class inicializaServidor(threading.Thread):

     def __init__(self, numThread, vetServidores, vetPontos, matCustos):
        threading.Thread.__init__(self)
        self.numThread=numThread      
        self.vetServidores=vetServidores
        self.IP       =vetServidores[numThread][0]
        self.porta    =vetServidores[numThread][3]
        self.vetPontos=vetPontos        
        self.matCustos=matCustos

     def run(self):

        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect((self.IP, self.porta))
        dados_enviar=pickle.dumps([comunic.MSG_REQUISICAO_CAMINHO,self.vetPontos, matCustos])
        s.sendall(dados_enviar)

        while True:
           retorno = s.recv(5096)
           retorno = pickle.loads(retorno)

           if retorno[0] == comunic.MSG_RESPOSTA_CAMINHO: # concluído :
              s.close()
              informaResultadoThread(retorno,self.numThread)
              return retorno
           elif retorno[0] == comunic.MSG_INFORMACAO: # informação de um servidor sobre menor custo achado por lá:
              for i in range(len(self.vetServidores)):
                  if i != self.numThread:             # avisa aos demais, para reduzir o escopo das suas buscas
                      try:
                          serv = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
                          serv.connect((self.vetServidores[i][0], self.vetServidores[i][4]))
                          dados_enviar=pickle.dumps([comunic.MSG_INFORMACAO, retorno[1]])
                          serv.sendall(dados_enviar)
                          serv.close
                      except ValueError:
                          print "Erro ao tentar comunicar com ", self.vetServidores[i][0]
                          pass
           else:
               print "Retorno não identificado:", retorno


def processaPontosServidor(vetPontos, matrizCustos, conn):

    global matCustos

    matCustos = matrizCustos

    nTotCidades  = len(matCustos[0])-1

    listaNos   = Queue.PriorityQueue() 

    # coloca os pontos recebidos na fila
    for p in vetPontos:        
       prioridade = 1/float(p.nivel) + p.custo/1000000.0   
       listaNos.put((prioridade,p))

    p.custo = np.Inf
    solucaoCandidata = p

    lAchouSolucao = False
    nTotalDeNosAvaliados=0            # contador de nós gerados na solução

    while (not lAchouSolucao):
        # Pega próximo nó para o BRANCH, na fila prioritária (menor custo)
        ponto=listaNos.get()[1]       # elemento 1 contém o objeto ponto

        if (ponto.custo < solucaoCandidata.custo or solucaoCandidata.custo == np.Inf) and (ponto.custo < comunic.menorCustoRemoto):

            # Faz o branch do nó, gerando todos os nós do nível abaixo dele
            filhos = criaPontosFilhos(ponto,nTotCidades)
            for f in filhos:
                nTotalDeNosAvaliados += 1
                if f.custo < solucaoCandidata.custo:  # nó com custo viável?
                    # prioriza os nós de ramos mais adiantados para a busca
                    prioridade = 1/float(f.nivel) + f.custo/1000000.0   
                    listaNos.put((prioridade,f))  # coloca o novo nó na fila

                    if f.nivel == nTotCidades:   # chegou em solução alternativa?
                        solucaoCandidata = guardaMelhorSolucao(f,solucaoCandidata)                    

                        # Avisa sobre solução temporária encontrada
                        infor = [comunic.MSG_INFORMACAO, solucaoCandidata.custo]
                        infor = pickle.dumps(infor)
                        conn.sendall(infor)

        if listaNos.empty():  # Tour concluído!
            lAchouSolucao = True

    return [solucaoCandidata.cidadesVisitadas, solucaoCandidata.custo]

def bubbleSort(pontos):    
    n=len(pontos) 
    # leva o maior elemento para o final a cada passo
    for i in range(0,n): 
        for j in range(0,n-1-i): 
            if(pontos[j+1].custo < pontos[j].custo): 
                pontos[j], pontos[j+1]= pontos[j+1], pontos[j] 

    return pontos

def encontraCaminho():
    global matCustos

    nTotCidades  = len(matCustos[0])-1

    t0 = time.time()

    pontoInicio = Ponto(0,0,1,[])    # Inicia pela cidade 1 

    # Servidores disponíveis
    vetServidores = [  ["192.168.1.6",50020], ["192.168.1.6",50021], ["192.168.1.6",50022], ["127.0.0.1",50020] ] 

    # Calcula quantos pontos cada servidor receberá
    qtdePontosServidor, qtdeDistribuida = [], 0
    for i in range(len(vetServidores)):
        qtdePontosServidor.append(nTotCidades // len(vetServidores))
        qtdeDistribuida += qtdePontosServidor[i]

    qtdePontosServidor[i] += nTotCidades - qtdeDistribuida - 1

    # Gera os nós iniciais da árvore e ordena por custo, para
    # fazer a distribuição mais heterogênea possível e, em tese,
    # otimizar o processamento em cada servidor
    filhos = criaPontosFilhos(pontoInicio,nTotCidades)
    filhos = bubbleSort(filhos)

    # Distribui os pontos
    indProxServer = 0
    pontos = [ [] for i in range(len(vetServidores))]
    for i in range(len(filhos)):
       pontos[indProxServer].append(filhos[i])
       indProxServer += 1
       if indProxServer == len(vetServidores):
           indProxServer = 0

    # Inicializa uma thread para cada servidor
    threads = []
    for i in range(len(vetServidores)):
       thread=inicializaServidor(i,vetServidores,pontos[i],matCustos)    
       thread.start()
       threads.append(thread)

    for t in threads:
       t.join()

    print "FIM "    , nTotCidades, " cidades"

    # Fim:
    t1 = time.time()
    print "Tempo de execução (s):", t1-t0

if __name__ == '__main__':

    np.random.seed(0)

    # Teste com número crescente de cidades
    for i in range(10,22): 
       matrizAleatoria(i)   
       encontraCaminho()

CaixeiroBBServerv2.py: (Servidor)

import sys
import socket, pickle
import CaixeiroBB_Local_v2
import threading
import numpy as np
import CaixeiroBB_Local_v2_var as comunic

global matCustos

from CaixeiroBB_Local_v2 import processaPontosServidor
from CaixeiroBB_Local_v2 import Ponto

class threadMelhorCaminho(threading.Thread):

     global matCustos

     def __init__(self, vetPontos, matCustos, conn, socket):
        threading.Thread.__init__(self)
        self.vetPontos=vetPontos        
        self.matCustos=matCustos
        self.conn=conn
        self.socket=socket

     def run(self):

         # processa o pedido
         melhorCaminho = processaPontosServidor(self.vetPontos, self.matCustos, self.conn)
         caminho = melhorCaminho[0]
         custo   = melhorCaminho[1]

         print "Melhor caminho:", caminho
         print "Custo:", custo

         # informa ao Cliente
         retorno = [comunic.MSG_RESPOSTA_CAMINHO , caminho, custo]
         retorno = pickle.dumps(retorno)
         self.conn.sendall(retorno)

if __name__ == "__main__":

    HOST = 'localhost'    
    if len(sys.argv) == 1:
       PORT = 50020   # default
    else:
       PORT = int(sys.argv[1]) # específica

    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.bind((HOST, PORT))
    s.listen(1)
    print "Pronto", HOST, ":", PORT
    conexoes=[]
    while True:
        conn, addr = s.accept()
        conexoes.append(conn)
        while True:
            data = conexoes[len(conexoes)-1].recv(5096)
            if not data: break

            dadosRecebidos=pickle.loads(data)
            if dadosRecebidos[0] == comunic.MSG_REQUISICAO_CAMINHO:   # solicitação de processamento
               print "==========================================="
               print 'Chamada de ', addr
               print "Recebi ", len(dadosRecebidos[1]), " pontos da arvore"
               comunic.menorCustoRemoto=np.Inf
               thread = threadMelhorCaminho(dadosRecebidos[1], dadosRecebidos[2],conexoes[len(conexoes)-1],s)    
               thread.start()
            elif dadosRecebidos[0] == comunic.MSG_INFORMACAO:  # informação
               print "Informacao de menor custo:", dadosRecebidos[1]
               if dadosRecebidos[1] < comunic.menorCustoRemoto:
                   comunic.menorCustoRemoto = dadosRecebidos[1]
            else:
                print "msg:", dadosRecebidos[0]
            break
...