algorithm - 有人实现了SMA *搜索算法吗？

Question

我发现AIMA(Artificial Intelligence: A Modern Approach)中的算法描述根本不正确。 “必要”是什么意思？什么是内存限制？队列大小或已处理的节点？如果当前节点根本没有子节点怎么办？

我想知道此算法本身是否正确。因为我搜索了Internet，但是还没有人实现它。

谢谢。

Answer 1

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

我使用了3个列表-边界(开放列表)，叶列表和“树分支”列表。

Frontier是PDF中提到的Queue，它是一个常见的优先级队列，按从最佳到最坏的顺序排序。

叶子列表仅保留叶子(从最坏到最好排序)，当我们决定要忘记哪些叶子时，我们将需要它。 SMA只会忘记树叶，不会忘记整个 Twig 。

Twig 分支列表保留了完全展开的节点，这些节点的所有子节点都在内存中。我们将需要它来测试状态交集。

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

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

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

继任者列表。我们不可避免地需要这样做，以使f成本向上传播。另外，我还会保留简单的后继状态列表-像[已阻止，被遗忘，存在]。需要它来跟踪被遗忘和被阻塞的节点。 (在图中被某个节点阻止，该节点扩展得更快)

PDF中提到的两个F，是我们当前的F，也是最被遗忘的后继F。

节点深度

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

基本算法概述如下(类似于PDF):

如果边界标记为“finished”，则我们从边界中选择最佳节点-我们知道我们会记住这一点，请重置迭代器，在这种情况下(由于复杂的原因)，我们必须重置被遗忘的最佳继承者F。

如果列表中还没有此后继者(可能是，当我们想起的时候)-我们生成它并按照PDF中的说明将其设置为F。

然后进行最复杂的操作-我们测试边界或树分支列表中是否存在状态相同的节点。如果可以，我将在稍后描述。如果没有，我们只是将 child 添加到边疆(并从叶子列表中删除父对象)。

在所有情况下，后继者枚举结束时-我们进行f成本的所谓备份，并且如果我们没有任何被遗忘的节点(并且有一些后继者)，则从边界移除当前节点并将其添加到 Twig 列表。

如何忘记:我们从叶子列表(最差的叶子)中选择第一片叶子，将其从边界中删除，将其从父级的后继者列表中删除，如果需要，并且如果父级不在边界上，则更新(减少)父级的被遗忘的最好的父级F -我们将其从 Twig 列表中删除，然后将其添加到边界中，然后将其添加到叶子列表中(如果现在已经是叶子)(不再有后继者)。

如果生成了后继者，该怎么办，该后继者已经在边界列表或 Twig 列表中。首先，我们需要测试它是否更好-我们比较两个节点的PathCost + H(“原始” F)。请注意，我们根本无法比较备份的F-这是行不通的。如果不是更好-我们只需将后继状态设置为“阻止”即可。如果是-可能出现这种情况，则最差的节点是巨大子树的根(太复杂，无法再次说明)。在这种情况下，我们将子树完全切除，而SMA会一次忘记一堆节点。将较差的节点替换为较优的节点后，我们从其父级后继列表，边际列表，叶列表甚至 Twig 列表(甚至可能存在!)中删除了较差的节点，将后继状态设置为其父级并阻止别忘了检查最差节点的父节点现在是否阻塞了所有节点-我们需要将其F设置为无穷大，因为它成为终端节点。

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

我将在几周后分享工作实现的源代码。