Поиск по глубине рекурсивный псевдокод

Question

Я смотрю на псевдокодовую реализацию Depth-Limited Search, и у меня возникают проблемы с ее пониманием.

Псевдокод это:

Function Recursive-DLS(node, problem, limit)
    cutoff-occurred? = false
    if Goal-Test(problem, State[node]) then return node
    else if Depth[node] = limit then return cutoff
    else for each successor in Expand(node, problem) do
            result = Recursive-DLS(successor, problem, limit-1) 
            if result = cutoff then cutoff-occurred? = true
            else if result != failure then return result        
    if cutoff-occurred? then return cutoff else return failure

В основном у меня проблемы с пониманием причины повторения алгоритма с пределом-1 для каждого преемника. Может ли кто-нибудь пройти через это со мной? Некоторое графическое объяснение было бы неплохо, ха-ха.

Я собираюсь посмотреть на другие источники в то же время. Спасибо за прочтение!

Answer 1

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

Рекурсивный случай был написан с limit - 1 Таким образом, базовый случай может быть достигнут (вместо "предел", подумайте "оставшиеся").

Тем не менее, базовый случай для ограничения if Depth[node] = limit then return cutoff, После предложения Дэвида Чана это должно быть if 0 = limit then return cutoff, который согласился бы с limit - 1 в рекурсивном случае.

Или просто пройдите limit в рекурсивном случае и оставить текущий базовый случай в покое.