问题标签 [iterative-deepening]

这是Find first null in binary tree with limited memory的后续内容。

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

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

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

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

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

给定以下结构：

有没有办法解决这个问题：

或者换句话说，有没有办法让更高级别的标题包含在较低级别的标题和它们后面的所有内容中，从而创建一个嵌套结构。每个 TITEL1,2 和 3 标签的内容应该进入一个新的<TITEL>元素

给定以下 XML 结构（我在一个 XML 文件中有这个，还有很多其他内容 -<p>标签只是在那里表明其他标签可能会跟随）：

有没有办法使用 PHP 来解决这个问题（将其写入新文件）：

或者换句话说，有没有办法让更高级别的标题包含在较低级别的标题和它们后面的所有内容中，从而创建一个嵌套结构。每个 TITEL1,2 和 3 标签的内容应该进入一个新的<TITEL>元素

我已经在论坛的 XSLT 方面提出了同样的问题，但得到了尝试使用 c# 或 java 的建议。由于我不了解这些语言并且知道的比 PHP 的基础知识要多一些，所以我想尝试这种方式。任何人都可以让我上路吗？

我了解 BFS 和 DFS，但是对于我的生活来说，我无法弄清楚迭代深化和 BFS 之间的区别。显然，迭代深化与 DFS 具有相同的内存使用量，但我无法看到这是怎么可能的，因为它只是像 BFS 一样不断扩展。如果有人能澄清那将是很棒的。

如果需要，可以处理的树：

我有一个要解决的优化问题。你有某种数据结构：

和评级函数：

我必须rateFoo通过更改结构中的值来优化结果。在这种具体情况下，我决定使用迭代深化搜索来解决问题。用于最佳优化的（无限）搜索树由另一个函数创建，该函数简单地将所有可能的更改递归地应用于树：

我的搜索功能如下所示：

在我开始之前，我的问题是：

由于树可以由每个点的数据生成，是否可以只生成算法当前需要的树的部分？是否可以释放内存并在需要时重新生成树以节省内存（可以在 n 级生成一个叶，O(n)并且 n 仍然很小，但不足以随着时间的推移将整个树都放在内存中）？

这是我可以从运行时获得的东西吗？运行时可以取消计算表达式（将已计算的表达式转换为未计算的表达式）吗？或者我必须为此做些什么肮脏的黑客行为？

我正在使用以下控制结构（我认为它是尾递归的）

做迭代深化

在每次迭代深化之后，这个空闲内存（因为它在技术上将不再能够到达它），如果不是，我应该如何重写控制结构？

PS在第二个虽然看起来这会失败，因为尾递归结构经常能够访问堆栈上的东西，比如添加到前一个值，即使在这种情况下它没有。– Roman A. Taycher 11 月 28 日 12:33 PPS 在第三个问题上，尽管它让我认为它可以在 dfsWithMaxDepth 返回后立即丢弃 dfsWithMaxDepth 中的值，并且一堆答案不会占用太多内存。– Roman A. Taycher 11 月 2 日

每次迭代重新扫描 n-1 级节点不是多余的吗？

此刻我有一个看起来有点像这样的对象。

我正在尝试将它转换为另一个看起来非常相似的对象，除了它不允许循环之外。

它应该通过不扩展已经出现在更高深度的节点的子节点来处理循环。迭代深化解决了这个问题（深度优先搜索实现但广度优先搜索顺序），但我正在努力使用以下结构的实现。

我发现的所有实现都依赖于找到某种目标节点，而我需要扩展整个树。

任何帮助，将不胜感激。:D

我一直在阅读有关迭代深化的内容，但我不明白它与深度优先搜索有何不同。

我明白深度优先搜索会越来越深入。

在迭代深化中，您建立一个级别的值，如果在该级别没有解决方案，则增加该值，然后从头开始（根）。

这和深度优先搜索不一样吗？

我的意思是你会不断增加和增加，更深入，直到找到解决方案。我认为这是同一件事！我会沿着同一个分支走，因为如果我从头开始，我会像以前一样沿着同一个分支走。

So currently i have a DFS with the following pseudocode

How do I alter this function to accept a third argument that limits the depth of the search?