在线DFS（人工智能）中的问题

Question

我认为在线深度搜索算法中存在一些问题，因为我没有看到任何递归调用。这是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。