La domanda / i nucleo / i comune / i più corta

Question

La domanda / i nucleo / i comune / i più corta

#1 da (1 voti)
#2 da (0 voti)

-2

Non sono sicuro se sto usando la terminologia corretta qui. Sto cercando di trovare un algoritmo che consenta di trovare un vertice in un grafo arbitrario in modo che il vertice abbia una distanza minima dai vertici più lontani.

Inoltre, sto anche cercando di trovare un algoritmo che consenta di trovare 2 vertici invece di uno, riducendo di nuovo la distanza dai vertici più lontani a uno di questi due vertici.

La mia intuizione dice che dovrei trovare un algoritmo che calcoli i percorsi più brevi tra tutti i vertici nel grafico, e guardare i percorsi, e trovare i vertici con il traffico più alto. Ma ho difficoltà a venire con un algoritmo concreto poiché non ho alcuna esperienza precedente con questo. Ho provato a google questo problema, senza successo. Qualsiasi consiglio sarebbe molto apprezzato.

algorithms graph

posta Aisha Ashwal 01.11.2016 - 03:52

fonte

2 risposte

1

Devi davvero valutare cosa stai provando a modellare nel tuo algoritmo. Quali sono gli input per l'algoritmo e quali sono i possibili output. Ti suggerisco di iniziare leggendo la matematica dei Grafici. In un grafico, un vertice "più lontano" è un termine molto soggettivo e dipende in realtà da un determinato 0,0 scelto o dal vertice "indice" o "corrente".

Inizia imparando le basi dei grafici qui (trova e fai clic su una qualsiasi delle lezioni note intitolate 'grafici')

(La teoria di cui sopra è ovviamente solo la mia opinione e puoi scegliere di apprendere i grafici da qualsiasi luogo)

Gli algoritmi più importanti per "trovare i percorsi più brevi" sono:

L'algoritmo di Dijkstra risolve il problema del percorso più breve a sorgente singola.
L'algoritmo di Bellman-Ford risolve il problema della sorgente singola se marginale i pesi potrebbero essere negativi.
Un algoritmo di ricerca * risolve il percorso più breve con una coppia singola utilizzando euristica per cercare di accelerare la ricerca.
L'algoritmo di Floyd-Warshall risolve tutte le coppie di percorsi più brevi.
L'algoritmo di Johnson risolve tutti i percorsi a coppie più brevi e potrebbe esserlo più veloce di Floyd-Warshall su grafici sparsi.
L'algoritmo di Viterbi risolve il problema del percorso stocastico più breve con un peso probabilistico aggiuntivo su ciascun nodo.

Uno studio più completo può essere trovato nella pagina di Wikipedia

risposta data 01.11.2016 - 05:55

fonte

Leggi altre domande sui tag algorithms graph

Architettura - Libreria di modellazione 3D Come gestire un caso TODO non utilizzabile in uno script?

score 0 · Accepted Answer

Dopo un po 'di lettura ecco cosa mi è venuto in mente:

Per ridurre al minimo la distanza dai vertici più lontani, dobbiamo prima trovare i vertici più lontani. Quindi il primo passo è generare un algoritmo che trovi il percorso più breve tra due vertici.
Quindi eseguiamo quell'algoritmo attraverso tutti i vertici e registriamo solo il più lungo di quei percorsi più brevi.

L'algoritmo per trovare il percorso più breve per un grafo ponderato e non orientato, che è quello che ho nel mio problema, è l'algoritmo di Dijkstra, ma registriamo solo la distanza per i due vertici più lontani. Per visualizzare questo, per qualsiasi vertice v in un grafico G = (V, E), dove V = {v1..vn}, registriamo distancev = max {distanza (v, v1), distanza (v, v2) ... distanza (v, vn)}, dove distanza è definita come la distanza più breve tra due vertici.

Una volta raccolte tutte le distanze ai vertici più lontani, ordiniamo i risultati per trovare il minimo. Questa sarà la risposta.