Python - Búsqueda Local Interrutas

Herramientas de cómputo python

View more PowerPoint from Jorge Sepúlveda

#DATOS

distance=[

[0.00,16.40,13.34,9.21,10.29,12.20,6.32,6.40,17.72,6.08,12.04,4.00,10.44,3.16,7.21,9.84,9.43,14.14,10.44,13.6,14.31],

[16.40,0.00,13,8.94,19.41,6.00,13.89,10.00,18.78,12.65,25.05,19.10,16.00,19.41,17.46,25.49,21.58,23.00,25.49,30.00,26.30],

[13.34,13.00,0.00,6.4,7.21,14.31,7.07,10.00,8.94,15.00,15.00,13.03,20.61,16.12,18.78,18.02,22.47,26.41,23.08,24.51,27.51],

[9.21,8.94,6.40,0.00,11.00,8.24,5.00,4.47,9.84,8.94,16.12,10.81,14.42,12.36,13.60,17.02,17.26,20.61,19.23,22.36,22.36],

[10.29,19.41,7.21,11.00,0.00,19.10,7.61,13.60,4.47,17.00,8.54,10.29,22.47,14.42,19.84,13.00,22.02,26.87,20.61,20.02,26.62],

[12.2,6.00,14.31,8.24,19.10,0.00,12.04,6.32,17.11,7.21,22.80,15.65,10.00,14.86,11.70,21.95,15.81,17.00,20.24,25.45,20.39],

[6.32,13.89,7.07,5.00,7.61,12.04,0.00,6.08,5.09,9.43,11.18,6.32,15.00,9.05,12.8,12.2,15.65,20.00,16.03,18.02,20.61],

[6.40,10.00,10.00,4.47,13.60,6.32,6.08,0.00,11.00,4.47,16.49,9.43,10.00,9.43,9.21,15.81,13.03,16.15,15.81,20.00,18.11],

[17.72,18.78,8.94,9.84,4.47,17.11,5.09,11.00,0.00,13.60,6.40,5.83,18.78,10.00,15.81,9.21,17.69,22.67,16.15,16.03,22.2],

[6.08,12.65,15.00,8.94,17.00,7.21,9.43,4.47,13.60,0.00,18.00,10.04,5.65,8.06,5.00,15.81,9.05,11.70,13.03,18.43,14.00],

[12.04,25.05,15.00,16.12,8.54,22.80,11.18,16.49,6.40,18.00,0.00,8.06,22.36,11.70,18.68,5.83,19.23,24.59,15.55,12.65,22.80],

[4.00,19.10,13.03,10.81,10.29,15.65,6.32,9.43,5.83,10.04,8.06,0.00,14.31,4.24,10.77,6.40,12.04,17.2,12.80,11.70,16.40],

[10.44,16.00,20.61,14.42,22.47,10.00,15.00,10.00,18.78,6.65,22.36,14.31,0.00,11.00,4.12,19.02,7.07,7.00,13.03,19.69,10.77],

[3.16,19.41,16.12,12.36,14.42,14.86,9.05,9.43,10.00,8.06,11.70,4.24,11.00,0.00,7.07,8.06,7.81,13.03,7.00,10.63,12.20],

[7.21,17.46,18.78,13.60,19.84,11.70,12.80,9.21,15.81,5.00,18.68,10.77,4.12,7.07,0.00,15.00,4.12,7.21,9.21,15.65,9.00],

[9.84,25.49,18.02,17.02,13.00,21.95,12.20,15.81,9.21,15.81,5.83,6.40,19.02,8.06,15.00,0.00,14.56,19.92,10.00,7.07,17.49],

[9.43,21.58,22.47,17.26,22.02,15.81,15.65,13.03,17.69,9.05,19.23,12.04,7.07,7.81,4.12,14.56,0.00,5.38,6.32,13.34,5.09],

[14.14,23.00,26.41,20.61,26.87,17.00,20.00,16.15,22.67,11.70,24.59,17.20,7.00,13.03,7.21,19.92,5.38,0.00,11.00,18.02,5.00],

[10.44,25.49,23.08,19.23,20.61,20.24,16.03,15.81,16.15,13.03,15.55,12.80,13.03,7.00,9.21,10.00,6.32,11.00,0.00,7.07,7.00],

[13.60,30.00,24.51,22.36,20.02,25.45,18.02,20.00,16.03,18.43,12.65,11.70,19.69,10.63,15.65,7.07,13.34,18.02,7.07,0.00,14.14],

[14.31,26.30,27.51,22.36,26.62,20.39,20.61,18.11,22.20,14.00,22.80,16.40,10.77,12.2,9.00,17.49,5.09,5.00,7,14.14,0.00],

]



