Algoritmo di ricerca parallela
La ricerca è una delle operazioni fondamentali nell'informatica. Viene utilizzato in tutte le applicazioni in cui è necessario verificare se un elemento è nell'elenco fornito o meno. In questo capitolo, discuteremo i seguenti algoritmi di ricerca:
- Dividere e conquistare
- Ricerca in profondità
- Ricerca in ampiezza
- Migliore prima ricerca
Dividere e conquistare
Nell'approccio divide et impera, il problema è suddiviso in diversi piccoli problemi secondari. Quindi i sottoproblemi vengono risolti ricorsivamente e combinati per ottenere la soluzione del problema originale.
L'approccio divide et impera prevede i seguenti passaggi ad ogni livello:
Divide - Il problema originale è suddiviso in sottoproblemi.
Conquer - I problemi secondari vengono risolti in modo ricorsivo.
Combine - Le soluzioni dei sottoproblemi vengono combinate per ottenere la soluzione del problema originale.
La ricerca binaria è un esempio di algoritmo divide et impera.
Pseudocodice
Binarysearch(a, b, low, high)
if low < high then
return NOT FOUND
else
mid ← (low+high) / 2
if b = key(mid) then
return key(mid)
else if b < key(mid) then
return BinarySearch(a, b, low, mid−1)
else
return BinarySearch(a, b, mid+1, high)
Ricerca in profondità
Depth-First Search (o DFS) è un algoritmo per la ricerca in un albero o in una struttura di dati del grafico non orientata. In questo caso, il concetto è di iniziare dal nodo di partenza noto comeroote traversa il più possibile nello stesso ramo. Se otteniamo un nodo senza nodo successore, torniamo e continuiamo con il vertice, che deve ancora essere visitato.
Fasi della ricerca in profondità
Considera un nodo (root) che non è stato visitato in precedenza e contrassegnalo come visitato.
Visita il primo nodo successore adiacente e contrassegnalo come visitato.
Se tutti i nodi successori del nodo considerato sono già visitati o non ha più nodi successori, torna al suo nodo padre.
Pseudocodice
Permettere v essere il vertice in cui inizia la ricerca in Graph G.
DFS(G,v)
Stack S := {};
for each vertex u, set visited[u] := false;
push S, v;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbour w of u
push S, w;
end if
end while
END DFS()
Ricerca in ampiezza
Breadth-First Search (o BFS) è un algoritmo per la ricerca in un albero o in una struttura di dati del grafico non orientata. Qui, iniziamo con un nodo e quindi visitiamo tutti i nodi adiacenti nello stesso livello e poi ci spostiamo al nodo successore adiacente nel livello successivo. Questo è anche noto comelevel-by-level search.
Passi della ricerca in larghezza
- Inizia con il nodo radice, contrassegnalo come visitato.
- Poiché il nodo radice non ha alcun nodo allo stesso livello, passare al livello successivo.
- Visita tutti i nodi adiacenti e contrassegnali come visitati.
- Vai al livello successivo e visita tutti i nodi adiacenti non visitati.
- Continua questo processo fino a quando tutti i nodi non sono stati visitati.
Pseudocodice
Permettere v essere il vertice in cui inizia la ricerca in Graph G.
BFS(G,v)
Queue Q := {};
for each vertex u, set visited[u] := false;
insert Q, v;
while (Q is not empty) do
u := delete Q;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbor w of u
insert Q, w;
end if
end while
END BFS()
Migliore prima ricerca
Best-First Search è un algoritmo che attraversa un grafico per raggiungere un obiettivo nel percorso più breve possibile. A differenza di BFS e DFS, Best-First Search segue una funzione di valutazione per determinare quale nodo è il più appropriato da attraversare successivamente.
Passaggi della ricerca Best-First
- Inizia con il nodo radice, contrassegnalo come visitato.
- Trova il successivo nodo appropriato e contrassegnalo come visitato.
- Vai al livello successivo e trova il nodo appropriato e contrassegnalo come visitato.
- Continua questo processo fino a raggiungere l'obiettivo.
Pseudocodice
BFS( m )
Insert( m.StartNode )
Until PriorityQueue is empty
c ← PriorityQueue.DeleteMin
If c is the goal
Exit
Else
Foreach neighbor n of c
If n "Unvisited"
Mark n "Visited"
Insert( n )
Mark c "Examined"
End procedure