Как применять итерационного Углубление глубиной первого поиска (IDDFS) на графах

Question

Я попытался применить IDDFS на этом графике, сначала сделав его в виде дерева, и результат был таков:

At level 1: d,e,p 
At level 2: d,b,e,c,e,h,r,p,q 
At level 3: d,b,a,e,h,c,a,e,h,q,p,r,f,p,q 
At level 4: d,b,a,e,h,p,q,c,a,e,h,q,p,q,r,f,c,GOAL 

I я запутался в этих повторяющихся узлах пути, мы можем их устранить или они появятся в конечном пути?

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

И какой будет путь, если мы применим DFS и BFS на одном графике?

Будет ли разница в результатах DFS и IDDFS? Вроде бы похоже

Answer 1

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

2. Если вы выписываете расширение для BFS и DFS, вы увидите, что IDDFS начинает выглядеть как BFS и в конечном итоге выглядит все более похожим на DFS, тем больше вы повышаете уровень. Когда level = length-of-longest-path, voila, вы получаете DFS, что неудивительно, поскольку IDDFS - это DFS, только с отключенными путями по заданному числу; в этом конкретном случае число не имеет эффекта, потому что нет путей, достаточно длинных, чтобы их можно было отрезать.

3. Порядок на графике не определен. Вы сами выбираете тот или иной порядок. Если вы выбираете следующий узел наугад, вы получаете недетерминированные алгоритмы. Если вы выберете их, dunno, в алфавитном порядке, то вы получите некоторый детерминизм. Иногда различие не имеет значения, но детерминизм хорош для отладки вашего кода и т. Д. Теперь, когда вы делаете это упражнение, вы делаете это, чтобы видеть шаблоны, поэтому лучше не учитывать случайность.

Ваш вопрос действительно выглядит как домашнее задание. ;)