coordenadas=[[0,15,12],[1,2,2],[2,2,15],[3,6,10],[4,6,21],[5,8,2],[6,9,14],[7,10,8],[8,10,19],[9,14,6],[10,14,24],[11,15,16],[12,18,2],[13,18,13],[14,19,6],[15,19,21],[16,23,7],[17,25,2],[18,25,13],[19,26,20],[20,28,6]]

#DATOS



#FUNCIONES

def city(x,y,k):

    res=750

    r=15

    xnorm=res/30

    ynorm=res/28

    x=x*xnorm

    y=y*ynorm

    canvas.create_oval(x-r, y-r, x+r, y+r, width = 0, fill = '#0000FF')

    canvas.create_text(x-r-5,y-r-5,text=k,fill="black")

    



def depot(x,y):

    res=750

    r=20

    xnorm=res/30

    ynorm=res/28

    x=x*xnorm

    y=y*ynorm

    canvas.create_oval(x-r, y-r, x+r, y+r, width = 0, fill = '#FF0000')

    canvas.create_text(x,y-r-8,text="Centro",fill="black")



def flecharp(city1,city2):

    res=750

    r=10

    xnorm=res/30

    ynorm=res/28

    x1=xnorm*coordenadas[city1][1]

    y1=ynorm*coordenadas[city1][2]

    x2=xnorm*coordenadas[city2][1]

    y2=ynorm*coordenadas[city2][2]

    canvas.create_line(x1, y1, x2, y2, width=4, arrow=LAST, dash=(2,2), fill='#FF0000')



def flechavp(city1,city2):

    res=750

    r=10

    xnorm=res/30

    ynorm=res/28

    x1=xnorm*coordenadas[city1][1]

    y1=ynorm*coordenadas[city1][2]

    x2=xnorm*coordenadas[city2][1]

    y2=ynorm*coordenadas[city2][2]

    canvas.create_line(x1, y1, x2, y2, width=4, arrow=LAST, dash=(2,2), fill='#FFA500')





def flechan(city1,city2):

    res=750

    r=10

    xnorm=res/30

    ynorm=res/28

    x1=xnorm*coordenadas[city1][1]

    y1=ynorm*coordenadas[city1][2]

    x2=xnorm*coordenadas[city2][1]

    y2=ynorm*coordenadas[city2][2]

    canvas.create_line(x1, y1, x2, y2, width=6, arrow=LAST, fill='#000000')



def flechaa(city1,city2):

    res=750

    r=10

    xnorm=res/30

    ynorm=res/28

    x1=xnorm*coordenadas[city1][1]

    y1=ynorm*coordenadas[city1][2]

    x2=xnorm*coordenadas[city2][1]

    y2=ynorm*coordenadas[city2][2]

    canvas.create_line(x1, y1, x2, y2, width=6, arrow=LAST, fill='#800080')





def near(jaja):

    k=0

    distance_near_city=999999

    while (k<=19):

        exist=(k in ruta)

        if(distance[jaja][k]0.00 and (not exist) ):

            distance_near_city=distance[jaja][k]

            best_near_city=k

        k=k+1

    return best_near_city





def graficar_rutaON(r):

    k=0

    while(k<=(len(r)-2)):

        flechan(r[k],r[k+1])

        k=k+1



