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:
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