algorithm - SMA* 算法与理解基本概念有关

Question

我正在尝试实现 SMA* 算法来解决 N-Puzzle 问题。

我在理解和实施以下问题时遇到困难：

1. 以下是 AIMA 书中的一句话：
   “SMA∗ 总是丢弃最差的叶节点——具有最高 f 值的节点。像 RBFS 一样，SMA∗ 然后将被遗忘节点的值备份到其父节点。通过这种方式，祖先节点被遗忘的子树知道该子树中最佳路径的质量。”
   当节点内存已满时，应丢弃内存中最差的叶子，并将其值记住在父节点中。我猜记忆的值不会覆盖父节点中的 f_cost，它是另一个变量吗？另外我不明白为什么如果我们从队列中删除最差的叶子，祖先如何知道子树中最佳路径的质量？（如书中引用所述）。
2. 算法扩展最佳节点并删除最差节点。我们可以通过在队列中
   找到最低的f值来确定最佳节点，并为这个f值找到具有最高g值的节点。
   最差节点可以通过搜索队列中的最高f值，然后通过找到一个已找到f和最低g的节点来找到。
   这些陈述是正确的，还是我误解了什么？
3. 当节点内存已满时，队列中最差的节点被移除，并且它的 f 成本被记住在父节点中。但是为什么我们要节省移除节点的 f 成本呢？我们在算法的什么地方使用它以及如何使用它？

标签： algorithmsearch