迭代加深深度首先使用有限的内存进行搜索

This is a follow-up to Find first null in binary tree with limited memory.

这是在内存有限的二叉树中查找第一个null的后续操作。

Wikipedia says that iterative-deepening depth first search will find the shortest path. I would like an implementation that is limited in memory to k nodes and accesses the tree the least number of times.

*说,迭代加深深度优先搜索将找到最短路径。我想在内存中限制k个节点并以最少的次数访问树。

For instance, if my binary tree is:

例如,如果我的二叉树是:

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

And I'm limited to 5 nodes of memory than my search order is:

而且我的内存节点仅限于我的搜索顺序:

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

Now if my next read is to 7, I need to re-read 3. But if I make my next read to 14, then I don't need to re-read 3 just yet. If the solution is at 14, this will make my algorithm a bit faster!

现在,如果我的下一次读取是7,我需要重新读取3.但如果我将下一次读取到14,那么我还不需要重新读取3。如果解决方案是14,这将使我的算法更快一点!

I'm looking for a general solution; something that will work for any size memory and number of branches per node.

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

1 个解决方案

#1

If your nodes link to their parents, and the children of a node will always be enumerated in the same order, you can trace your steps without having to save them.

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