Encontrar el camino más corto entre ciertos puntos en el sistema de coordenadas en Python.
He escrito un código que produce el número deseado de puntos en un cierto rango de longitud y anchura en el sistema de coordenadas. Calcula y tabula la matriz de distancias de estos puntos que he producido utilizando el método euclidiano.
Mi código está aquí:
import pandas as pd
from scipy.spatial import distance_matrix, distance
import random
npoints = int(input("Ingrese la cantidad de puntos: "))
width = float(input("Ingrese la anchura que desea: "))
height = float(input("Ingrese la altura que desea: "))
sample = []
for _ in range(npoints):
sample.append((width * random.random(), height * random.random()))
print(*[f"({w:.2f}, {h:.2f})" for w, h in sample], sep=', ')
mat_dist = distance.cdist(sample, sample, 'euclidean')
df_mat_dist = pd.DataFrame(mat_dist)
print(df_mat_dist)
La salida es:
Ingrese la cantidad de puntos: 5
Ingrese la anchura que desea: 6
Ingrese la altura que desea: 7
(2.26, 6.42), (0.19, 3.95), (2.76, 5.23), (5.69, 1.22), (0.28, 5.30)
0 1 2 3 4
0 0.000000 2.728079 0.797178 6.142169 2.811000
1 2.728079 0.000000 2.957627 5.387845 2.850051
2 0.797178 2.957627 0.000000 5.409880 2.597715
3 6.142169 5.387845 5.409880 0.000000 5.427921
4 2.811000 2.850051 2.597715 5.427921 0.000000
Quiero crear un algoritmo que pase por todos los puntos en el camino más corto, comenzando desde uno aleatorio de los puntos ingresados. (El método del vecino más cercano continúa encontrando el punto más cercano al punto de partida según la distancia euclidiana. Luego va al punto más cercano a este nuevo punto entre los puntos no conectados. Este proceso continúa hasta que se recorren todos los puntos y se completa la ronda). ¿Cómo puedo repetir este proceso 10 veces en 10 puntos diferentes y obtener una salida como esta?
Número del recorrido: 1
Número de puntos visitados en orden en el recorrido relevante: 0-7-3-8-2...
Longitud total del recorrido: 18,75755
Número del recorrido: 2
Número de puntos visitados en orden en el recorrido relevante: 6-9-11-2-7...
Longitud total del recorrido: 14,49849
.
...
Muchas gracias por la ayuda.
davy.ai
Para crear un algoritmo que recorra todos los puntos en el camino más corto, comenzando desde uno de los puntos introducidos al azar utilizando el método del vecino más cercano, se puede utilizar el siguiente código:
Este código repite el proceso 10 veces, elige un punto de inicio aleatorio y encuentra el punto no visitado más cercano utilizando la matriz de distancia con
distance_matrix ()
de la bibliotecascipy.spatial
. Luego agrega el punto más cercano al recorrido y actualiza la distancia total. Este bucle continúa hasta que se visitan todos los puntos. La información del recorrido se almacena en una lista de tuplas, y luego se imprime la información de cada recorrido.La salida de este código será similar a la salida deseada, con el número de recorrido, el orden de los puntos visitados en la ronda y la longitud total de la ruta del recorrido.