迭代深化深度优先搜索算法的最优性误差

Question

我已经在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 None

def iterative_deepening_search(game):
    depth = 0
    while True:
        result = depth_limited_search(game, depth)
        if result != 'Cutoff':
            return result
        depth += 1

实施的搜索算法确实在合理的时间内返回答案.问题是答案是非最佳的.我选择的测试板在8次移动中具有最佳答案,但是该算法使用10次移动返回一个.如果我用注释行替换注释掉的线以上的线,有效地将迭代加深深度优先搜索转换为迭代加深的广度优先搜索,算法将返回最佳答案!

我一直在盯着这个很长一段时间,试图找出遍历顺序的简单变化如何导致非最优性,我无法弄明白.任何帮助指出我的愚蠢错误将不胜感激

Answer 1

我无法测试这个，但我认为问题在于这个谓词：

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

问题是，在这个 DFS 迭代的早期，child.state可能已经被插入到边界或访问过的状态集中，但成本更大。

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

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

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