Ответ 1

Судя по существующим ответам, в этой концепции, похоже, много путаницы.

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

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

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

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

Ваш основной алгоритм поиска в графике выглядит примерно так: С начала узла 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 * обеспечивает оптимальное решение при использовании с допустимой эвристикой. Однако алгоритм поиска графа A * дает такую гарантию только в том случае, если он используется с согласованной (или "монотонной") эвристикой (более сильное условие, чем допустимость).

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

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

• обрабатывать неудачные поиски, то есть он работает только в том случае, если можно найти решение

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

GRAPH VS TREE

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

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

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

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

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

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

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

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

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

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

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

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

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

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