一致和可接受的启发式方法

Question

任何一致的启发式也是可以接受的.但什么时候启发式可以接受但不一致(单调)？

请举例说明这种情况.

Answer 1

正如Russel和Norvig在" 人工智能:现代方法"(最常用的AI教科书)中指出的那样,提出一种可接受但不一致的启发式技术具有挑战性.

显然,您可以为图中的节点选择值,使得它们表示的启发式是可接受的但不一致.Felner等人的这篇论文有一个很好的例子,说明了这两种方法是可行的,但它有点密集,所以我总结一下:

• 这种启发式方法不一致,c1因为它给出了比其父节点更低的(即信息量更少)到达目标的成本下限.通过父节点到达目标的成本估计至少为10(因为路径的成本p为5,启发式估计p值为5).c1然而,通过目标达到目标的成本估算仅为8(父项成本(5),加上父项(1)的路径成本,加上c1(2)处的启发式估计).
• 由于这是无向图,这种试探法是在也不一致c2,因为从去c2到p具有与上述相同的问题.

Felner等人还提供了一些允许但不一致的启发式算法的具体例子.考虑8拼图问题:

在这个拼图中,有8个编号为1-8的滑动拼块和一个空的空间.切片不按顺序开始(如左图所示).目标是通过将瓷砖滑入空白区域,使拼图进入右上方所示的状态.这个问题的经典启发式(每个瓦片的曼哈顿距离到它应该是的位置)是可接受的和一致的.

但是,您可以提出不同的启发式方法.也许你只是想看看1,2,3的曼哈顿距离(即平方掉号)中,他们应该是在目标状态的位置.启发式虽然比所有瓷砖的曼哈顿距离信息量少,但仍然是可接受的和一致的.

但是,假设你选择广场,也许5,6的其他组,和7.然后让我们说你在每个节点计算的启发式方法是随机选择的集合中的一个(1,2和3)或(5,6和7)并计算他们与目标位置的曼哈顿距离.这种启发式方法仍然可以接受 - 它只能低估或匹配达到目标状态所需的移动次数.但是,它不再一致 - 每个节点的启发式估计之间没有明确的关系.