使用有限内存的迭代加深深度优先搜索

Question

这是在二进制文件中查找第一个空值的后续内容内存有限的树。

维基百科说，迭代深化深度优先搜索将找到最短路径。 我想要一个将内存限制为 k 个节点并且访问树的次数最少的实现。

例如，如果我的二叉树是：

           0
    1             2
 3    4        5      6
7 8  9 10    11 12  13 14

我的内存限制为 5 个节点，而我的搜索顺序是：

mem[0] = read node 0
mem[1] = read node 1
mem[2] = read node 2
mem[3] = read node 3
mem[4] = read node 4 //Now my memory is full.  I continue...
mem[3] = read node 5 //overwrite where I stored node 3
mem[4] = read node 6 //overwrite where I stored node 4

现在，如果我的下一次读取是 7，我需要重新读取 3。但是如果我下一次读取到14，那么我还不需要重新阅读3。 如果解是 14，这将使我的算法更快一些！

我正在寻找一个通用的解决方案； 适用于任何大小的内存和每个节点的分支数量的东西。

Answer 1

如果您的节点链接到其父节点，并且节点的子节点将始终以相同的顺序枚举，则您可以跟踪您的步骤而无需保存它们。