5

El objetivo de este problema es crear un camino el cual sea la distancia más corta, el cual consiste en:

  1. Las ciudades a visitar empiezan desde el nodo 0.

  2. Elegir la distancia mas corta del nodo 0 comparado con el resto de nodos -> (0, nodo_actual).

  3. 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).

  4. Un nodo no puede visitarse a si mismo, todos los nodos deben de ser visitados.

  5. 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: ** introducir la descripción de la imagen aquí

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.

5
  • ¿Qué has intentado? Si son ejercicios de clase, lo fundamental es que lo intentes tú para aprender
    – fedorqui
    el 8 oct. 2019 a las 4:58
  • Fueron 2 problemas, el Nearest de TSP y el Cheapest de TSP, pude completar el Nearest pero al momento de comparar los valores con la formula para el cheapest, no me da los resultados correctos, y no lo he logrado.
    – Axel
    el 8 oct. 2019 a las 5:02
  • Copia pues en la pregunta el código que tienes hasta el momento, para ver dónde te has encallado
    – fedorqui
    el 8 oct. 2019 a las 5:03
  • 2
    Listo, sigo batallando para implementar la formula dentro de mi codigo, ya tengo los nodos a visitar pero sin la restriccion de que la suma de sus distancias sea menos conforme la insercion de cada nodo.
    – Axel
    el 8 oct. 2019 a las 6:10
  • @Axel Te he cambiado el título a la pregunta, espero que no te moleste, pues el anterior no se entendía bien. Quizás con el nuevo título recibas más ayuda. Si no te gusta, siéntete libre de editarlo de nuevo y dejarlo a tu gusto, pero intenta que guarde relación con lo que se pregunta.
    – abulafia
    el 8 oct. 2019 a las 9:12

1 respuesta 1

3

La cosa es más complicada de lo que has planteado. He implementado una solución, pero no te la doy de momento para que sigas intentándolo por ti mismo. Te doy no obstante el psecudocódigo junto con pistas sobre las estructuras de datos más apropiadas para simplificar la implementación.

  1. Conviene que tengas, además de la lista NN en la que está la ruta que has construido hasta el momento, otra lista en la que tengas los nodos que aún no están en la ruta. Llamemos a esta otra ruta sin_visitar, por ejemplo. Inicialmente tendrá todos los nodos, pero a medida que vayas eligiendo algunos para formar parte de la ruta, los vas eliminando de esta otra lista con sin_visitar.remove().
  2. Comienzas añadiendo 0 a NN y por tanto eliminándolo de sin_visitar
    • Después encuentras el nodo con menor distancia a 0 y lo añades a NN (eliminándolo por tanto también de sin_visitar)
  3. Y ahora viene la parte complicada. MIENTRAS aún haya nodos sin_visitar, debes repetir lo siguiente:

    1. Para cada pareja de nodos consecutivos en la ruta NN (llamémosles inicio y fin)
      • Para cada nodo en la lista sin_visitar
        • Calcular el delta_f que supone insertar ese nodo entre inicio y fin, usando la fórmula. Sería por tanto delta_f = distancias[inicio, nodo] + distancias[nodo, fin] - distancias[inicio,fin]
        • Ir recopilando estas distancias en una estructura de datos adecuada. Por ejemplo un diccionario cuya clave sea (nodo, (inicio, fin)) y cuyo valor sea el delta_f que has calculado
    2. Una vez has terminado los bucles anidados de 3.1, en el diccionario descrito tienes la información necesaria para elegir el siguiente nodo y dónde debe ser insertado. El valor menor de ese diccionario te da el delta_f más pequeño, y la clave correspondiente te dice qué nodo insertar y dónde.
    3. Inserta el nodo elegido en la posición adecuada de NN. Elimina ese nodo de sin_visitar
  4. Cuando sin_visitar esté vacía, saldrás del bucle y en NN tendrás la solución buscada.

Por si te sirve para aclararte el algoritmo, esta es la salida que produce mi código (en el que he insertado una serie de print() para depuración en el bucle MIENTRAS y en los bucles internos, que van mostrando las posibilidades que se van probando):

RUTA DE MOMENTO: 0-3-0
Sin visitar: [1, 2]
  Considerando par (0, 3)
    Probando a insertar 1 en medio de (0, 3) el coste es 8
    Probando a insertar 2 en medio de (0, 3) el coste es 19
  Considerando par (3, 0)
    Probando a insertar 1 en medio de (3, 0) el coste es 8
    Probando a insertar 2 en medio de (3, 0) el coste es 19
Se elige insertar el nodo 1 entre el par (0, 3) por ser el menor coste (8)

RUTA DE MOMENTO: 0-1-3-0
Sin visitar: [2]
  Considerando par (0, 1)
    Probando a insertar 2 en medio de (0, 1) el coste es 20
  Considerando par (1, 3)
    Probando a insertar 2 en medio de (1, 3) el coste es 21
  Considerando par (3, 0)
    Probando a insertar 2 en medio de (3, 0) el coste es 19
Se elige insertar el nodo 2 entre el par (3, 0) por ser el menor coste (19)

RUTA FINAL: 0-1-3-2-0
6
  • Muchas gracias, y eso lo que busco a veces, una idea explicada para entender mejor este tipo de problemas complejos, muchas gracias!!!
    – Axel
    el 8 oct. 2019 a las 12:33
  • 1
    @Axel De nada! Me alegra que te haya aclarado las ideas. Si tienes problemas pythónicos para implementarlo, ya sabes, pregunta de nuevo y muestra hasta dónde has llegado.
    – abulafia
    el 8 oct. 2019 a las 13:09
  • Okay si estoy batallando demasiado por la falta de experiencia programar, al momento que elimino el nodo que esta dentro de sin_visitar, cuando busca el proximo minimo al final del loop, dice que no puede encontrar uno y ya intente darle un rango pero nada mas no.
    – Axel
    el 8 oct. 2019 a las 16:38
  • No sé si estoy entendiendo tu problema, pero el diccionario ese que se construye en ese loop hay que volver a crearlo vacío cada vez que se itera en el MIENTRAS del paso 3. Pero casi mejor que abres otra pregunta y muestras tu código.
    – abulafia
    el 8 oct. 2019 a las 16:55
  • En los cambios que puse, me esta agarrando mal el nodo pasado mas minimo, y no me deja compararlo con el nuevo, no se si me puedas ayudar checando que esta mal en esa parte
    – Axel
    el 11 oct. 2019 a las 18:37

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.