El objetivo de este problema es crear un camino el cual sea la distancia más corta, el cual consiste en:
Las ciudades a visitar empiezan desde el nodo 0.
Elegir la distancia mas corta del nodo 0 comparado con el resto de nodos -> (0, nodo_actual).
El próximo nodo a elegir (nodo_actual, nuevo_nodo), sera comparado con la siguiente formula: d(i, k) + d(k, j) - d(i, j).
Un nodo no puede visitarse a si mismo, todos los nodos deben de ser visitados.
El nodo final debe ser el mismo que el inicial (0 en este caso).
Ejemplo:
my_distances =
{(0,1)= 12,
(0,2): 17,
(0,3): 8,
(1,0): 12,
(1,2): 15,
(1,3): 4,
(2,0): 17,
(2,1): 15,
(2,3): 10,
(3.0): 8,
(3,1): 4,
(3,2): 10,
}
El procedimiento deberia ser asi:
[0] = 0
[0, 3] = 8
[0, 3, 1] = 12
[0, 3, 1, 2] = 27
[0, 3, 1, 2, 0] = 44 // se cambia la posicion del 1
[0, 1, 3, 2, 0] = 43
**Ese fue un pequeño ejemplo ya que las ciudades que seran visitadas en el problema que tengo, son de +200 nodos. Un ejemplo más claro podría ser: **
Esto es lo que he intentado pero no se como aplicar la formula en esta parte
NN = [starting_node]
non_visited = ciudades
fin =-1
inicio = 1
distances = {}
while len(NN)<=n:
fin = -1
k=NN[-1]
nn={(k,j): distancia[(k,j)] for j in ciudades if k!=j and j not in NN}
new=min(nn.items(), key=lambda x:x[1])
best = new[0][1]
if len(NN)>2:
NN.insert(fin,best)
print(NN)
nodes1 = list(zip(NN, NN[1:]))
print(nodes1)
while len(non_visited) > 0:
for start,end in nodes1:
print(best)
#print(start, end)
print(distancia[start,best])
print(distancia[best, new])
print(distancia[start,end])
delta_f = distancia[start,best] + distancia[best, end] - distancia[start,end]
distances[best] = [best]
else:
NN.append(best)
new = best
NN.append(last_node)
print(NN)
non_visited.remove(best)
Hasta ahi es lo que intente hacer, despues lo intentare reducir para que no se vea tanto codigo pero primero quiero que mi idea en codigo quede bien.