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

82

В чем разница междуgraph search а такжеtree search версии относительно DFS, A * ищет вartificial intelligence?

Ваш Ответ

5   ответов
155

в этой концепции, похоже, много путаницы.

The Problem Is Always a Graph

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

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

Difference Between Graph and Tree Search

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

Tree Search
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 звездный поиск, выбрав узел с наименьшимcost plus heuristic ценность и тд.

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

Graph Search

Как мы видели, поиск по дереву может посещать состояние несколько раз. И как таковой он будет исследовать «поддерево» найден после этого состояния несколько раз, что может быть дорого. Поиск в графике исправляет это, отслеживая все посещенные состояния вclosed list, Если недавно найденный преемник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
Comparison

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

Optimal solutions

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

A*

Также (очень популярный) A *tree Алгоритм поиска обеспечивает оптимальное решение при использовании сadmissible heuristic, А *graph алгоритм поиска, однако, дает эту гарантию только тогда, когда он используется сconsistent (or "monotonic") heuristic (более сильное условие, чем допустимость).

(2) Flaws of pseudo-code

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

handle failing searches, i.e. it only works if a solution can be found
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededstateError: User Rate Limit ExceedednodeError: User Rate Limit ExceededunderlyingError: User Rate Limit ExceededstateError: User Rate Limit ExceedednodeError: User Rate Limit Exceeded
Error: User Rate Limit Exceededtree-shaped problemError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

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

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

0

GRAPH VS TREE

Graphs have cycles Trees don't have cycles "For example imagine any tree in your head, branches don't not have direct connections to the root, but branches have connections to other branches, upward"

Но в случае AI Graph-search против Tree-search

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

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

A-B, B-C и C-A, ну, есть цикл от C до A,

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

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

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

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

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

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

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

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

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

Error: User Rate Limit Exceeded
5

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

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

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

Update: Обратите внимание, что если вы заботитесь оtraversal pattern of the search а не структура самого графа, это не ответ. См., Например, ответ @ ziggystar.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
2

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededtwoError: User Rate Limit Exceeded
Error: User Rate Limit ExceededrootedError: User Rate Limit Exceededat mostError: User Rate Limit ExceededforestsError: User Rate Limit ExceededpreciselyError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы