[ Foro de Python ]

Algoritmo genético TSP

25-Apr-2020 03:14
Invitado (Isma)
0 Respuestas

Buenas, encontré este algoritmo genético para resolver el TSP, però necesito ayuda para que se printee por consola "La mejor ruta és, con una distancia recorrida de: " + distancia + ", " + mejor ruta (ej: 3,4,2,1)
Se que parece que soy tonto, pero me interessa mucho este problema y apenas estoy empezando a programar. Espero que alguien me pueda ayudar. SInceramente, me hariais un gran favor.

import random
import math

class Nodo(object):
def __init__(self, Nombre = "", X = 0, Y = 0, Nodo = None):
if Nodo is None:
self.Nombre = Nombre
self.X = X
self.Y = Y
else:
self.Nombre = Nodo.Nombre
self.X = Nodo.X
self.Y = Nodo.Y
self.Padre = None

def GenerarPoblacion(nNodos, distancia):
rango = 10**distancia - 1
nodos = []
poblacion = []

for i in range(nNodos):
nombre = i + 1
x = random.randint(-rango, rango)
y = random.randint(-rango, rango)
nodo = Nodo(Nombre =  nombre, X = x, Y = y)
nodos.append(nodo)

for nodo in nodos:
nodosPorVisitar = nodos[:]
nodosPorVisitar.remove(nodo)
GenerarArbol(nodo, nodosPorVisitar, poblacion)

return poblacion


def GenerarArbol(raiz, nodosPorVisitar, poblacion):
if len(nodosPorVisitar) > 0:
for nodo in nodosPorVisitar:
nodosFaltantes = nodosPorVisitar[:]
nodosFaltantes.remove(nodo)
hijo = Nodo(Nodo = nodo)
hijo.Padre = raiz
GenerarArbol(hijo, nodosFaltantes, poblacion)

else:
n = raiz
solucion = []
while n is not None:
solucion.append(n)
n = n.Padre
solucion.reverse()
poblacion.append(solucion)

def CalcularRuta(solucion):
total = 0
for i in range(len(solucion) -1):
x1 = solucion[i].X
x2 = solucion[i + 1].X
y1 = solucion[i].Y
y2 = solucion[i + 1].Y
total = total + math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
return total


if __name__ == "__main__":
nNodos = int(input("Ingrese cantidad de nodos: "))
distancia = int(input("Ingrese valor de distancia: "))

poblacion = GenerarPoblacion(nNodos, distancia)
for solucion in poblacion:
string = "["
for nodo in solucion:
string = string + str(nodo.Nombre) + " "

print(string + "] = " + str(CalcularRuta(solucion)))

for nodo in poblacion[0]:
print(str(nodo.Nombre) + " X=" + str(nodo.X) + " Y=" + str(nodo.Y))




Si ya eres usuario del sistema, puedes contestar desde tu cuenta y así ganar prestigio.

Si sólo eres un visitante, puedes optar por...