Algoritmo de pesquisa paralela
Pesquisar é uma das operações fundamentais da ciência da computação. Ele é usado em todos os aplicativos onde precisamos descobrir se um elemento está na lista fornecida ou não. Neste capítulo, discutiremos os seguintes algoritmos de pesquisa -
- Dividir e conquistar
- Pesquisa em profundidade
- Pesquisa em amplitude
- Melhor primeira pesquisa
Dividir e conquistar
Na abordagem dividir para conquistar, o problema é dividido em vários pequenos subproblemas. Em seguida, os subproblemas são resolvidos recursivamente e combinados para obter a solução do problema original.
A abordagem de dividir para conquistar envolve as seguintes etapas em cada nível -
Divide - O problema original está dividido em subproblemas.
Conquer - Os subproblemas são resolvidos recursivamente.
Combine - As soluções dos subproblemas são combinadas para obter a solução do problema original.
A pesquisa binária é um exemplo de algoritmo de divisão e conquista.
Pseudo-có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)Pesquisa em profundidade
Pesquisa em profundidade (ou DFS) é um algoritmo para pesquisar uma árvore ou uma estrutura de dados de gráfico não direcionado. Aqui, o conceito é começar do nó inicial conhecido como oroote atravesse o mais longe possível no mesmo galho. Se obtivermos um nó sem nó sucessor, retornamos e continuamos com o vértice, que ainda não foi visitado.
Etapas da pesquisa em profundidade
Considere um nó (raiz) que não foi visitado anteriormente e marque-o como visitado.
Visite o primeiro nó sucessor adjacente e marque-o como visitado.
Se todos os nós sucessores do nó considerado já foram visitados ou se não houver mais nenhum nó sucessor, retorne ao seu nó pai.
Pseudo-código
Deixei v ser o vértice onde a pesquisa começa no gráfico 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()Pesquisa em amplitude
Pesquisa em amplitude (ou BFS) é um algoritmo para pesquisar uma árvore ou uma estrutura de dados de gráfico não direcionado. Aqui, começamos com um nó e, em seguida, visitamos todos os nós adjacentes no mesmo nível e, em seguida, passamos para o nó sucessor adjacente no próximo nível. Isso também é conhecido comolevel-by-level search.
Etapas da pesquisa ampla primeiro
- Comece com o nó raiz, marque-o como visitado.
- Como o nó raiz não possui nenhum nó no mesmo nível, vá para o próximo nível.
- Visite todos os nós adjacentes e marque-os como visitados.
- Vá para o próximo nível e visite todos os nós adjacentes não visitados.
- Continue este processo até que todos os nós sejam visitados.
Pseudo-código
Deixei v ser o vértice onde a pesquisa começa no gráfico 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()Melhor primeira pesquisa
Best-First Search é um algoritmo que percorre um gráfico para alcançar um alvo no caminho mais curto possível. Ao contrário do BFS e do DFS, Best-First Search segue uma função de avaliação para determinar qual nó é o mais apropriado para atravessar a seguir.
Etapas da melhor pesquisa
- Comece com o nó raiz, marque-o como visitado.
- Encontre o próximo nó apropriado e marque-o como visitado.
- Vá para o próximo nível, encontre o nó apropriado e marque-o como visitado.
- Continue este processo até que a meta seja alcançada.
Pseudo-có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