Почему говорят, что поиск в глубину страдает от бесконечных циклов?

Question

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

Насколько я знаю, это ограничение можно легко снять, отслеживая посещенные узлы.Фактически, во всех книгах, которые я прочитал, эта небольшая проверка является частью DFS.

Так почему же «бесконечные циклы» упоминаются как недостаток DFS?Это просто потому, что оригинальный алгоритм DFS не имел этой проверки для посещенных узлов?Пожалуйста, объясните.

Answer 1

(1) В алгоритмах поиска по графу [часто используемых в AI] главное преимущество DFS - эффективность использования пространства . Это его главное преимущество на BFS. Однако, , если вы отслеживаете посещенные узлы, вы теряете это преимущество , так как вам нужно хранить все посещенные узлы в памяти. Не забывайте, что размер посещаемых узлов резко увеличивается со временем, а для очень больших / бесконечных графиков - может не поместиться в памяти.

(2) Иногда DFS может находиться в бесконечной ветви [в бесконечных графах]. Бесконечная ветвь - это ветвь, которая не заканчивается [всегда имеет «больше сыновей»], а также не доставляет вас к вашему целевому узлу, поэтому для DFS вы можете бесконечно расширять эту ветвь и «пропустить» хорошую ветку, это приводит к целевому узлу.

Бонус:
Вы можете преодолеть этот недостаток в DFS, сохранив относительно небольшой объем памяти, используя комбинацию DFS и BFS: Итеративное углубление DFS

Answer 2

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