有人实施过 SMA* 搜索算法吗？
我在 AIMA 中找到了算法描述（人工智能：现代方法）根本不正确。 “必要”是什么意思？内存限制是多少？队列大小或处理的节点？如果当前节点根本没有子节点怎么办？
我想知道这个算法本身是否正确。因为我上网查了一下，还没人实现。
谢谢。
I find the algorithm description in AIMA (Artificial Intelligence: A Modern Approach) is not correct at all. What does 'necessary' mean? What is the memory limit? The queue size or processed nodes? What if the current node has no children at all?
I am wondering if this algorithm itself is correct or not. Because I searched the Internet and nobody has implemented it yet.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我已经成功地在 C# 中使用 PDF 来实现图形搜索。
我使用了 3 个列表 - 前沿（开放列表）、叶列表和“树枝”列表。
Frontier是Queue，在PDF中提到的，它是一个常见的优先级队列，从最好到最差排序。
Frontier是Queue，在PDF
叶子列表只保留叶子，从最差到最好排序，当我们决定忘记哪个叶子时，我们将需要它。 SMA 只忘记叶子，而不是整个分支。
树分支列表保留完全展开的节点，其子节点都在内存中。我们需要它来测试状态交集。
我使用快速二进制堆作为边界和叶列表，使用哈希表作为树枝列表。
节点应保留以下附加信息：
具有位置的后继迭代器（需要位置来指向后继列表）。如果我们忘记了，我们绝对不能将后继枚举重置为零，因为我们有可能忘记刚刚添加的节点。我使用 IEnumerator，int 表示位置，bool 表示“完成”标志。
继任者名单。我们不可避免地需要它来进行 f 成本向上传播。我还保留简单的后继状态列表 - 例如[被阻止、被遗忘、存在]。它需要跟踪被遗忘和被阻止的节点。 （在图表中被某个节点阻止，该节点扩展得更快）
PDF 中提到的两个 F，我们当前的 F，以及最容易被遗忘的后继 F。
节点深度
边界和叶列表中的节点排序应该像这样完成：“如果我们有“完成”枚举标志，则选择最佳被遗忘的后继 F，否则选择当前F，如果等于，选择最深”。叶列表使用完全相同的条件按相反顺序排序。
基本算法大纲是这样的（类似于PDF）：
我们从边界中选择最好的节点，如果它有“完成”标志 - 我们知道我们会记住，重置迭代器，并且我们必须重置最好的被遗忘的后继F在这种情况下（由于复杂的原因）。
如果我们在列表中还没有这个后继者（可能是，当我们记得的时候） - 我们生成它并按照 PDF 中的描述将其设置为 F。
接下来是最复杂的事情 - 我们测试具有相同状态的节点是否存在于边界或树分支列表中。如果是的话 - 我将描述稍后要做什么。如果不是，我们只需将子节点添加到边界（并从叶列表中删除父节点）。
在所有情况下，当后继枚举结束时 - 我们都会进行所谓的 f 成本备份，如果我们没有任何被遗忘的节点（并且有一些后继节点），我们会从边界中删除当前节点并添加 在所有情况下，
如何忘记：我们从叶子列表中选择第一个叶子（最差的叶子），将其从边界中删除，将其从父代的后继者列表中删除，如果需要，并且如果父代不在边界上，则更新（减少）父代最好的被遗忘的后继者的F - 如果它现在是叶子（不再有后继者），我们将其从树枝列表中删除并将其添加到边界，并将其添加到叶子列表中。
如果我们生成了一个后继者，它已经在边界或树枝列表中，该怎么办？首先，我们需要测试它是否更好 - 我们比较两个节点的 PathCost + H（“原始”F）。请注意，我们根本无法比较备份的 F - 这是行不通的。如果还不好——我们只需将后继状态设置为阻塞。如果是的话 - 可能会出现这种情况，最糟糕的节点是一个巨大子树的根（太复杂而无法再次解释）。在唯一的情况下，我们完全切断了子树，SMA 立即忘记了一堆节点。用更好的节点替换更差的节点后，我们从其父后继列表、边界、叶列表甚至树分支列表（它甚至可能在那里！）中删除更差的节点，将其父节点的后继状态设置为阻塞，然后停止不要忘记检查更差节点的父节点现在是否已阻止所有节点 - 我们需要将其 F 设置为无穷大，因为它成为终端节点。
也许我没有最简单的实现，但它是唯一适合我的实现。我使用 8 个谜题进行测试 - 使用最少 (n+1) 内存（计算起始节点）解决 n 个步骤，并使用传统的 a-star 检查解决方案的最优性。我花了大约 20-30 个小时试图弄清楚所有细节 - 主要问题在于失败测试用例的复杂性 - 我仅在 20 多个步骤中遇到了“用更好的节点替换”逻辑错误对数千个随机种子进行广泛测试。还要注意优先级队列 - 在很多情况下我必须重新插入项目，导致 F 发生任何变化，最好忘记 F 或“完成”标志 - 更改排序顺序。我最终检查了每次出队时二进制堆的一致性。消除无限循环中最复杂、最难以理解的错误的主要思想是检查您是否在所有情况下都不会减少 F。这样F就会不断增加。
我将在几周内分享工作实施源代码。
I've managed to implement graph search with it in C#, using the PDF.
I've used 3 lists - frontier (open list), leaf list and "tree branch" list.
Frontier is the Queue, mentioned in the PDF, it is a common priority queue sorted from best to worst.
Leaf list keeps only leaves, sorted from worst to best, we will need it when we'll decide what leaf to forget. SMA forgets only leaves, not whole branches.
Tree branch list keeps fully expanded nodes, whose children are all in memory. We'll need it to test state intersection.
I've used fast binary heaps for frontier and leaf list, and hash table for tree branch list.
Nodes should keep the following additional info:
Successors iterator with position (position is needed for pointing in successors list). We absolutely must not reset our successor enumeration to zero if we forget as we go, cause it is possible, that we forget the node we just added. I use IEnumerator, int for position and bool for "finished" flag.
Successors list. We unevitably need this for f-cost upwards propagation. Also I keep simple successor states list - like [blocked, forgotten, exists]. It is needed for keeping track of forgotten and blocked nodes. (blocked - in graph - by some node, which expanded faster)
Two F's, mentioned in the PDF, our current F, and best forgotten successor F.
Node depth
Sorting of nodes in both frontier and leaf list should be done like this: "if we have "finished" enumeration flag, pick best forgotten successor F, else pick current F, if equals, pick deepest". Leaf list is sorted in reverse order using the exact same condition.
Basic algorithm outline is like this (similar to PDFs):
We pick best node from frontier, if it has "finished" flag - we know we'll be remembering, reset the iterator, and we must reset best forgotten successor F in this case (for complicated reasons).
If we don't have this successor in list already (can be, when we're remembering) - we generate it and set it's F as described in PDF.
Then follows the most complex thing - we test if the node with the same state exists in frontier or tree branch list. If it does - I'll describe what to do later. If not we just add child to frontier (and remove parent from leaf list).
In all cases when enumeration of successors ends - we do the so-called backup of f-costs, and if we don't have any forgotten nodes (and have some successors), we remove current node from the frontier and add it to tree branch list.
How to forget: we pick first leaf from leaf list (the worst leaf), remove it from the frontier, remove it from parent's successors list, update (decrease) parent's best forgotten successor's F, if needed, and if parent is not on frontier - we remove it from tree branch list and add it to frontier and also add it to leaf list, if it's now a leaf (doesn't have successors anymore).
What to do, if we generated a successor, that is already in frontier or tree branch list. First, we'll need to test it's better - we compare PathCost + H (the "original" F) of the two nodes. Note, that we can't compare backed-up F's at all - this will not work. If it's not better - we just set the successor state to blocked. If it is - there could be the case, that the worse node is a root of a huge subtree (too complicated to explain again). In this only case we cut the subtree completely and SMA forgets a bunch of nodes at once. After replacing the worse node with the better node, we remove worse node from it's parent successor list, from frontier, leaf list, or even tree branch list (it could be even there!), set successor state to blocked for it's parent and don't forget to check if worse node's parent have all nodes blocked now - we'll need to set it's F to infinity, cause it became the terminal node.
Maybe I've got not the simplest implementation, but it's the only, that works for me. I've used 8-puzzles for tests - solving n-steps with a minimum of (n+1)-memory (counting starting node), and checking the solution optimality with conventional a-star. I've spent like 20-30 hours trying to figure out all the details - the main problem was in the complexity of the fail test cases - I've got the "replacing with better node" logic bugs only on 20+ steps with an extensive testing of thousands random seeds. Also watch out for priority queues - I had to reinsert the item in so much cases, cause any change in F, best forgotten F, or "finished" flag - changes the sort order. I ended up checking my binary heaps consistency on every dequeue. And the main idea of getting rid of the most complicated to understand bug of endless cycling is to check, that you do not decrease F's in all cases. This way the F's will keep to increase.
I'm going to share the working implementation source in a couple of weeks.
我相信此 PDF 是 SMA* 部分来自 AIMA，适合那些没有这本书的人。
我首先注意到维基百科的伪代码在该行中有一个相当明显的错误：
它应该是
（父母如何成为自己的继任者？）
如果它的父级尚未在队列中，那么我们必须将其添加到队列中。否则，我们将再次搜索该节点。
队列将占用所有可用内存。已处理节点没有队列。这正是 SMA* 可以重新遍历节点并可能陷入困境的原因。
如果一个节点没有子节点，那么它就是叶节点。如果它是叶节点，那么它就是终端节点。在这种情况下，如果它不是目标节点，我们将其 f 成本设置为无穷大，并将该信息传播到其父节点。
I believe this PDF is the SMA* section from AIMA, for those that don't have the book.
I first note the pseudocode from Wikipedia has a rather obvious error in the line:
It should be
(How could a parent be its own successor?)
If its parent is not already in the queue, then we have to add it to the queue. Otherwise, we'll end up searching this node again.
The queue will take up all available memory. There is no queue for processed nodes. This is precisely why SMA* can re-traverse nodes and potentially get stuck.
If a node has no children, then it's a leaf node. And if it's a leaf node, then it's a terminal node. In that case, if it's not the goal node, we set its f-cost to infinity, and propagate that information to its parent.