DFS "Может вернуть любой путь" - PullRequest
Новая
       55

DFS "Может вернуть любой путь"

0 голосов
/ 12 октября 2018

Это из практического экзамена AI из Университета Беркли, Калифорния.

Вопрос ставит enter image description here

Рассмотрим график пространства состояний, показанный выше.A является начальным состоянием, а G является целевым состоянием.Стоимость каждого ребра показана на графике.Каждое ребро можно пройти в обоих направлениях.Обратите внимание, что эвристика h1 согласована, но эвристика h2 не согласована.

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

Алгоритмы поиска были сначала глубиной, шириной вначале, равномерной стоимостью, A * с h1 и A * с h2.«Перечисленными путями» являются ABDG, ACDG и ABCDFG

Это дерево поиска, которое я построил из графика (с различными эвристиками и затратами на действия): enter image description here Решение говорит, чтоDFS будет возвращать ABDG, ACDG и ABCDFG, потому что «DFS может вернуть любой путь»

Я могу понять, что, если прерыватель связи будет более ранней буквой в алфавите, DFS вернет ABCDE G. Если связьболее поздняя буква в алфавите, DFS будет возвращать ACD G. Но я не понимаю, при каких обстоятельствах DFS будет возвращать ABDG или ABCDF G.

Я также думал, что DFS расширяет самый глубокий узел и возвращаетРешение таким образом.Правда ли, что он может вернуть любое решение пути?Если так, то как?

1 Ответ

0 голосов
/ 13 октября 2018

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

Например, предположим, что граф связан с этим порядком: 

Node   edges to ...
 A       B C
 B       C D
 C       D A B
 D       F B C G E
 F       G D
 G       E F
 E       D G

ТогдаОбход тривиально ABCDFG (первая ссылка на каждом узле).Из-за других порядков ребер будут возвращены другие решения.

Аналогично, BFS может привести к возвращению любого из 4-узловых решений.

Это очищает его?

...