Algoritmo de búsqueda en paralelo
La búsqueda es una de las operaciones fundamentales en informática. Se usa en todas las aplicaciones donde necesitamos encontrar si un elemento está en la lista dada o no. En este capítulo, discutiremos los siguientes algoritmos de búsqueda:
- Divide y conquistaras
- Búsqueda en profundidad
- Búsqueda primero en amplitud
- Mejor búsqueda primero
Divide y conquistaras
En el enfoque de divide y vencerás, el problema se divide en varios subproblemas pequeños. Luego, los subproblemas se resuelven de forma recursiva y se combinan para obtener la solución del problema original.
El enfoque de divide y vencerás implica los siguientes pasos en cada nivel:
Divide - El problema original se divide en subproblemas.
Conquer - Los subproblemas se resuelven de forma recursiva.
Combine - Las soluciones de los subproblemas se combinan para obtener la solución del problema original.
La búsqueda binaria es un ejemplo de algoritmo de divide y vencerás.
Pseudocódigo
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)Búsqueda en profundidad
La búsqueda en profundidad primero (o DFS) es un algoritmo para buscar un árbol o una estructura de datos de gráfico no dirigido. Aquí, el concepto es comenzar desde el nodo inicial conocido como elrooty atravesar lo más lejos posible en el mismo ramal. Si obtenemos un nodo sin nodo sucesor, regresamos y continuamos con el vértice, que aún no se ha visitado.
Pasos de la búsqueda en profundidad
Considere un nodo (raíz) que no se visitó anteriormente y márquelo como visitado.
Visite el primer nodo sucesor adyacente y márquelo como visitado.
Si todos los nodos sucesores del nodo considerado ya se han visitado o no tiene más nodos sucesores, regrese a su nodo padre.
Pseudocódigo
Dejar v ser el vértice donde comienza la búsqueda en 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()Búsqueda primero en amplitud
Breadth-First Search (o BFS) es un algoritmo para buscar un árbol o una estructura de datos de gráficos no dirigida. Aquí, comenzamos con un nodo y luego visitamos todos los nodos adyacentes en el mismo nivel y luego pasamos al nodo sucesor adyacente en el siguiente nivel. Esto también se conoce comolevel-by-level search.
Pasos de la búsqueda primero en amplitud
- Comience con el nodo raíz, márquelo como visitado.
- Como el nodo raíz no tiene ningún nodo en el mismo nivel, pase al siguiente nivel.
- Visite todos los nodos adyacentes y márquelos como visitados.
- Vaya al siguiente nivel y visite todos los nodos adyacentes no visitados.
- Continúe este proceso hasta que se visiten todos los nodos.
Pseudocódigo
Dejar v ser el vértice donde comienza la búsqueda en 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()Mejor búsqueda primero
Best-First Search es un algoritmo que atraviesa un gráfico para alcanzar un objetivo en la ruta más corta posible. A diferencia de BFS y DFS, Best-First Search sigue una función de evaluación para determinar qué nodo es el más apropiado para atravesar a continuación.
Pasos de la búsqueda "Mejor primero"
- Comience con el nodo raíz, márquelo como visitado.
- Busque el siguiente nodo apropiado y márquelo como visitado.
- Vaya al siguiente nivel y busque el nodo apropiado y márquelo como visitado.
- Continúe este proceso hasta alcanzar el objetivo.
Pseudocódigo
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