任何一致的启发式也是可采纳的。但是,启发式何时是可采纳的但不一致(单调的)呢?
请提供一个这种情况的例子。
回答:
正如Russel和Norvig在《人工智能:现代方法》(最常用的AI教科书)中指出的那样,提出一个可采纳但不一致的启发式是具有挑战性的。
显然,你可以在图中的节点上选择值,使它们代表的启发式是可采纳的但不一致的。Felner等人的这篇论文很好地展示了这两种可能的方式,但内容有点密集,所以我来总结一下:
- 这个启发式在
c1
处不一致,因为它给出的到达目标的成本下限(即较少的信息量)低于其父节点。通过父节点到达目标的成本估计至少为10(因为到达p
的路径成本为5,且p
处的启发式估计也为5)。然而,通过c1
到达目标的成本估计仅为8(父节点的成本(5),加上从父节点到c1
的路径成本(1),再加上c1
处的启发式估计(2))。 - 由于这个图是无向的,这个启发式在
c2
处也不一致,因为从c2
到p
的路径存在与上述相同的问题。
Felner等人还提供了一些可采纳但不一致的启发式的具体例子。考虑8拼图问题:
在这个拼图中,有8个编号为1-8的滑动瓷砖和一个空格。瓷砖开始时是无序的(如左图所示)。目标是通过将瓷砖滑动到空格中,使拼图达到右图所示的状态。这个问题的经典启发式(每个瓷砖到其应在位置的曼哈顿距离)是可采纳且一致的。
然而,你可以提出一个不同的启发式。也许你只想查看1、2和3到它们在目标状态中应在位置的曼哈顿距离(即相隔的方格数)。虽然这个启发式比所有瓷砖的曼哈顿距离提供的信息少,但它仍然是可采纳且一致的。
但假设你选择了另一组方块,比如5、6和7。然后假设你在每个节点计算启发式的方式是随机选择其中一组(1、2和3)或(5、6和7),并计算它们到目标位置的曼哈顿距离。这个启发式仍然是可采纳的——它只能低估或匹配到达目标状态所需的移动次数。然而,它不再是一致的——各节点的启发式估计之间没有明确的关系。