Algoritmo a due centri per trovare il minimo del punto più lontano

Question

Algoritmo a due centri per trovare il minimo del punto più lontano

#1 da (0 voti)

0

Sto cercando di trovare un algoritmo che mi permetta di trovare due vertici in un grafo orientato e ponderato che minimizza la distanza dal punto più lontano.

La distanza del punto più lontano è fondamentalmente la distanza tra due vertici (u, v) nel grafico tale che la distanza (u, v) > = distanza (x, y) per qualsiasi altro due vertice nello stesso grafico.

So come risolvere questo problema per 1 centro (ovvero un vertice che riduce al minimo la distanza dal punto più lontano). Ho anche letto l'algoritmo K-center che mi consente di trovare più centri. Ma ho letto che l'algoritmo K-center non funziona quando k = 2. Quindi qualcuno può dirmi che cosa dovrei fare esattamente per trovare 2 centri?

Qualsiasi aiuto sarebbe molto apprezzato. Grazie!

algorithms graph

posta Aisha Ashwal 01.11.2016 - 22:35

fonte

1 risposta

Leggi altre domande sui tag algorithms graph

Modo corretto per la ricerca geografica Confronto tra MSVC e Mingw

score 0 · Accepted Answer

Il mio algoritmo utilizza il metodo Brute Force.
Per ciascuna coppia di vertici (u, v) in G, calcolo la distanza più lontana da te v verso tutti gli altri vertici. Quindi trovo semplicemente il minimo.

Ad esempio, in un grafico G costituito dai vertici A, B, C, D, E.. . Seleziono arbitrariamente (A, B) per essere la prima coppia possibile. Calcolo la distanza (A, B) da C. Diciamo che la distanza di A da C è 4. La distanza di B da C è 14. Quindi seleziono 4 come distanza da C a (A, B) perché stiamo cercando il minimo .

Eseguo questa selezione per i vertici D, E, F ... Ogni vertice produrrà una distanza da (A, B). Di quelle distanze, seleziono il massimo. Questa sarà la distanza più lontana tra tutte le località in G (A, B).

Quindi eseguo questa selezione per tutte le possibili coppie di posizioni, quindi eseguirò questa selezione per (A, C), (A, D), (B, C), (B, D) e così via. < br> Una volta che ho generato una distanza dal punto più lontano (o vertice) per tutte le coppie di vertici, seleziono semplicemente la coppia che produce la distanza più piccola.