def Troca(x,y,p): #ponto p(x,y)
    i,f=np.random.randint(0,30,size=2) #randomico entre i e f da rota
    #temp=ponto[i].copy()
    #p[i],p[f]=p[f],temp
    p[i],p[f]=p[f],p[i]     #guarda a sequência dos vértices
    x[i],x[f]=x[f],x[i]
    y[i],y[f]=y[f],y[i]

def Inverte():
    pass
def Tranlacao():
    pass
#sugestão verificar Cruzamentos e retirar cruzamentos
def tiraCruzamento()
    pass

# =============================================================================
# Função usada para calculo da energia das ligações entre os vértices    
# =============================================================================
def Energia(x,y):
    xa=np.append(x,x[0])
    ya=np.append(y,y[0])
    #xa[1:-1] = x[1], x[2], ...x[n-1]
    #xa[0:-2] = xa[:-2] = x[0], x[x1], ...x[n-2]
    dx2=np.power(xa[1:-1]-xa[:-2],2) # x[1..n-1]  x[0 .. n-2] :=> (x[1]-x[0])^2 + (x[2] - x[1])^2 +  ...(x[n-1]-x[n-2])^2 
    dy2=np.power(ya[1:-1]-ya[:-2],2)
    return np.sum(np.sqrt(dx2+dy2))  #distancia euclidiana

   #tpxy=list(zip(p,xl,yl))
# =============================================================================
# INICIO DO PROGRAMA
# =============================================================================

#Digitar no spyder ou IPython %matplotlib auto
import numpy as np
import matplotlib.pyplot as plt
import time as tm
import math as mt
import random as rd
np.seterr(over='ignore')
plt.close() #fecha alguma figura aberta
plt.ion()  #necessário adicionar quando se faz procedimento iterativo
x=np.random.randint(0,30,size=30,dtype=int) #gera aleatoriamente 30 x
y=np.random.randint(0,30,size=30,dtype=int) #'                     'y
p=np.arange(0,30,1)
xl=list(x)
yl=list(y)
xl.append(xl[0])   #adiciona o primeiro elemento para que possa ser 
yl.append(yl[0])   #ligado do ultimo ao primeiro       
plt.suptitle("Tempera Simulada Para Problema do Caixeiro Viajante\n\n") #titulo para a figura     
plt.subplot(1,2,1) #seleciona o primeiro axes (subgrafico ou gráfico)
plt.plot(xl,yl,'c-',xl,yl,'ro') #uma figura é composta de um ou mais gráficos ou subgráficos
plt.title("Configuração Inicial")   #Titulo para o gráfico
Perturba(x,y,p)    #Esta função é que dá uma chacoalhada no sistema
plt.axis([-1,31,-1,31])       #define o limite do gráfico x=-1 a 31, y=-1 a 31
figManager = plt.get_current_fig_manager()
figManager.window.showMaximized() #maximiza a janela da figura
rd.seed(int(tm.time())) #seleciona uma semente
#se quizer que a sequência seja a mesma, faça:
#rd.seed(234568)    
xl=list(x)
yl=list(y)
xl.append(xl[0])              #adiciona o ultimo elemento para que possa ser 
yl.append(yl[0])              #plotada a volta para a cidade de origem
plt.subplot(1,2,2)            #seleciona o segundo gráfico que mudara iterativamente
plt.plot(xl,yl,xl,yl,'ro')    #liga cada ponto ao outro, e plota cada ponto como
                              #um círculo vermelho (red)
                              
plt.title("Energia: "+str(Energia(xl,yl)))                            
plt.draw() #melhor usar draw(), pois show() pode dar problema
plt.pause(0.000000000000000005) #permite pausar para mostrar plotagem
#plt.pause(0)
KB=1.38*(10**(-23))       #constante de Boltzman
t=373
n=30
escala=0.1; #escala de redução da temperatura    
nSucesso = 0
total = 0
nFracasso = 0 
sucContinuo=False         
#for j in range(100):                   #é obvio que este laço não será assim
while total<100:
    nSucesso=0
    nFracasso=0
    continua = True
    #ou 10n sucessos ou 100n fracassos
    #para 12 cidades sucesso <=120 ou fracasso <= 1200 xor(A,B)= not(A)B+ Anot(B)
    
    while ((nSucesso<=10*n) and (nFracasso<=100*n)):
    #while ((not (nSucesso <= 10*n)) or (nFracasso <=100*n)) and ((nSucesso <= 10*n) or (not (nFracasso <=100*n))):   
        oldp=p.copy()
        oldx=x.copy()
        oldy=y.copy()
        
        Ec=Energia(x,y) #Energia corrente
        Perturba(x,y,p) #retorna com novo x,y,p
        Enew=Energia(x,y) #Nova energia após a perturbação
        probabilidade = 1
        deltaE=Ec-Enew
        if deltaE<0:
            probabilidade =(1/(1+mt.exp(deltaE/(KB*t))))
        
        probNovoEst=rd.random()
        
        if (probNovoEst < probabilidade): #aceita a nova configuracao
            if sucContinuo:
                nSucesso +=1
                #probabilidade=0
            else:
                nSucesso = 1      #primeiro sucesso, ou primeiro apos fracassos
                sucContinuo = True
                #nFracasso =0
            #nSucesso +=1
            Ec=Enew
            xl=list(x)
            yl=list(y)
            xl.append(xl[0])    #adiciona o primeiro elemento para que possa ser 
            yl.append(yl[0])    #ligado do ultimo ao primeiro
            plt.subplot(1,2,2)  #seleciona o segundo subgrafico ou eixo da figura
            plt.cla()           #limpa o eixo (gráfico) corrente
            plt.plot(xl,yl,xl,yl,'ro') #plota
            
            plt.title("Energia: "+str(Ec)+"  Temperatura: "+str(t))
            if deltaE<0:
                plt.xlabel('deltaE: '+ str(deltaE)+ '  prob: {:.2f}'.format(probabilidade))
            plt.draw()
            plt.pause(0.0000000005) #permite pausar para mostrar plotagem
        else:
            p = oldp.copy()
            y = oldy.copy()
            x = oldx.copy()
            nFracasso += 1
            if deltaE<0:
                if not sucContinuo:
                    nFracasso +=1
                else:
                    nFracasso = 1    #primeiro fracasso, ou primeiro apos sucessos
                    sucContinuo = False
#                    #nSucesso=0
                #plt.subplot(1,2,2)  #seleciona o segundo subgrafico ou eixo da figura
                #plt.cla()    
                #plt.xlabel('deltaE: '+ str(deltaE)+ '  prob: '+str(probabilidade))
                #plt.draw()
                #plt.pause(0.0000000005) #permite pausar para mostrar plotagem 
            plt.subplot(1,2,2)  #seleciona o segundo subgrafico ou eixo da figura
            plt.cla()           #limpa o eixo (gráfico) corrente
            plt.plot(xl,yl,xl,yl,'ro') #plota
            plt.title("Energia: "+str(Ec)+"  Temperatura: "+str(t))
            if deltaE<0:
                plt.xlabel('deltaE: '+ str(deltaE)+ '  prob: {:.2f}'.format(probabilidade))
           
            plt.draw()
            plt.pause(0.0000000005) #permite pausar para mostrar plotagem        
        #continua=(nSucesso<=10*n) and (nFracasso<=100*n)
    t=t*(1-escala)
    total +=1
plt.subplot(1,2,2)    
plt.xlabel('Concluido')     
plt.draw()    
#input('Fim da simulação')