Алгоритм параллельного поиска

Поиск - одна из фундаментальных операций в информатике. Он используется во всех приложениях, где нам нужно определить, находится ли элемент в данном списке или нет. В этой главе мы обсудим следующие алгоритмы поиска -

Разделяй и властвуй
Поиск в глубину
Поиск в ширину
Поиск лучшего первого

Разделяй и властвуй

В подходе «разделяй и властвуй» проблема делится на несколько небольших подзадач. Затем подзадачи рекурсивно решаются и объединяются, чтобы получить решение исходной проблемы.

Подход «разделяй и властвуй» включает следующие шаги на каждом уровне:

Divide - Исходная проблема разделена на подзадачи.
Conquer - Подзадачи решаются рекурсивно.
Combine - Решения подзадач объединяются, чтобы получить решение исходной проблемы.

Бинарный поиск - это пример алгоритма «разделяй и властвуй».

Псевдокод

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)

Поиск в глубину

Поиск в глубину (или DFS) - это алгоритм поиска в дереве или структуре данных неориентированного графа. Здесь концепция состоит в том, чтобы начать с начального узла, известного какrootи пройти как можно дальше в той же ветви. Если мы получаем узел без узла-преемника, мы возвращаемся и продолжаем работу с вершиной, которую еще предстоит посетить.

Шаги поиска в глубину

Рассмотрим узел (корень), который ранее не посещался, и отметим его посещенным.
Посетите первый соседний узел-преемник и отметьте его посещенным.
Если все узлы-преемники рассматриваемого узла уже посещены или у него больше нет узла-преемника, вернитесь к его родительскому узлу.

Псевдокод

Позволять v - вершина, с которой начинается поиск в 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()

Поиск в ширину

Поиск в ширину (или BFS) - это алгоритм поиска в дереве или структуре данных неориентированного графа. Здесь мы начинаем с узла, затем посещаем все соседние узлы на том же уровне, а затем переходим к соседнему узлу-преемнику на следующем уровне. Это также известно какlevel-by-level search.

Шаги поиска в ширину

Начните с корневого узла, отметьте его посещенным.
Поскольку корневой узел не имеет узла на том же уровне, перейдите на следующий уровень.
Посетите все соседние узлы и отметьте их посещенными.
Перейдите на следующий уровень и посетите все непосещенные соседние узлы.
Продолжайте этот процесс, пока не будут посещены все узлы.

Псевдокод

Позволять v - вершина, с которой начинается поиск в 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()

Поиск лучшего первого

Поиск лучшего первого - это алгоритм, который просматривает граф, чтобы достичь цели по кратчайшему пути. В отличие от BFS и DFS, поиск Best-First следует функции оценки, чтобы определить, какой узел наиболее подходит для следующего перехода.

Шаги поиска лучшего первого

Начните с корневого узла, отметьте его посещенным.
Найдите следующий подходящий узел и отметьте его посещенным.
Перейдите на следующий уровень, найдите соответствующий узел и отметьте его посещенным.
Продолжайте этот процесс, пока цель не будет достигнута.

Псевдокод

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