Matematicamente corretto A * euristico / stimatore di distanza per un grafico di latitudine / longitudine

Question

Matematicamente corretto A * euristico / stimatore di distanza per un grafico di latitudine / longitudine

#1 da (5 voti)

5

Ho un grafico in cui ogni nodo è un punto geografico sulla superficie della terra, definito dalle sue coordinate di latitudine / longitudine.

Modi corretti per calcolare la distanza tra due di questi punti potrebbero essere la formula di Haversine per i modelli di terra sferica, o il problema inverso di Vincenty per i modelli di terra sferoidale.

Ma questi sono molto costosi in termini di risorse computazionali, e in A * fondamentalmente non hai bisogno dei valori assoluti di quei risultati, ne hai solo bisogno per scopi di confronto.

Nel mio algoritmo A * la funzione euristica è la distanza più breve tra 2 punti (definita come la lunghezza dell'arco del cerchio grande più piccolo tra i 2 punti in un modello sferico) e il percorso effettivo tra due nodi è una stringa lineare, la cui lunghezza è calcolata fondamentalmente nello stesso modo, solo che sommi le distanze tra i vertici consecutivi.

Quindi, se d(A, B) è la distanza geografica effettiva tra A e B (come punti di latitudine / longitudine), il problema è fondamentalmente trovare lo stimatore di distanza computazionalmente efficiente d*(A, B) che soddisfi le condizioni necessarie affinché A * funzioni correttamente, come ad esempio:

se d(A, B) < d(C, D) poi d*(A, B) < d*(C, D) .
se d(A, B) + d(E, F) < d(C, D) poi d*(A, B) + d*(E, F) < d*(C, D)

Ho persino visto in alcuni luoghi che la gente consiglia la distanza euclidea per un caso del genere, anche se latitudine / longitudine sono angoli. Potrebbe essere il caso, ma sono interessato se è "matematicamente corretto" presumere che soddisfi condizioni come sopra.

language-agnostic math graph graph-traversal heuristics

posta Tiborg 22.01.2015 - 14:27

fonte

1 risposta

Leggi altre domande sui tag language-agnostic math graph graph-traversal heuristics

Come risolve il problema di coerenza nell'applicazione concomitante e distribuita (costruita attorno al dilemma dei banchieri)? Si tratta di un odore di invidia caratteristica?

score 5 · Accepted Answer

Se l'area in cui i nodi possono essere è piccola (relativamente, la metà della metà degli Stati Uniti è abbastanza piccola) e lontana dai poli, si può ragionevolmente affrontare il problema usando solo la longitudine e la latitudine come coordinate X / Y. Vicino ai poli puoi trattarli come coordinate polari con la latitudine di 90 ° come distanza dal centro e la longitudine come l'angolo dall'asse x.

Se stai lavorando in tutto il mondo, puoi trasformare lat / lon in un punto su una sfera di unità 3D, quindi prendere la distanza euclidea tra di loro. La lunghezza dell'accordo tra i 2 punti. (2 sin e cos per ogni coordinata (precalcolata), più una radice quadrata). Questo è tuttavia mal condizionato quando i punti sono vicini. Un'altra opzione invece della distanza euclidea è ottenere il prodotto punto tra di loro e trovare gli aco di esso. Ciò determinerà l'angolo tra i punti.