def graficar_rutaOA(r):

    k=0

    while(k<=(len(r)-2)):

        flechaa(r[k],r[k+1])

        k=k+1



def graficar_rutaMRP(r):

    k=0

    while(k<=(len(r)-2)):

        flecharp(r[k],r[k+1])

        k=k+1



def graficar_rutaMVP(r):

    k=0

    while(k<=(len(r)-2)):

        flechavp(r[k],r[k+1])

        k=k+1



def distancia_ruta(ruta):

    distancia=0

    k=0

    while (k<(len(ruta)-1)):

        distancia=distancia+distance[ruta[k]][ruta[k+1]]

        k += 1

    return distancia



#FUNCIONES







    

#IMPRIMIR GRAFO

from Tkinter import * 

from sys import argv 



tk = Tk() # controlador de ventana

res=750

canvas = Canvas(tk, width = res, height = res, bg='#FFFFFF') # fondo de ventana



depot(15,12)

k=1

while (k<=20):

     city(coordenadas[k][1],coordenadas[k][2],k)

     k=k+1

#FIN IMPRIMIR GRAFO





#HEURISTICA INTERRUTAS



instancia=int(sys.argv[1])





if (instancia==1):

    ruta1=[0,19,20,17,16,14,12,9,5,1,6,7,0]

    ruta2=[0,3,2,4,8,10,15,18,13,11,0]



if (instancia==2):

    ruta1=[0,8,4,2,1,5,7,9,12,14,17,0]

    ruta2=[0,3,6,10,15,11,13,19,18,20,16,0]



if (instancia==3):

    ruta1=[0,9,10,17,8,16,14,13,18,19,15,0]

    ruta2=[0,11,12,20,4,6,3,2,1,5,7,0]













graficar_rutaON(ruta1)

graficar_rutaOA(ruta2)



print "Distancia Ruta 1", distancia_ruta(ruta1)

print "Distancia Ruta 2", distancia_ruta(ruta2)

orig_ruta1=distancia_ruta(ruta1)

orig_ruta2=distancia_ruta(ruta2)



print "Ruta 1 Original", ruta1

print "Ruta 2 Original", ruta2





#BUSQUEDA LOCAL

#PRUEBA INTERCAMBIANDO CADA UNO DE LAS CIUDADES EN LAS RUTAS PARA VER SI EXISTE UN INTERRUTEO CON DISTANCIA RECORRIDA MAS CORTA



j,k=1,1



optimoinicial=5

optimofinal=1



while(optimofinal    optimoinicial=distancia_ruta(ruta1)+distancia_ruta(ruta2)

    k,j=1,1

    while(j<(len(ruta1)-1) ):

        k=1

        while(k<(len(ruta2)-1) ):

            original=distancia_ruta(ruta1)+distancia_ruta(ruta2)

            ruta1[j],ruta2[k]=ruta2[k],ruta1[j]

            modified=distancia_ruta(ruta1)+distancia_ruta(ruta2)

            print "Paso ",j," Paso ",k," Original=",original," Modified=",modified

            if(modified                O_ruta1=ruta1

                O_ruta2=ruta2

                print "Cambio"

            else:

                ruta1[j],ruta2[k]=ruta2[k],ruta1[j]

        

            k += 1

        j += 1

    optimofinal=distancia_ruta(ruta1)+distancia_ruta(ruta2)







print "Ruta1: ", O_ruta1

print "Ruta2: ", O_ruta2



graficar_rutaMRP(ruta1)

graficar_rutaMVP(ruta2)



print "Distancia Nueva Ruta 1=", distancia_ruta(ruta1)," (cambio de ",orig_ruta1," a ",distancia_ruta(ruta1)," )"

print "Distancia Nueva Ruta 2=", distancia_ruta(ruta2)," (cambio de ",orig_ruta2," a ",distancia_ruta(ruta2)," )"







#BUSQUEDA LOCAL







#HEURISTICA INTERRUTAS









canvas.pack()

tk.mainloop()