我用 Python 实现了一个“Rush Hour”（华容道）游戏，以此演示一些 AI 算法。游戏本身并不重要，因为 AI 相对独立于它的细节：我尝试用 Python 实现了一个迭代加深深度优先搜索算法，如下所示（请注意，对于熟悉 Russell 和 Norvig 的 AI 教材第 3 版的读者来说，这段代码几乎是直接从书中复制的）：

def depth_limited_search(game, limit):    node = GameNode(game)    frontier = []    #frontier = Queue.Queue()    frontier.append(node)    #frontier.put(node)    frontier_hash_set = set()    frontier_hash_set.add(str(node.state))    explored = set()    cutoff = False    while True:        if len(frontier) == 0:        #if frontier.empty():           break        node = frontier.pop()        #node = frontier.get()        frontier_hash_set.remove(str(node.state))        explored.add(str(node.state))        if node.cost > limit:            cutoff = True        else:            for action in node.state.get_actions():                child = node.result(action)                if str(child.state) not in frontier_hash_set and str(child.state) not in explored:                    if child.goal_test():                        show_solution(child)                        return child.cost                    frontier.append(child)                    #frontier.put(child)                    frontier_hash_set.add(str(child.state))    if cutoff:        return 'Cutoff'    else:        return Nonedef iterative_deepening_search(game):    depth = 0    while True:        result = depth_limited_search(game, depth)        if result != 'Cutoff':            return result        depth += 1

如上实现的搜索算法确实可以在合理的时间内返回答案。但问题是答案不是最优的。我选择的测试棋盘的最佳答案是 8 步，但是这个算法返回的是 10 步的答案。如果我将上面注释掉的行替换为未注释的行，实际上是将迭代加深深度优先搜索转换为迭代加深广度优先搜索，那么算法就会返回最优答案！

我已经盯着这个问题看了很久了，试图弄清楚为什么一个简单的遍历顺序的改变会导致非最优性，但我无法弄清楚。 非常感谢任何指出我愚蠢错误的人。

回答：

我无法测试这段代码，但我认为问题在于以下谓词：

if str(child.state) not in frontier_hash_set and \   str(child.state) not in explored:

问题在于，在这个 DFS 迭代的早期，child.state 可能已经被插入到 frontier 或已访问状态的集合中，但具有**更高的成本**。

S -> A -> B -> C -> G \            /  \-----> D -/ 

显然，当 limit < 3 时，你无法到达目标。但是当 limit = 3 时，你的 DFS 可能会首先访问 A、B 和 C。然后当它回溯到 S，访问 D，并尝试访问 C 时，它不会将 C 推入堆栈，因为你之前已经访问过它了。

为了解决这个问题，我认为你需要在回溯时“取消访问”状态。在实现方面，最简单的方法可能是以递归方式编写你的算法，并以函数式风格传递已探索状态集合的副本。