Domanda Algoritmo per trovare il punto di distanza totale minima dalle posizioni


Sto costruendo un'applicazione basata sulla ricerca di un "punto d'incontro conveniente" dato un insieme di posizioni.

Attualmente sto definendo "conveniente" come "minimizzare la distanza totale di viaggio". Questo è un problema diverso dalla ricerca del centroide come illustrato dall'esempio seguente (usando le coordinate cartesiane piuttosto che latitudine e longitudine per comodità):

  • A è a (0,0)
  • B è a (0,0)
  • C è a (0,12)

La posizione della corsa totale minima per questi punti è a (0,0) con una distanza di viaggio totale di 12; il centroide è a (0,4) con una distanza di viaggio totale di 16 (4 + 4 + 8).

Se la posizione era limitata ad essere in uno dei punti, il problema sembra essere più semplice, ma questo non è un vincolo che intendo avere (a differenza, ad esempio, questa domanda altrimenti simile).

Quello che non riesco a fare è trovare una sorta di algoritmo per risolvere questo - suggerimenti accolti per favore!


15
2018-01-03 20:19


origine


risposte:


Ecco una soluzione che trova il punto medio geografico e poi esplora iterativamente le posizioni vicine per adattarlo al punto di distanza totale minimo.

http://www.geomidpoint.com/calculation.html

Questa domanda è anche abbastanza simile a

Somma minima di tutti i tempi di viaggio

Ecco un articolo di Wikipedia sul problema generale che stai cercando di risolvere:

http://en.wikipedia.org/wiki/Geometric_median


11
2018-01-03 20:38



In un certo senso ciò che sembri cercare è il centro di massa di un triangolo con pesi uguali ai vertici. Ciò farebbe riferimento alle coordinate baricentriche.

Quando si va oltre un triangolo ci sono soluzioni per le coordinate baricentriche generalizzate e si potrebbero dare priorità alle persone modificando il peso dei vertici. Ciò che ancora non darebbe conto delle distanze su una mappa reale (non può semplicemente andare dritto in qualsiasi direzione) ma potrebbe essere un inizio?


3
2018-01-03 20:38



Un'opzione consiste nel definire una funzione obiettivo (e gradiente) e utilizzare una libreria di ottimizzazione generica, come ad esempio scipy.optimize. fmin_cg sarebbe un buon algoritmo per provare il tuo problema. Il tuo obiettivo sarebbe la somma delle distanze come definito nella sezione "Definizione" del Pagina di Wikipedia mediana geometrica referenziato con l'accetta. L'argomento della tua funzione obiettivo è y.


1
2018-01-03 21:21