Python - Algoritmo genético TSP

 
Vista:

Algoritmo genético TSP

Publicado por Isma (1 intervención) el 25/04/2020 03:11:18
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.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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))
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder