Двунаправленный поиск

Двунаправленный поиск

Двунаправленный поиск пути[1][2] в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа.

Содержание

Идея

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

Преимущества и недостатки

  • Повышенное быстродействие;
  • Нужна память для хранения дерева поиска для того, чтобы можно было выполнить проверку принадлежности листа другому дереву.

Оценка сложности исполнения

Сложность всего алгоритма оценивается как сумма сложности прямого и обратных поисков, проверки принадлежности, равной одной операции, постоянному времени (O(n)), обращению к хэш-таблице.

Подсчёт количества операций

Слишком зависит от конкретной ситуации, если поиск осуществляется не по n-арному дереву.

Асимптотическая сложность возрастания количества операций

  • Если известны единственные конкретные начальный и целевой элементы, то временная асимптотическая сложность прямого и обратного поисков равна O(b^{d/2}), следовательно общая — O(b^{d/2}) + O(b^{d/2}), что гораздо меньше чем O(b^{d}). Пространственная асимптотическая сложность O(b^{d/2}), вместо — O(1) у прямого, так как нужно хранить в памяти.
  • Если известны конкретный начальный элемент и набор элементов, из которого один — целевой.

Статистическая оценка

Двунаправленный поиск, при заданных единственных начального и конечного элементах, может улучшить однонаправленный поиск в ширину, обычно, в 2 раза. Наиболее сложным случаем для двунаправленного поиска является такая задача, в котором для проверки цели дано только неявное описание некоторого (возможно очень большого) множества целевых состояний, например всех состояний, соответствующих проверки цели "Мат" в шахматах. При обратном поиске потребовалось бы создать компактные описания всех состояний, которые позволяют поставить мат с помощью ходов q1, q2, q3 ... и т.д. ; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует.

Алгоритм двунаправленного поиска

Алгоритм состоит:

  • прямого поиска, аналогичного одиночному поиску;
  • обратного поиска;
  • операции определения принадлежности листа другому дереву поиска.

Сложность реализации

Сложность реализации заключается в алгоритме обратного поиска.

Примеры реализации

Практическое применение

См. также

Примечания

  1. Другое: двунаправленный поиск элемента — осуществляется в двунаправленных или кольцевых списках от искомого элемента в обе стороны.
  2. [1] Этот алгоритм является полным и оптимальным (при единообразных стоимостях этапов), если оба процесса поиска осуществляются в ширину; другие сочетания методов могут характеризоваться отсутствием полноты, оптимальности или того и другого.

Ссылки

Литература

  • Стюарт Рассел & Питер Норвиг Часть 2. Решение проблем // Искусственный интеллект (Современный подход) = Artificial Intelligence (A Modern Approach). — 2-е изд. — ФГУП. "Печатный двор" им. А.М.Горького: Вильямс, 2006. — С. 135-136. — ISBN 5-8459-0887-6



Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Двунаправленный поиск" в других словарях:

  • Поиск в ширину — Порядок обхода дерева в ширину Поиск в ширину (BFS, Breadth first search)  метод обхода и разметки вершин графа. Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам  метка 1.… …   Википедия

  • Поиск в глубину — Порядок обхода дерева в глубину Поиск в глубину (англ. Depth first search, DFS)  один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные… …   Википедия

  • Поиск по первому наилучшему совпадению — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… …   Википедия

  • Алгоритм поиска A* — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… …   Википедия

  • А* — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Поиск A* (произносится «А звездочка») в информатике и математике, алгоритм …   Википедия

  • Алгоритм Дейкстры — Блок схема алгоритма Дейкстры. Алгоритмы поиска на гр …   Википедия

  • Алгоритм Левита — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла… …   Википедия

  • Shortest Path First — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Дейкстры алгоритм на графах, изобретенный Э. Дейкстрой. Находит… …   Википедия

  • Алгоритм Джонсона — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла… …   Википедия

  • Дейкстры алгоритм — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Дейкстры алгоритм на графах, изобретенный Э. Дейкстрой. Находит… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»