迭代加深 A 星 (ID A*) 是一种内存有界搜索。我的问题是,当我们s'
从 ID A* 中的打开状态到达新状态时s
,为什么我们不测试是否s'
已经处于“打开状态”或“关闭状态”?
对于某些问题,例如:数独,因为状态永远不会达到两次,因为“问题的状态图”是一棵树。但是,对于其他问题,例如:一个 8 拼图,它很可能会一次又一次地达到一个状态。因此,绝对应该测试一个状态是否已经“访问过”(无论是打开状态还是关闭状态)。
如果必须进行这样的测试,那么 ID A* 不再是内存受限的,因为必须存储所有可能状态的大型哈希表。