我发现aima（Artificial Intelligence: A Modern Approach）中的算法描述完全不正确。“必要”是什么意思？内存限制是多少？队列大小或已处理的节点？如果当前节点没有子节点怎么办？
我想知道这个算法本身是否正确。因为我在网上搜索了一下，还没人实现。
谢谢。
最佳答案
我已经设法用它在c_中实现了图形搜索，使用the PDF。
我使用了3个列表-Frontier（开放列表）、Leaf列表和“Tree Branch”列表。
frontier是pdf中提到的队列，它是一个从最好到最差排序的公共优先级队列。
叶子列表只保存叶子，从最坏的到最好的排序，当我们决定要忘记什么叶子时，我们需要它。SMA只会忘记叶子，而不会忘记整个树枝。
树分支列表保留完全展开的节点，其子节点都在内存中。我们需要它来测试状态交集。
我使用快速二进制堆作为frontier和leaf列表，使用hash表作为tree branch列表。
节点应保留以下附加信息：
具有位置的后续迭代器（在后续列表中需要位置来指向）。如果我们忘记了刚才添加的节点，那么绝对不能将后续枚举重置为零，因为可能会忘记刚才添加的节点。我使用IEnumerator，int表示位置，bool表示“finished”标志。
继任者名单。我们无可避免地需要这个来进行f成本向上传播。此外，我保持简单的继承国名单-像[封锁，忘记，存在]。需要它来跟踪被遗忘和阻塞的节点。（图中被某个节点阻塞，扩展速度更快）
两个f，在pdf中提到，我们当前的f，以及最被遗忘的继承者f。
节点深度
frontier和leaf列表中节点的排序应该这样做：“如果我们已经“完成”枚举标志，则选择best forgotten后继f，否则选择current f，如果等于，则选择depth”。叶列表使用完全相同的条件按相反的顺序排序。
基本算法大纲如下（类似于PDF）：
我们从frontier中选择最佳节点，如果它有“finished”标志——我们知道我们会记住，重置迭代器，在这种情况下，我们必须重置被遗忘的最佳继承者f（出于复杂的原因）。
如果列表中还没有这个继任者（可以是，当我们记事的时候）-我们生成它并设置它为pdf中描述的f。
然后遵循最复杂的事情——我们测试在边界或树分支列表中是否存在相同状态的节点。如果是的话-我稍后会描述该怎么做。如果不是，我们只需将子元素添加到frontier（并从叶列表中移除父元素）。
在所有情况下，当后续节点的枚举结束时-我们执行所谓的f-costs备份，如果没有任何被遗忘的节点（并且有一些后续节点），我们将当前节点从边界中移除并将其添加到树分支列表中。
如何忘记：我们从叶列表中选择第一个叶（最差的叶），从边界中移除它，从父级的继承者列表中移除它，如果需要，更新（减少）父级被遗忘的最佳继承者的f，如果父级不在边界上-我们从树分支列表中移除它，将其添加到边界，并将其添加到叶列表中，如果它现在是一片叶子（不再有接班人了）。
怎么办，如果我们产生了接班人，那已经在边疆或树枝名单上了。首先，我们需要测试它是否更好-我们比较两个节点的pathcost+h（原始的f）。注意，我们根本无法比较备份的F—这不起作用。如果不是更好的话-我们只是将继承状态设置为阻止。如果是这样的话——可能是这样的，更糟糕的节点是一个巨大子树的根（太复杂，无法再解释）。在这种情况下，我们完全切断子树和形状记忆合金忘记了一堆节点。将坏节点替换为好节点后，我们将坏节点从其父继承者列表、frontier、leaf列表甚至树分支列表中移除（甚至可能存在！），将其父节点的后续状态设置为blocked，不要忘记检查更糟节点的父节点是否现在已阻止所有节点-我们需要将其f设置为无穷大，因为它已成为终端节点。
也许我没有最简单的实现，但它是唯一对我有效的。我用了8个谜题来测试——用最少的（n+1）内存（计算起始节点）来解决n个步骤，用传统的a星来检查解决方案的最优性。我花了大约20-30个小时试图找出所有的细节-主要的问题是在复杂的失败测试案例-我有“替换更好的节点”逻辑错误只在20 +步骤与广泛的测试数以千计的随机种子。还要注意优先级队列-在很多情况下，我必须重新插入项目，导致f中的任何更改、best forget f或“finished”标志更改排序顺序。最后我检查了每个出列上的二进制堆的一致性。消除最复杂的理解无休止循环的错误的主要思想是检查，在所有情况下你都不能减少f。这样F值会继续增加。
我将在几周内分享工作实现源代码。