 | Эта статья требует дополнительных ссылок для проверки . ( октябрь 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
| Алгоритмы поиска по графам и деревьям |
|---|
| Списки |
| похожие темы |
|
В информатике , график обход (также известный как поиск графа ) относится к процессу посещения (проверки и / или обновления) каждой вершине в графе . Такие обходы классифицируются по порядку посещения вершин. Обход дерева - это частный случай обхода графа.
Избыточность [ править ]
В отличие от обхода дерева, обход графа может потребовать, чтобы некоторые вершины были посещены более одного раза, поскольку перед переходом к вершине не обязательно известно, что она уже была исследована. По мере того, как графы становятся более плотными , эта избыточность становится все более распространенной, что приводит к увеличению времени вычислений; по мере того как графики становятся более разреженными, верно и обратное.
Таким образом, обычно необходимо помнить, какие вершины уже были исследованы алгоритмом, чтобы вершины пересматривались как можно реже (или, в худшем случае, чтобы предотвратить бесконечное продолжение обхода). Это может быть выполнено путем связывания каждой вершины графа с состоянием «цвет» или «посещение» во время обхода, которое затем проверяется и обновляется, когда алгоритм посещает каждую вершину. Если вершина уже была посещена, она игнорируется и путь больше не используется; в противном случае алгоритм проверяет / обновляет вершину и продолжает движение по текущему пути.
Некоторые частные случаи графов подразумевают посещение других вершин в своей структуре и, таким образом, не требуют явной записи посещения во время обхода. Важным примером этого является дерево: во время обхода можно предположить, что все вершины-предки текущей вершины (и другие в зависимости от алгоритма) уже посещены. И поиск в графах, и в глубину, и в ширину являются адаптациями древовидных алгоритмов, отличающихся в первую очередь отсутствием структурно определенной «корневой» вершины и добавлением структуры данных для записи состояния посещения при обходе.
Алгоритмы обхода графа [ править ]
Примечание. - Если каждая вершина в графе должна быть пройдена древовидным алгоритмом (таким как DFS или BFS), то алгоритм должен быть вызван по крайней мере один раз для каждого связного компонента графа. Это легко сделать, перебирая все вершины графа, выполняя алгоритм для каждой вершины, которая еще не посещена при проверке.
Поиск в глубину [ править ]
Поиск в глубину (DFS) - это алгоритм обхода конечного графа. DFS посещает дочерние вершины перед посещением родственных вершин; то есть он проходит всю глубину любого конкретного пути, прежде чем исследовать его широту. Стек (часто стек вызовов программы через рекурсию ) обычно используется при реализации алгоритма.
Алгоритм начинается с выбранной «корневой» вершины; затем он итеративно переходит от текущей вершины к соседней, непосещенной вершине, пока не перестанет находить неисследованную вершину для перехода из ее текущего местоположения. Затем алгоритм возвращается к ранее посещенным вершинам, пока не найдет вершину, связанную с еще более неизведанной территорией. Затем он продолжит движение по новому пути, как и раньше, с обратным отслеживанием, когда он встречается с тупиками, и завершится только тогда, когда алгоритм вернется через исходную «корневую» вершину с самого первого шага.
DFS является основой для многих алгоритмов, связанных с графами, включая топологические сортировки и тестирование планарности .
Псевдокод [ править ]
- Входные данные : Граф G и вершины v из G .
- Результат : разметка ребер связного компонента v как ребер обнаружения и задних ребер.
Процедура ДФС ( G , v ) является этикетка v , как исследовал для всех ребер е в G .incidentEdges ( v ) делать , если ребро е является неисследованным , то ш ← G .adjacentVertex ( V , е ) , если вершина ш является неисследованной затем этикетка е в виде обнаруженный край рекурсивно вызвать DFS ( G , w ), иначе пометить e как задний край
Поиск в ширину [ править ]
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Октябрь 2012 г. ) |
Поиск в ширину (BFS) - это еще один метод обхода конечного графа. BFS посещает родственные вершины перед посещением дочерних вершин, а в процессе поиска используется очередь . Этот алгоритм часто используется для поиска кратчайшего пути от одной вершины к другой.
Псевдокод [ править ]
- Входные данные : Граф G и вершины v из G .
- Выход : ближайшая к v вершина, удовлетворяющая некоторым условиям, или ноль, если такой вершины не существует.
Процедура BFS ( G , v ) является создание очереди Q Епдиеие V на Q знак V , а Q не пусто делать ж ← Q .dequeue () , если вес является то , что мы ищем , то вернуть вес для всех ребер е в G .adjacentEdges ( w ) do x ← G .adjacentVertex ( w , e ) если й не отмечен , то отметьте х Епдиеий х на Q возвратного нуль
Приложения [ править ]
Поиск в ширину можно использовать для решения многих задач теории графов, например:
- поиск всех вершин в одной компоненте связности ;
- Алгоритм Чейни ;
- нахождение кратчайшего пути между двумя вершинами;
- проверка графа на двудольность ;
- Нумерация сеток алгоритма Катхилла – Макки ;
- Алгоритм Форда – Фулкерсона для вычисления максимального потока в потоковой сети ;
- сериализация / десериализация двоичного дерева по сравнению с сериализацией в отсортированном порядке (позволяет эффективно реконструировать дерево);
- алгоритмы генерации лабиринтов ;
- алгоритм заливки для маркировки смежных областей двумерного изображения или n-мерного массива;
- анализ сетей и отношений.
Исследование графа [ править ]
Задачу исследования графа можно рассматривать как вариант обхода графа. Это онлайн-проблема, означающая, что информация о графике раскрывается только во время выполнения алгоритма. Общая модель выглядит следующим образом: дан связный граф G = ( V , E ) с неотрицательными весами ребер. Алгоритм начинается с некоторой вершины и знает все исходящие ребра и вершины на концах этих ребер, но не более того. Когда посещается новая вершина, снова становятся известны все инцидентные исходящие ребра и вершины в конце. Цель - посетить все nвершины и вернуться в начальную вершину, но сумма весов тура должна быть как можно меньше. Проблему также можно понять как особую версию задачи коммивояжера , в которой продавец должен находить граф на ходу.
Для общих графов самый известный алгоритм как для неориентированных, так и для ориентированных графов - это простой жадный алгоритм :
- В неориентированном случае жадный тур не более чем в O (ln n ) раз длиннее оптимального маршрута. [1] Лучшая нижняя граница, известная для любого детерминированного онлайн-алгоритма, равна 2,5 - ε ; [2]
- В управляемом случае жадный тур не более чем в ( n - 1 ) раз длиннее оптимального тура. Это соответствует нижней границе n - 1 . [3] Аналогичная конкурентная нижняя граница Ω ( n ) также верна для рандомизированных алгоритмов, которые знают координаты каждого узла в геометрическом вложении. Если вместо посещения всех узлов только один узел «клад» должен быть найден, конкурентные оценки являются thetas ; ( п 2 ) на единицу веса ориентированных графов, как для детерминированных и рандомизированных алгоритмов.
Универсальные последовательности обхода [ править ]
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Декабрь 2016 г. ) |
Универсальная последовательность обхода представляет собой последовательность инструкций , содержащих обход графа для любого регулярного графа с установленным числом вершин и для любой начальной вершины. Вероятностное доказательство было использовано Aleliunas et al. показать, что существует универсальная последовательность обхода с числом инструкций, пропорциональным O ( n 5 ) для любого регулярного графа с n вершинами. [4] Шаги, указанные в последовательности, относятся к текущему узлу, а не абсолютны. Например, если текущий узел v j , а v j имеет dсоседи, то последовательность обхода укажет следующий узел для посещения, v j +1 , в качестве i- го соседа v j , где 1 ≤ i ≤ d .
Ссылки [ править ]
- ^ Розенкранц, Дэниел Дж .; Стернс, Ричард Э .; Льюис, II, Филип М. (1977). «Анализ нескольких эвристик для задачи коммивояжера». SIAM Journal on Computing . 6 (3): 563–581. DOI : 10.1137 / 0206041 .
- ^ Добрев, Стефан; Кралович, Растислав; Марку, Еврипид (2012). «Исследование графов онлайн с советом». Proc. 19-го Международного коллоквиума по структурной информационной и коммуникационной сложности (SIROCCO) . Конспект лекций по информатике. 7355 : 267–278. DOI : 10.1007 / 978-3-642-31104-8_23 . ISBN 978-3-642-31103-1.
- ^ Ферстер, Клаус-Тихо; Ваттенхофер, Роджер (декабрь 2016 г.). «Нижняя и верхняя конкурентные границы для исследования ориентированного графа онлайн» . Теоретическая информатика . 655 : 15–29. DOI : 10.1016 / j.tcs.2015.11.017 .
- ^ Aleliunas, R .; Karp, R .; Lipton, R .; Lovász, L .; Ракофф, К. (1979). «Случайные блуждания, универсальные последовательности обходов и сложность задач лабиринта». 20-й ежегодный симпозиум по основам информатики (SFCS 1979) : 218–223. DOI : 10,1109 / SFCS.1979.34 .
См. Также [ править ]
- Обход графа внешней памяти
