迭代深化深度优先搜索算法的最优性错误
我用Python实现了一个“高峰时刻”这个拼图游戏，主要是为了演示一些人工智能算法。游戏本身并不重要，因为人工智能的实现和游戏的细节关系不大。我尝试在Python中实现一种叫做“迭代加深深度优先搜索”的算法，代码几乎是直接从Russell和Norvig的人工智能教材第三版中复制过来的，大家如果知道这本书的话就明白了：
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步的解。如果我把上面注释掉的代码替换成注释中的代码，实际上把迭代加深深度优先搜索变成了迭代加深广度优先搜索，那么算法就能返回最优解了！
我盯着这个问题看了很久，试图弄明白为什么简单的遍历顺序改变会导致非最优解，但我还是搞不明白。如果有人能指出我这个愚蠢的错误，我将非常感激。
2 个回答
你的代码找到的不是最优解，主要是因为深度优先搜索和广度优先搜索的工作方式不同。
广度优先搜索会先尝试所有可能的8步解决方案，然后才会尝试任何9步的解决方案，所以广度优先搜索一定会找到步数最少的解决方案。
相对而言，深度优先搜索会在尝试完所有8步的解决方案之前，先尝试一些9步、10步、11步等的解决方案，因此可能会得到一个不是最优的结果。
举个例子，假设有一个游戏树长这样：
1
/ \
2 3
/ \ / \
4 5 6 7
/\ /\ /\ /\
8 9 A B C D E F
按照你给出的代码，goal_test的调用顺序是：2, 3, 6, 7, E, F, C, D, 4, 5, A, B, 8, 9。注意，节点E和F在节点6的子节点之前被测试，也在节点2的子节点之前被测试。这就是深度优先搜索。
而你代码的另一种版本会按照这个顺序调用goal_test：2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F。这是广度优先搜索。
编辑：抱歉，我之前提到的goal_test的调用顺序只对iterative_deepening_search的最后一次迭代是正确的。实际的调用顺序是：2, 3, 2, 3, 6, 7, 4, 5, 2, 3, 6, 7, E, F, C, D, 4, 5, A, B, 8, 9。我通过实际运行代码验证了这一点，所以我可以100%确定现在是正确的。
你确定每个游戏节点的child.state值都是唯一的吗？如果不是，算法就会失败。比如，假设节点4和节点6的状态是一样的。在这种情况下，你的代码会按照这个顺序调用goal_test：2, 3, 2, 3, 6, 7, 5, 2, 3, 6, 7, E, F, C, D, 5, A, B。注意，goal_test从来没有在节点4、8和9上被调用。
但是如果我们切换到你代码的另一种版本，那么goal_test的调用顺序是：2, 3, 2, 3, 4, 5, 7, 2, 3, 4, 5, 7, 8, 9, A, B, E, F。现在goal_test没有在节点6、C和D上被调用！我认为这可能是你问题的原因。
我不能测试这个，但我觉得问题出在这个条件判断上：
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 -/
显然，如果限制小于 3，你是无法达到目标的。但是当限制等于 3 时，你的深度优先搜索可能会先访问 A、B 和 C。然后当它回溯到 S，访问 D，并尝试访问 C 时，它不会把 C 放回栈里，因为你之前已经访问过它了。
为了解决这个问题，我认为你需要在回溯时“取消访问”那些状态。从实现的角度来看，最简单的方法可能是以递归的方式编写你的算法，并以函数式风格传递你已经探索过的状态集合的副本。