es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Encontrar el camino más corto entre ciertos puntos en el sistema de coordenadas en Python.

Encontrar el camino más corto entre ciertos puntos en el sistema de coordenadas en Python.

11 Jun, 2023 Programación

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.

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    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:

    tours = []
for i in range(10): # repetir 10 veces
    start_point = random.choice(sample) # elegir un punto de inicio aleatorio
    unvisited_points = sample.copy()
    unvisited_points.remove(start_point)
    tour = [start_point]
    total_distance = 0

    while unvisited_points:
        distances = distance_matrix([tour[-1]], unvisited_points)[0]
        nearest_point_index = distances.argmin()
        nearest_point = unvisited_points[nearest_point_index]
        tour.append(nearest_point)
        total_distance += distances[nearest_point_index]
        unvisited_points.remove(nearest_point)

    tours.append((i+1, tour, total_distance)) # agregar información del recorrido a la lista de recorridos

for tour in tours:
    print(f"Número de recorrido:{tour[0]}")
    print(f"Número de puntos visitados en orden en la ronda correspondiente: {'-'.join(str(sample.index(p)) for p in tour[1])}")
    print(f"Longitud total de la ruta del recorrido: {tour[2]:.5f}")

    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 biblioteca scipy.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.

Comments are closed.