Migliore e più semplice algoritmo per la ricerca di un vertice su un grafico?

Question

Dopo aver implementato la maggior parte delle funzioni comuni e necessari per la mia realizzazione Grafico, mi sono reso conto che un paio di funzioni (rimuovere vertici, ricerca vertice e ottenere vertice) non hanno il "migliore" implementazione.

Sto usando liste di adiacenza con liste collegate per la mia realizzazione dei grafici e stavo cercando un vertice dopo l'altro fino a trovare quello che voglio. Come ho detto, ho capito che non stavo usando l'attuazione "migliore". Posso avere 10000 vertici e la necessità di cercare l'ultimo, ma quel vertice potuto avere un collegamento alla prima, che sarebbe accelerare notevolmente le cose. Ma questo è solo un caso ipotetico, si può o non può accadere.

Quindi, l'algoritmo mi consigliate per la ricerca di ricerca? I nostri insegnanti hanno parlato in ampiezza e profondità, prima per lo più (e l'algoritmo Dikjstra', ma questo è un argomento completamente diverso). Tra quei due, quale mi consigliate?

Sarebbe perfetto se potessi realizzare entrambi, ma non ho tempo per questo, ho bisogno di prendere uno e mettere in atto ha la prima fase scadenza si avvicina ...

La mia ipotesi, è di andare con profondità prima, sembra più facile da implementare e guardando il loro modo di lavorare, mi sembra una soluzione migliore. Ma che in realtà dipende l'ingresso.

Ma ciò che voi ragazzi suggeriscono?

Answer 1

Se hai un lista di adiacenza, alla ricerca di un vertice significa semplicemente attraversare quella lista. Si potrebbe forse anche ordinare la lista di diminuire le operazioni di ricerca necessari.

A attraversamento grafico (come DFS o BFS) non migliorerà questo da un punto di vista delle prestazioni.

Answer 2

trovare ed eliminare i nodi di un grafo è un non problema "cercare" un problema grafico, in modo da rendere meglio di O (n) = ricerca lineare, BFS, DFS, è necessario memorizzare i nodi in una diversa struttura di dati ottimizzato per la ricerca o ordinarli. Questo vi dà O (log n) per trovare ed eliminare le operazioni. Candidatas sono strutture ad albero come b-alberi o tabelle hash. Se si vuole codificare la roba da soli vorrei andare per una tabella di hash che dà normalmente ottime prestazioni ed è ragionevolmente facile da implementare.

Answer 3

Credo che BFS di solito è più veloce in media. Leggere le pagine wiki per DFS e BFS .

Il motivo dico BFS è più veloce è perché ha la proprietà di nodi che raggiungono in ordine di distanza dal nodo di partenza. Così, se il grafico ha nodi N e si desidera cercare per il nodo e il nodo N 1, che è il nodo si avvia il modulo di ricerca, è legata alla N, allora troverete subito. DFS può espandere l'intero grafico prima che questo accada tuttavia. DFS sarà solo più veloce se si è fortunati, mentre BFS sarà più veloce se i nodi si cerca sono vicino al vostro nodo di partenza. In breve, entrambi dipendono l'ingresso, ma avrei scelto BFS.

DFS è anche più difficile da codice senza ricorsione, il che rende BFS un po 'più veloce, in pratica, dal momento che è un algoritmo iterativo.

Se si riesce a normalizzare i nodi (loro numero da 1 a 10 000 e accedervi da un numero), allora si può facilmente tenere Exists[i] = true if node i is in the graph and false otherwise, dando O (1) ricerca del tempo. In caso contrario, è consigliabile utilizzare un se la normalizzazione non è possibile o non si vuole fare esso.

Answer 4

Ricerca profondità prima è migliore perché

1. Si utilizza molta meno memoria
2. più facile da implementare

Answer 5

la profondità e l'ampiezza primo primi algoritmi sono quasi identici, tranne per l'utilizzo di una pila a uno (DFS), una coda nell'altro (BFS), e alcune variabili membro necessaria. entrambi di applicazione non si dovrebbe prendere tempo molto più.

Inoltre, se si dispone di una lista di adiacenza dei vertici poi il tuo look con O (V) comunque. Quindi, poco o niente sarà guadagnato via utilizzando una delle altre due ricerche.

Answer 6

Mi piacerebbe commento sul post di Konrad, ma non posso commentare eppure così ... mi piacerebbe secondo che non fa la differenza in termini di prestazioni, se si sceglie di implementare DFS o BFS sopra una semplice ricerca lineare attraverso il vostro elenco. La ricerca di un particolare nodo del grafo non dipende dalla struttura del grafico, quindi non è necessario limitare se stessi ad algoritmi grafico. In termini di tempo di codifica, la ricerca lineare è la scelta migliore; se si vuole rispolverare le tue abilità in algoritmi per grafi, implementare DFS o BFS, a seconda di quale si sente come.

Answer 7

Se siete alla ricerca di un vertice specifico e che termina quando a trovarlo, mi consiglia di utilizzare A * , che è un best-prima ricerca.

L'idea è che si calcola la distanza dal vertice sorgente al vertice corrente si sta elaborando, e quindi "indovinare" la distanza dal vertice corrente verso il bersaglio.

Si avvia alla fonte, calcolare la distanza (0) più l'ipotesi (qualunque essa sia) e aggiungerlo a una coda di priorità in cui la priorità è la distanza + indovinare. Ad ogni passo, si rimuove l'elemento con la più piccola distanza + indovinare, fare il calcolo per ogni vertice nella sua lista di adiacenza e bastone quelli nella coda di priorità. Fermarsi quando si trova il vertice di destinazione.

Se il vostro euristica (il vostro "indovinare") è ammissibile, cioè, se si tratta di sempre un sotto-stima, poi si sono garantiti per trovare il percorso più breve per raggiungere il tuo obiettivo vertice la prima volta che si visitarlo. Se il vostro euristica non è ammissibile, allora si dovrà eseguire l'algoritmo a compimento per trovare il percorso più breve (anche se suona come non si cura per il percorso più breve, solo qualsiasi percorso).

Non è molto più difficile da attuare di una ricerca in ampiezza (basta aggiungere l'euristica, in realtà) ma sarà probabilmente resa risultati più rapidi. L'unica parte difficile è capire il vostro euristica. Per i vertici che rappresentano aree geografiche, un'euristica comune è quello di utilizzare un "come-il-corvo-mosche" (linea d'aria) euristici.

Answer 8

ricerca lineare è più veloce di BFS e DFS. Ma più veloce di ricerca lineare sarebbe un * con il costo passo impostato a zero. Quando il costo passo è zero, A * aumenterà solo i nodi che sono vicini a un nodo obiettivo. Se il costo passo è zero, allora il costo cammino di ogni nodo è zero e A * non priorità nodi con un percorso più breve. Questo è ciò che si vuole dal momento che non è necessario il percorso più breve.

A * è più veloce di ricerca lineare perché ricerca lineare, molto probabilmente completa dopo O (n / 2) iterazioni (ogni nodo ha la stessa probabilità di essere un nodo di obiettivo), ma A * dà la priorità nodi che hanno una maggiore probabilità di essere un nodo obiettivo.