В чем разница между поиском по графу и поиском по дереву?

99

В чем разница между поиском по графу и версиями поиска по дереву относительно поиска DFS, A * в искусственном интеллекте ?

Райханур Рахман
источник

Ответы:

179

Судя по существующим ответам, эта концепция вызывает большую путаницу.

Проблема всегда в графике

Различие между поиском по дереву и поиском по графу не связано с тем, является ли проблемный граф деревом или общим графом. Всегда предполагается, что вы имеете дело с общим графиком. Различие заключается в шаблоне обхода, который используется для поиска по графу, который может иметь форму графа или дерева.

Если вы имеете дело с проблемой в форме дерева , оба варианта алгоритма приводят к одинаковым результатам. Таким образом, вы можете выбрать более простой вариант поиска по дереву.

Разница между поиском по диаграмме и дереву

Ваш основной алгоритм поиска по графу выглядит примерно так. С начальным узлом start, ориентированные ребра как successorsи goalспецификация, используемая в условии цикла. openхранит в памяти узлы, которые в настоящее время рассматриваются, в открытом списке . Обратите внимание, что следующий псевдокод верен не во всех аспектах (2).

Поиск по дереву

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

В зависимости от того, как вы реализуете select from open, вы получаете различные варианты алгоритмов поиска, такие как поиск в глубину (DFS) (выбор новейшего элемента), поиск в ширину (BFS) (выбор самого старого элемента) или поиск по единой стоимости (выбор элемента с наименьшей стоимостью пути ), популярный поиск A-star путем выбора узла с наименьшей стоимостью плюс эвристическое значение и т. д.

Изложенный выше алгоритм фактически называется поиском по дереву . Он будет посещать состояние основного графа проблемы несколько раз, если к нему есть несколько направленных путей, укорененных в начальном состоянии. Можно даже посещать состояние бесконечное количество раз, если оно находится в направленном цикле. Но каждое посещение соответствует отдельному узлу в дереве, созданном нашим алгоритмом поиска. Эта очевидная неэффективность иногда требуется, как будет объяснено позже.

Поиск граф

Как мы видели, поиск по дереву может посещать состояние несколько раз. И поэтому он будет исследовать «поддерево», найденное после этого состояния, несколько раз, что может быть дорогостоящим. Поиск по графику исправляет это, отслеживая все посещенные состояния в закрытом списке . Если только что найденный преемник nextуже известен, он не будет вставлен в открытый список:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Сравнение

Мы заметили, что поиск по графу требует больше памяти, так как он отслеживает все посещенные состояния. Это может быть компенсировано меньшим размером открытого списка, что приводит к повышению эффективности поиска.

Оптимальные решения

Некоторые методы реализации selectмогут гарантировать получение оптимальных решений - т.е. кратчайшего пути или пути с минимальными затратами (для графов с затратами, прикрепленными к ребрам). Это в основном выполняется всякий раз, когда узлы расширяются в порядке увеличения стоимости или когда стоимость является ненулевой положительной константой. Распространенным алгоритмом, реализующим этот тип выбора, является поиск по единообразной стоимости или, если стоимость шагов идентична, BFS или IDDFS . IDDFS позволяет избежать агрессивного потребления памяти BFS и обычно рекомендуется для неинформированного поиска (также известного как грубая сила), когда размер шага постоянен.

А *

Также (очень популярный) алгоритм поиска по дереву A * обеспечивает оптимальное решение при использовании с допустимой эвристикой . Однако алгоритм поиска по графу A * дает эту гарантию только тогда, когда он используется с последовательной (или «монотонной») эвристикой (более сильное условие, чем допустимость).

(2) Недостатки псевдокода

Для простоты представленный код не:

  • обрабатывать неудачные поиски, т. е. работает, только если решение может быть найдено
зиггистар
источник
1
Хороший всесторонний ответ! Не могли бы вы пояснить, что вы подразумеваете под проблемой в форме дерева ? Кроме того, как вы предлагаете сохранить путь, пройденный алгоритмом для достижения цели, в отличие от полного обхода?
Брайан,
1
Задача в форме дерева @Brian означает, что искомый граф является деревом. И по вашему второму вопросу: это зависит от проблемы. Одна из возможностей - просто сохранить путь к узлу вместе с каждым развернутым узлом, если это возможно.
ziggystar
5
Более формально будет сказать, что «одно состояние» может быть посещено несколько раз поиском по дереву, а НЕ узел. Поскольку каждый узел в дереве поиска соответствует одному пути в графе пространства состояний и посещается не более одного раза при поиске по дереву. (Хотя это неверно для итеративного поиска с углублением, который пересекает дерево с увеличивающимися пределами глубины, но в этом случае также на каждой итерации каждый узел посещается только один раз)
Надер Ганбари,
1
@NaderhadjiGhanbari Является ли stateили nodeболее адекватным для вершин основного графа проблемы, в отличие от графа обхода, зависит от контекста. Но использование stateдля проблемного графа вершин и nodeдля графа обхода определенно может улучшить ясность ответа. Попробую скоро переписать. Спасибо.
ziggystar
TL; DR: поиск по графу использует закрытую структуру данных, а поиск по дереву - нет.
shinzou
8

Дерево - это частный случай графа, поэтому все, что работает для общих графов, работает и для деревьев. Дерево - это граф, в котором есть ровно один путь между каждой парой узлов. Это означает, что он не содержит никаких циклов, как указано в предыдущем ответе, но ориентированный граф без циклов (DAG, ориентированный ациклический граф) не обязательно является деревом.

