问题标签 [iterative-deepening]

我正在从这个链接学习迭代深化。我主要关心的是Overhead。该链接说

分支因子越高，重复扩展状态的开销越低

该声明没有给出解释，该链接也没有给出令人信服的论据。我正在寻找这个陈述背后的原因，因为我认为开销应该随着分支因子的增加而增加，这也意味着没有节点在增加，那么开销是如何减少的？

直到现在我还没有找到任何合理和有用的东西。如果有人可以帮助纠正我的概念，那么我将不胜感激。

我有一个学校作业要做一个迭代深化算法来解决一个 6x6 的高峰时间难题。我选择使用 JavaScript 是因为我需要练习。然而，我在优化算法时遇到了麻烦。

我试图解决一个难题，它的解决方案在树中的 8 个级别，我发现我访问了 7,350,669 个节点，我的计算机花了将近 13 分钟才解决。

我正在寻找技巧和帮助来理解算法本身。

我做了两个类——节点和车辆。这些的实现可能是问题的一部分：

我是否正确地假设，同时拥有一个用于网格的“二维”数组以及一个车辆数组是一种矫枉过正的行为？在检查可能的运动时，我会遍历车辆数组，但使用网格来快速检查车辆是否有空路。我会回到我看到的这个问题。

我无法公开发布该算法的代码，但这是我理解 IDDFS 并实现该算法的方式：

1. 检查当前节点是否为最终状态，如果是则将其添加到解决方案数组中并返回true。
2. 否则检查是否达到 maxDepth，如果达到则返回 false。
3. 如果不是，则为处于此状态的每辆车辆创建新节点，用于他们可以进行的所有移动（除了在最后移动中移动的那些）
4. 访问您刚刚创建的所有孩子（返回第 1 步），如果它们返回 false，则删除它们。
5. 如果没有一个子节点显示为最终状态，则返回父节点并探索其邻居。否则返回真正的连锁反应。
6. 重复直到找到最终状态。如果回到顶部，则将 maxDepth 增加 1 并重复整个过程。

我看到的一个问题是我的数据结构可能有点复杂。由于 JavaScript 将对象和对象数组作为引用传递，因此必须使用以下方法进行深度复制：

这里的主要问题是——我错过了什么吗？删除“坏”子节点并在迭代深化算法中一次又一次地遍历整个树是否正确，还是我误解了这一点？它们是否只是应该被标记为“已检查”，然后返回然后稍后通过它们，以便不必再次生成整个树？

我正在上一门人工智能课程，我们需要创建一个玩井字游戏的人工智能。

指导员指定在放置下一步时对 AI 的决策过程使用 alpha-beta 修剪。我现在遇到的问题是人工智能创建决策树并采取行动所需的时间。普通的 3x3 很好，3x4 和 4x3 需要一点时间，但是 4x4 第一步需要几分钟，而且我还没有从更大的游戏板上得到结果。

我使用的源代码：

如果需要，请提供源链接

导师还建议使用迭代加深搜索，但我是一个不知道怎么做的傻瓜。

我有一个关于搜索技术迭代深化的问题。我的问题是，正常的深度优先搜索和没有指定深度限制的迭代深化有什么区别？所以我有一棵带有目标节点的树，但在我的迭代深化搜索中没有指定限制。这会输出与我进行常规深度优先搜索相同的遍历序列吗？

我尝试实现迭代深度 A* 搜索。问题是他走的很正常，而不是我想要的。

当我声明一个节点时，我还写了他所在的级别（adancime）。

所以我的逻辑是，如果（他获得的级别与作业中的级别（adancime）相同）是可以的，试试那里。

我的图表是这样的：

来源：S 目的地：G

他应该给出的路径是：SBDHFH F....（他应该找不到节点）因为他总是在某个点得到最低值 H 或 F。

这是我的代码：

我首先尝试将 IDDFS 应用到此图上，方法是先将其制成树形，结果是这样的：

我对路径中的那些重复节点感到困惑，我们可以消除它们还是它们会出现在最终路径中？

这是遍历图形以达到目标的正确方法吗？以及我们如何知道在图中接下来要访问哪个节点（例如，在树中，我们从左到右开始）。

如果我们在同一张图上应用 DFS 和 BFS，路径会是什么？

DFS 结果和 IDDFS 会有什么不同吗？好像很相似

我已经为 Java 中的 8 个难题问题实现了深度优先搜索（递归）：

我不知道我必须改变什么才能将其转换为迭代加深深度搜索。我知道深度没有限制，因为它在每一轮中都会增加。试过这个：

有谁知道如何将其更改为所需的IDS？先感谢您！

以下是 Ivan Bratko 通过他的书在 Prolog 中关于人工智能的示例：

“人工智能 Prolog 编程 - 第 3 版”（ISBN-13：978-0201403756）（Addison-Wesley 1986 年第 1 版，ISBN 0-201-14224-4）

我注意到很多示例没有运行完成，而是似乎卡住了。我已经尝试了几种不同的实现方式，但没有运气。有人愿意看一下代码，看看他们是否能发现逻辑错误或我是否犯了错误？

这是STRIPS 风格规划器的完整程序，用于块世界，如书中所示：

我添加了 7 个块和 4 个位置，并使用所有块按字母顺序在位置 1 上从 a 到 g 堆叠的表示进行了测试，目标是在位置 2 上以相同的顺序堆叠它们。

运行程序调用plan(StartState,GoalState, Sol).

参考：

• 移动的定义：http: //media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_2.txt
• 结束意味着具有目标回归的计划者：http: //media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt

任何建议将不胜感激。

我正在编写一个程序来玩点和盒子，我想通过在迭代深化方案中根据它们的启发式值排序我在 alphaBeta 中考虑的移动来提高我的时间效率。本质上，我想进入搜索树，增加每次迭代的深度，并使用 alphaBeta 评估每个节点。在每次连续迭代中，我考虑节点的顺序将由前一次迭代中节点的启发式值决定。但是，我无法理解这将如何实现。有人可以提供伪代码来说明标准 alphaBeta 程序如何适应使用迭代深化进行搜索吗？谢谢！

我正在尝试将此递归算法转换为迭代算法，它是 ida A* 算法（来自维基百科）。我已经实现了它，迭代版本不会返回与递归版本相同的结果。

第一次尝试