В чем разница между поиском по графу и версиями поиска по дереву относительно поиска DFS, A * в искусственном интеллекте ?
источник
В чем разница между поиском по графу и версиями поиска по дереву относительно поиска DFS, A * в искусственном интеллекте ?
Судя по существующим ответам, эта концепция вызывает большую путаницу.
Различие между поиском по дереву и поиском по графу не связано с тем, является ли проблемный граф деревом или общим графом. Всегда предполагается, что вы имеете дело с общим графиком. Различие заключается в шаблоне обхода, который используется для поиска по графу, который может иметь форму графа или дерева.
Если вы имеете дело с проблемой в форме дерева , оба варианта алгоритма приводят к одинаковым результатам. Таким образом, вы можете выбрать более простой вариант поиска по дереву.
Ваш основной алгоритм поиска по графу выглядит примерно так. С начальным узлом 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 * дает эту гарантию только тогда, когда он используется с последовательной (или «монотонной») эвристикой (более сильное условие, чем допустимость).
Для простоты представленный код не:
state
илиnode
более адекватным для вершин основного графа проблемы, в отличие от графа обхода, зависит от контекста. Но использованиеstate
для проблемного графа вершин иnode
для графа обхода определенно может улучшить ясность ответа. Попробую скоро переписать. Спасибо.Дерево - это частный случай графа, поэтому все, что работает для общих графов, работает и для деревьев. Дерево - это граф, в котором есть ровно один путь между каждой парой узлов. Это означает, что он не содержит никаких циклов, как указано в предыдущем ответе, но ориентированный граф без циклов (DAG, ориентированный ациклический граф) не обязательно является деревом.
Однако, если вы знаете, что ваш граф имеет некоторые ограничения, например, что это дерево или DAG, вы обычно можете найти более эффективный алгоритм поиска, чем для неограниченного графа. Например, вероятно, не имеет большого смысла использовать A * или его неэвристический аналог «алгоритм Дейкстры» на дереве (где в любом случае есть только один путь, который вы можете найти с помощью DFS или BFS) или на DAG (где оптимальный путь может быть найден путем рассмотрения вершин в порядке, полученном топологической сортировкой).
Что касается направленного и неориентированного, то неориентированный граф - это частный случай ориентированного, а именно случай, который следует правилу «если есть ребро (связь, переход) от u к v, то существует также ребро от v к u .
Обновление : обратите внимание, что если вам важен шаблон обхода поиска, а не структура самого графика, это не ответ. См., Например, ответ @ziggystar.
источник
Единственная разница между графом и деревом - это цикл . Граф может содержать циклы, дерево - нет. Поэтому, когда вы собираетесь реализовать алгоритм поиска по дереву, вам не нужно учитывать существование циклов, но при работе с произвольным графом вам необходимо их учитывать. Если вы не обрабатываете циклы, алгоритм может в конечном итоге попасть в бесконечный цикл или бесконечную рекурсию.
Еще один момент, о котором следует подумать, - это свойства направленности графика, с которым вы имеете дело. В большинстве случаев мы имеем дело с деревьями, которые представляют отношения родитель-потомок на каждом краю. DAG (направленный ациклический граф) также показывает аналогичные характеристики. Но двунаправленные графики разные. Каждое ребро двунаправленного графа представляет двух соседей. Таким образом, алгоритмические подходы для этих двух типов графиков должны немного отличаться.
источник
ГРАФИК ПРОТИВ ДЕРЕВА
Но в случае 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, что означает, что не все узлы различны.
Наконец, вы можете реализовать алгоритм поиска по дереву, чтобы не исследовать один и тот же узел дважды. Но это имеет последствия.
источник
Проще говоря, дерево не содержит циклов, а где граф может. Поэтому при поиске следует избегать циклов в графах, чтобы не попасть в бесконечные циклы.
Другой аспект заключается в том, что дерево обычно имеет какую-то топологическую сортировку или свойство, такое как двоичное дерево поиска, что делает поиск таким быстрым и простым по сравнению с графами.
источник