algorithm - online - camino mas corto dijkstra c++
Algoritmo para encontrar el punto de distancia total mínima desde ubicaciones (3)
Aquí hay una solución que encuentra el punto medio geográfico y luego explora iterativamente las posiciones cercanas para ajustar eso hacia el punto de distancia total mínimo.
http://www.geomidpoint.com/calculation.html
Esta pregunta también es bastante similar a
Suma mínima de todos los tiempos de viaje
Aquí hay un artículo de wikipedia sobre el problema general que intentas resolver:
Estoy creando una aplicación basada en la búsqueda de un "punto de encuentro conveniente" dado un conjunto de ubicaciones.
Actualmente estoy definiendo "conveniente" como "minimizando la distancia total de viaje". Este es un problema diferente al encontrar el centroide como se ilustra en el siguiente ejemplo (usando coordenadas cartesianas en lugar de latitud y longitud por conveniencia):
- A está en (0,0)
- B está en (0,0)
- C está en (0,12)
La ubicación del recorrido total mínimo para estos puntos es en (0,0) con una distancia total de viaje de 12; el centroide está en (0,4) con una distancia total de viaje de 16 (4 + 4 + 8).
Si la ubicación se limitara a estar en uno de los puntos, el problema parece simplificarse, pero no es una restricción que pretendo (a diferencia de, por ejemplo, esta pregunta similar ).
Lo que parece que no puedo hacer es encontrar algún tipo de algoritmo para resolver esto. ¡Sugerencias bienvenidas, por favor!
En cierto modo, lo que parece que estás buscando es el centro de masa de un triángulo con pesos iguales en los vértices. Eso apuntaría a coordenadas baricéntricas.
Al ir más allá de un triángulo, hay soluciones para las coordenadas baricéntricas generalizadas y puede dar prioridad a las personas modificando el peso de los vértices. Lo que todavía no explicaría las distancias en un mapa real (no puede viajar directamente en cualquier dirección) pero puede ser un comienzo.
Una opción es definir una función objetivo (y degradada) y usar una biblioteca de optimización genérica, como scipy.optimize . fmin_cg sería un buen algoritmo para tratar su problema. Su objetivo sería la suma de las distancias tal como se define en la sección "Definición" de la página de Wikipedia Mediana geométrica a la que hace referencia el hacha. El argumento de tu función objetivo es y .