Учебники

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

Сентябрь 28, 2018

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

  • Разделяй и властвуй
  • Поиск в глубину
  • Поиск в ширину
  • Best-First Search

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

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

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

  • Разделить — исходная проблема делится на подзадачи.

  • Завоевать — Подзадачи решаются рекурсивно.

  • Объединить — Решения подзадач объединяются, чтобы получить решение исходной проблемы.

Разделить — исходная проблема делится на подзадачи.

Завоевать — Подзадачи решаются рекурсивно.

Объединить — Решения подзадач объединяются, чтобы получить решение исходной проблемы.

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

ПСЕВДОКОД 

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), который ранее не посещался, и отметьте его как посещенный.

  • Посетите первый соседний узел-преемник и отметьте его как посещенный.

  • Если все последующие узлы рассматриваемого узла уже посещены или у него больше нет преемного узла, вернитесь к его родительскому узлу.

Рассмотрим узел (root), который ранее не посещался, и отметьте его как посещенный.

Посетите первый соседний узел-преемник и отметьте его как посещенный.

Если все последующие узлы рассматриваемого узла уже посещены или у него больше нет преемного узла, вернитесь к его родительскому узлу.

ПСЕВДОКОД

Пусть v будет вершина, с которой начинается поиск в графе 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) — это алгоритм поиска в дереве или структуре данных неориентированного графа. Здесь мы начинаем с узла, а затем посещаем все смежные узлы на одном уровне, а затем переходим на соседний узел-преемник на следующем уровне. Это также называется поиском по уровням .

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

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

ПСЕВДОКОД

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

Best-First Search

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

58
Share: