El cartero “Jimmy Carter” todos los días debe repartir por todo el barrio las cartas de los
vecinos. A diario Jimmy debe resolver el problema de generar la ruta ruta de mínimo costo para
entregar todas las cartas . Considere que “Don Carter” debe entregar N cartas y que i-ésimo
Pi está localizado mediante las coordenadas (x i , y i ) de su domicilio. La
destinatario
distancia euclidiana entre dos puntos P1=( x1, y 1 ) y P2=(x2, y 2 ) se define como:
d ( P1, P2 )=√ ( x 1−x 2)2 +( y 1− y 2)2 . Considere que una ruta de N domicilios es una secuencia
ordenada de la forma: { p1, p2, ... , p N } y donde la distancia de la ruta es la suma de las
distancias entre puntos consecutivos más la distancia entre el último y primer domicilio. Jimmy
dispone de las direcciones de los destinatarios de su próximo recorrido diario en un archivo
llamado “plano.dest”, el que se indica en cada línea las coordenadas (x i , y i ) de un domicilio.
El plano del próximo recorrido se muestra en la Figura 1.
Figura 1. Plano de direcciones de los destinarios
Dado lo anterior programa las siguientes funciones en python:
a) Generación aleatoria de K rutas de domicilios, donde el parámetro K es pasado por
línea de comando. El programa debe mostrar por pantalla cada ruta.
b) Se define el vecino cercano del domicilio d i como la cuidad d j que se encuentra a
menor distancia. Genere una ruta de vecinos cercanos de un domicilio Pi , donde i
es pasado como parámetro por línea de comandos.
c) Visualizar la generación de 4 rutas de vecinos cercanos (cuidad inicial aleatoria) en un
mismo plot, empleando matplotlib subplots. La visualización debe generar una imagen
llamada “cuatro_vecinos.png” que debe guardarse en la misma ruta donde se ejecuta el
programa que usted debe implementar.
Normas de entrega
•
•
•