6

我发现 AIMA（人工智能：现代方法）中的算法描述根本不正确。“必要”是什么意思？内存限制是多少？队列大小或处理的节点？如果当前节点根本没有子节点怎么办？

我想知道这个算法本身是否正确。因为我搜索了互联网，还没有人实现它。

谢谢。

4

2 回答 2

3

我已经设法在 C# 中使用PDF实现了图形搜索。

我使用了 3 个列表 - 边界（开放列表）、叶列表和“树枝”列表。

  • Frontier 即 Queue，在 PDF 中提到，它是一个从好到坏排序的常见优先级队列。

  • 叶子列表只保留叶子，从最差到最好排序，当我们决定要忘记哪个叶子时，我们将需要它。SMA 只忘记树叶，而不是整个树枝。

  • 树分支列表保持完全展开的节点，其子节点都在内存中。我们需要它来测试状态交集。

我将快速二进制堆用于边界和叶列表，并将哈希表用于树分支列表。

节点应保留以下附加信息：

  • 具有位置的后继迭代器（指向后继列表需要位置）。如果我们忘记了，我们绝对不能将后继枚举重置为零，因为有可能我们忘记了刚刚添加的节点。我使用 IEnumerator，int 表示位置，bool 表示“完成”标志。

  • 继任者名单。我们不可避免地需要它来进行 f-cost 向上传播。我还保留了简单的后继状态列表——比如[阻塞、遗忘、存在]。它是跟踪被遗忘和阻塞的节点所必需的。（阻塞 - 在图中 - 由一些节点，它扩展得更快）

  • PDF 中提到的两个 F，我们当前的 F，以及最被遗忘的继任者 F。

  • 节点深度

边界和叶子列表中节点的排序应该像这样进行：“如果我们有“完成”枚举标志，则选择最好的被遗忘的后继 F，否则选择当前 F，如果相等，则选择最深的。叶列表使用完全相同的条件以相反的顺序排序。

基本算法大纲是这样的（类似于PDF）：

  • 我们从边界中选择最佳节点，如果它具有“已完成”标志 - 我们知道我们将记住，重置迭代器，并且在这种情况下我们必须重置最佳被遗忘的后继 F（出于复杂的原因）。

  • 如果我们在列表中还没有这个后继者（可以是，当我们记住时） - 我们生成它并将其设置为 F，如 PDF 中所述。

  • 然后是最复杂的事情 - 我们测试具有相同状态的节点是否存在于边界或树分支列表中。如果是这样 - 我将在稍后描述要做什么。如果不是，我们只需将子级添加到边界（并从叶列表中删除父级）。

  • 在所有后继枚举结束的情况下——我们进行所谓的 f 成本备份，如果我们没有任何被遗忘的节点（并且有一些后继），我们从边界中删除当前节点并将其添加到树分支列表。

如何忘记：我们从叶子列表（最差叶子）中选择第一个叶子，将其从边界中删除，将其从父节点的后继列表中删除，如果需要，如果父节点不在边界上，则更新（减少）父节点的最佳被遗忘后继节点的 F - 我们从树分支​​列表中删除它并将其添加到边界并将其添加到叶子列表，如果它现在是叶子（不再有后继者）。

如果我们生成了一个已经在边界或树分支列表中的后继者，该怎么办。首先，我们需要测试它是否更好——我们比较两个节点的 PathCost + H（“原始”F）。请注意，我们根本无法比较备份的 F - 这不起作用。如果不是更好 - 我们只是将后继状态设置为阻塞。如果是 - 可能存在这样的情况，即最差的节点是一个巨大子树的根（太复杂，无法再次解释）。在这种唯一的情况下，我们完全切断了子树，SMA 立即忘记了一堆节点。在用更好的节点替换更差的节点后，我们从它的父后继列表、边界、叶列表甚至树分支列表中删除更差的节点（它甚至可能在那里！），将后继状态设置为阻塞它的父节点并不要'不要忘记检查是否更糟糕的节点'

也许我没有最简单的实现，但它是唯一对我有用的。我使用了 8 个拼图进行测试 - 使用最少 (n+1) 个内存（计算起始节点）解决 n 步，并使用传统的 a-star 检查解决方案的最优性。我花了大约 20 到 30 个小时试图找出所有细节 - 主要问题在于失败测试用例的复杂性 - 我只有在 20 多个步骤中出现“用更好的节点替换”逻辑错误对数以千计的随机种子进行广泛测试。还要注意优先级队列——在很多情况下我不得不重新插入项目，导致 F、最好忘记的 F 或“完成”标志的任何变化——改变排序顺序。我最终检查了每个出队的二进制堆一致性。摆脱最复杂的无休止循环错误的主要想法是检查，在所有情况下都不会降低 F。这样 F 会不断增加。

我将在几周内分享有效的实现源代码。

于 2013-01-31T23:18:05.910 回答
2

我相信这个 PDF是 AIMA 的 SMA* 部分，适用于那些没有这本书的人。

我首先注意到来自 Wikipedia 的伪代码在该行中有一个相当明显的错误：

parent.successors.remove(parent);

它应该是

parent.successors.remove(badNode);

（父母怎么可能是自己的继任者？）

“必要”是什么意思？

如果它的父级还没有在队列中，那么我们必须将它添加到队列中。否则，我们最终将再次搜索该节点。

内存限制是多少？队列大小或处理的节点？

队列将占用所有可用内存。处理的节点没有队列。这正是 SMA* 可以重新遍历节点并可能卡住的原因。

如果当前节点根本没有子节点怎么办？

如果一个节点没有孩子，那么它就是一个叶子节点。如果它是一个叶节点，那么它就是一个终端节点。在这种情况下，如果它不是目标节点，我们将其 f-cost 设置为无穷大，并将该信息传播给它的父节点。

于 2009-12-13T20:47:41.907 回答