Bucle infinito
Publicado por Mario (2 intervenciones) el 10/05/2020 21:01:29
Hola a todos
Estoy resolviendo un (tsp) problema del agente viajero con python me dieron unos datos pero me los entregaron como matriz de adyacencia, y el programa la logra convertir en una lista de listas pero al ejecutar el código se entra a un bucle infinito porque al final nunca imprime ni el recorrido ni el costo total. Y por más que lo he checado no he logrado ver mi error por lo que me gustaría recibir su apoyo.
La matriz es la siguiente:
Y está guardada en un archivo de tipo .txt de la siguiente manera:
-1 6 9 -1 -1 -1 -1 -1
6 -1 4 4 2 -1 -1 -1
9 4 -1 8 -1 -1 -1 -1
-1 4 8 -1 -1 16 -1 3
-1 2 -1 -1 -1 -1 1 6
-1 -1 -1 16 -1 -1 -1 -1
-1 -1 -1 -1 1 -1 -1 -1
-1 -1 -1 3 6 -1 -1 -1
En la matriz si el número es un -1 eso quiere decir que desde esa posición no se puede avanzar a dicho nodo y si el número es diferente de -1 ese es el "costo" para ir a dicho nodo
Mi código es el siguiente:
Estoy resolviendo un (tsp) problema del agente viajero con python me dieron unos datos pero me los entregaron como matriz de adyacencia, y el programa la logra convertir en una lista de listas pero al ejecutar el código se entra a un bucle infinito porque al final nunca imprime ni el recorrido ni el costo total. Y por más que lo he checado no he logrado ver mi error por lo que me gustaría recibir su apoyo.
La matriz es la siguiente:
Y está guardada en un archivo de tipo .txt de la siguiente manera:
-1 6 9 -1 -1 -1 -1 -1
6 -1 4 4 2 -1 -1 -1
9 4 -1 8 -1 -1 -1 -1
-1 4 8 -1 -1 16 -1 3
-1 2 -1 -1 -1 -1 1 6
-1 -1 -1 16 -1 -1 -1 -1
-1 -1 -1 -1 1 -1 -1 -1
-1 -1 -1 3 6 -1 -1 -1
En la matriz si el número es un -1 eso quiere decir que desde esa posición no se puede avanzar a dicho nodo y si el número es diferente de -1 ese es el "costo" para ir a dicho nodo
Mi código es el siguiente:
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
79
80
81
82
83
#Se convierte la matriz en una lista de listasdef Universo(A):
A = []
aux = []
with open("prueba.txt", "r") as archivo:
for linea in archivo: for num in linea:if num != '\n' and num != ' ':
if num == '-':
aux.append(-1)
elif num == '1':
pass
else:num = int(float(num))
aux.append((num))
A.append(aux)
aux = []
return A
A = []
inicio = int(input("Desde que nodo se va a recorrer? Recuerde que el primer nodo es el nodo 0 "))
fin = int(input("Hasta que nodo se va a recorrer? Recuerde que el último nodo es el 7 "))
print(Universo(A))
#Se obtendrá el recorrido en el caso de que se iteren los nodos de manera ascendentedef normal(U,B,inicio,fin):
k = inicio costo = 0recorrido = []
#Se recorren las líneas de la matrizwhile(k<fin):
fila = U[k]
n = krecorrido.append(B[k])
#Recorrido de los elementos de la lineawhile (n<fin):
#Se evalúa si ya no se puede avanzarif n != -1:
costo = costo + fila[n]
k = n-1
break
n = n+1
k = k+1
print("El recorrido fue:",recorrido)
print("El costo total fue:",costo)
return
#Se obtendrá el recorrido en el caso de que se iteren los nodos de manera descendentedef inverso(U,B,inicio,fin):
k = fin costo = 0recorrido = []
#Se recorren las líneas de la matrizwhile(k>=inicio):
fila = U[k]
n = krecorrido.append(B[k])
#Recorrido de los elementos de la lineawhile (n<=fin):
#Se evalúa si ya no se puede avanzarif n != -1:
costo = costo + fila[n]
k = n+1
break
n = n-1
k = k-1
print("El recorrido fue:",recorrido)
print("El costo total fue:",costo)
return
def backtrack(A,inicio,fin):
U = []
U = Universo(A)
B=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
if fin > inicio:
normal(U,B,inicio,fin)
else:inverso(U,B,inicio,fin)
return
backtrack(A,inicio,fin)
Valora esta pregunta
0