Однако, если вы знаете, что ваш граф имеет некоторые ограничения, например, что это дерево или DAG, вы обычно можете найти более эффективный алгоритм поиска, чем для неограниченного графа. Например, вероятно, не имеет большого смысла использовать A * или его неэвристический аналог «алгоритм Дейкстры» на дереве (где в любом случае есть только один путь, который вы можете найти с помощью DFS или BFS) или на DAG (где оптимальный путь может быть найден путем рассмотрения вершин в порядке, полученном топологической сортировкой).

Что касается направленного и неориентированного, то неориентированный граф - это частный случай ориентированного, а именно случай, который следует правилу «если есть ребро (связь, переход) от u к v, то существует также ребро от v к u .

Обновление : обратите внимание, что если вам важен шаблон обхода поиска, а не структура самого графика, это не ответ. См., Например, ответ @ziggystar.

Njlarsson
источник
Хм, контекст вопроса мне не совсем понятен, но, взглянув на него еще раз, увидев ваш ответ, @ziggystar, я чувствую, что упоминание A * и AI указывает на то, что вы, возможно, правы, и мой ответ из контекста. Я интерпретировал «поиск по дереву» как «поиск по дереву». Не «поиск в общем графике с использованием древовидной схемы обхода», как следует из вашего ответа.
njlarsson
@njlarsson Я включил вашу перефразировку в свой ответ. Это хорошо для разъяснения.
ziggystar
Добавил примечание об этом в ответ. Я подозреваю, что мой ответ является правильным для многих людей, которые попадают сюда через Google и т. Д., Даже если он может быть вне контекста того, что искал Райханур Рахман.
njlarsson
Я видел, как многие студенты испытывают трудности с изучением поисковых алгоритмов, и ваш ответ просто вводит их в заблуждение.
Надер Ганбари
1
Ответ также касается алгоритмов поиска, но это правда, что плакат не об этом. См. «Обновление» в ответе - в марте 2014 года я понял, что неправильно понял вопрос. Я не хочу удалять ответ, потому что он все еще может быть полезен тем, кто пришел сюда через поиск.
njlarsson
3

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

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

0605002
источник
3
В дополнение к этому, если у вас действительно есть дерево, вам не нужно выполнять обнаружение дубликатов в A *. Тем не менее, вам все равно понадобится способ извлечь последний путь, поэтому у вас все еще может быть закрытый список.
Натан С.
Обычно дерево - это ориентированный граф с не более чем одним путем между любыми двумя вершинами. То есть между графами и деревьями есть два различия: направленный и уникальный путь. Алгоритм, работающий с DAG, не нуждается в проверке циклов, а алгоритм, работающий с деревом, не нуждается в проверке дубликатов.
thiton
1
Терминология варьируется, но деревья не всегда считаются направленными. Для корневого дерева, т. Е. Когда один узел указан как корень, существует подразумеваемое направление, но деревья не обязательно должны быть корневыми. Также общие графы могут быть как ориентированными, так и неориентированными. Кроме того, если вы требуете только в большинстве одного пути между двумя вершинами, вы также включаете лес . Дерево обычно определяется как связный граф, т.е. должен быть ровно один путь.
njlarsson
Этот ответ больше касается разницы между деревьями и графами в теории графов, но не на самом деле с различными типами алгоритмов поиска.
mlibby
1

ГРАФИК ПРОТИВ ДЕРЕВА

  • У графиков есть циклы
  • У деревьев нет циклов «Например, представьте себе любое дерево в своей голове, ветки не имеют прямых связей с корнем, но ветви имеют связи с другими ветвями вверх»

Но в случае AI Graph-search vs Tree-search

Поиск по графу имеет хорошее свойство: всякий раз, когда алгоритм исследует новый узел и помечает его как посещенный, «Независимо от используемого алгоритма» алгоритм обычно исследует все другие узлы, достижимые из текущего узла.

Например, рассмотрим следующий граф с 3 вершинами AB и C и следующие ребра

AB, BC и CA. Ну, есть цикл от C до A,

И когда DFS, начиная с A, A сгенерирует новое состояние B, B сгенерирует новое состояние C, но когда C исследуется, алгоритм попытается сгенерировать новое состояние A, но A уже посещается, поэтому он будет проигнорирован. Прохладно!

А как насчет деревьев? Алгоритм хорошо деревьев не помечает посещенный узел как посещенный, но у деревьев нет циклов, как бы он попал в бесконечные циклы?

Рассмотрим это Дерево с 3-мя вершинами и рассмотрим следующие ребра

A - B - C с корнем A, вниз. Предположим, мы используем алгоритм DFS.

A сгенерирует новое состояние B, B сгенерирует два состояния A и C, потому что деревья не имеют «Отметить посещенный узел, если он исследован», поэтому, возможно, алгоритм DFS снова исследует A, тем самым генерируя новое состояние B, таким образом мы попадаем в бесконечный цикл.

Но вы что-то заметили, мы работаем над ненаправленными ребрами, то есть между AB и BA есть связь. конечно, это не цикл, потому что цикл подразумевает, что вершин должно быть> = 3, и все вершины различны, кроме первого и последнего.

ST A-> B-> A-> B-> A это не цикл, потому что он нарушает свойство цикличности> = 3. Но на самом деле A-> B-> C-> A - это цикл> = 3 различных узла Проверено, первый и последний узел одинаковы Проверено.

Снова рассмотрим ребра дерева, A-> B-> C-> B-> A, конечно, это не цикл, потому что есть два B, что означает, что не все узлы различны.

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

Мохамед Хорани
источник
Этот ответ сбивает с толку, потому что он, кажется, смешивает ситуацию, когда проблема представляет собой дерево или граф, с тем, использует ли сам алгоритм поиска дерево или граф во время поиска.
mlibby
1

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

Другой аспект заключается в том, что дерево обычно имеет какую-то топологическую сортировку или свойство, такое как двоичное дерево поиска, что делает поиск таким быстрым и простым по сравнению с графами.

Мадхи
источник