algorithm - 在线 DFS(人工智能)中的问题

Question

我认为 Online-Depth-Search Algorithm 存在一些问题，因为我没有看到任何递归调用。
这是来自 peter Norvig 的代码。
如果正确或错误，请帮助我理解这一点。

function ONLINE -DFS-AGENT (s′) returns an action

    inputs: s′, a percept that identifies the current state

    persistent: result , a table indexed by state and action, initially empty
    untried, a table that lists, for each state, the actions not yet tried
    unbacktracked , a table that lists, for each state, the backtracks not yet tried

    s, a: the previous state and action, initially null

    if GOAL-TEST(s') then 
        return stop
    if s ′ is a new state (not in untried ) then 
        untried[s′] ← ACTIONS(s′)
    if s is not null then
        result[s, a] ← s′
        add s to the front of unbacktracked[s′]
    if untried[s′] is empty then
        if unbacktracked[s′] is empty then return stop
        else a ← an action b such that result [s′, b] = POP(unbacktracked [s′])
    else 
        a ← POP (untried [s′])
    s ← s′
    return a

Answer 1

你几乎不需要递归，它只是方便。

使用一个或多个堆栈是 DFS 的替代方法。具体上面的堆栈代码涉及:

两张牌堆:untried和 unbacktracked

设置整个堆栈:untried[s′] ← ACTIONS(s′)

将元素插入堆栈:add s to the front of unbacktracked[s′]

弹出一个元素:[s′, b] = POP(unbacktracked [s′])

弹出一个元素:a ← POP (untried [s′])

使用显式堆栈而不是递归的原因是:

更容易停止

许多系统上的动态内存比堆栈内存的限制要少，因此您可以处理更大的图形

但是，代码不清楚 - 它使用 POP 和“将 s 添加到前面”，我认为这是一个 PUSH。