Используя поиск дерева

Question

У меня есть несколько вопросов, касающихся поиска деревьев и поиска на графике (неосведомленный поиск), как объяснено в главе 3 книги: http://aima.cs.berkeley.edu/

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

Первый вопрос: строят ли поиск графа и поиск дерева динамические деревья задачи под рукой?

Второй вопрос: я предполагаю, что поиск графика использовался для решения проблемы карты Румынии (переход от Арада в Бухарест) с DFS, BFS, UCS в качестве стратегий, которые сортируют только границу. Теперь есть стандартный способ изменить график карты Румынии на дерево, а затем использовать поиск дерева?

Третий вопрос: каковы некоторые из критериев, которые помогают нам выбрать между графиком и поиском дерева различных проблем?

Спасибо заранее

Answer 1

И BF, и DFS принимают график и вызывают его подграф. Этот подграф имеет все узлы, достижимые от начального узла, и является деревом.

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

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

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

Answer 2

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