0

迭代加深 A 星 (ID A*) 是一种内存有界搜索。我的问题是,当我们s'从 ID A* 中的打开状态到达新状态时s,为什么我们不测试是否s'已经处于“打开状态”或“关闭状态”?

对于某些问题,例如:数独,因为状态永远不会达到两次,因为“问题的状态图”是一棵树。但是,对于其他问题,例如:一个 8 拼图,它很可能会一次又一次地达到一个状态。因此,绝对应该测试一个状态是否已经“访问过”(无论是打开状态还是关闭状态)。

如果必须进行这样的测试,那么 ID A* 不再是内存受限的,因为必须存储所有可能状态的大型哈希表。

4

2 回答 2

1

我们不测试 s' 是否是重复的,以保持内存配置文件较小。一般来说,IDA *实际上会多次扩展同一个状态。

于 2013-10-06T20:48:37.527 回答
1

人工智能编程通常是尝试对算法进行许多不同的调整,以找到最适合您需求的算法。如果很可能已经访问过一个新状态,那么增加确定一个状态是否已经访问过的额外开销可能是一种性能改进。但可能还有许多其他变量需要考虑,例如算法如何适应问题、可用内存、处理能力、可扩展性。我认为成为一名优秀的 AI 程序员意味着您了解不同算法的优缺点,并了解有多少不同的问题会影响每种算法的性能。我认为您不应该认为像 ID A* 这样的算法仅限于不考虑是否已经达到状态。如果你认为考虑重新进入状态会表现得更好,

于 2013-10-06T20:58:33.433 回答