Trova n nodi più lontani l'uno dall'altro

Question

Trova n nodi più lontani l'uno dall'altro

#1 da (1 voti)

3

Sto cercando un algoritmo che mi dia gli n nodi più distanti l'uno dall'altro.

Questo può essere ottenuto in modo relativamente efficiente?

Per chiarire la mia domanda: Penso al problema come a una variante del contrario del problema del commesso viaggiatore. Abbiamo questo grafico:

La matrice di distanza ha il seguente aspetto:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

Ad esempio, il venditore deve visitare i 4 nodi mostrati sopra. Deve essere sulla strada tra tutti i nodi che visita il più a lungo possibile. Quali nodi visiterebbe?

La mia ipotesi è che stiamo cercando i 4 nodi con la massima distanza media tra loro. Esiste un modo ragionevolmente efficiente, preferibilmente non esponenziale, per farlo? Cosa succede se non ho bisogno di una soluzione esatta al problema?

algorithms graph

posta Sundae 02.10.2014 - 23:15

fonte

1 risposta

Leggi altre domande sui tag algorithms graph

Decidere il modo migliore di modellare un periodo di applicazione o un periodo di tempo per un programma Strutturare il repository git come un "catch-all"

score 1 · Accepted Answer

Per trovare le quattro distanze più lunghe, devi cercare su tutte le distanze. Quindi per n nodi, è necessario eseguire il ciclo di n ^ 2 distanze, e quindi qualcosa del tipo:

if dist > smallest_max
  replace smallest max in array of four maximums with dist
  recalculate the smallest max from array

Questo è O (n ^ 2), che non è buono ma non esponenziale come venditore ambulante.