问题标签 [iterative-deepening]

好的，所以，首先，我不知道我在用迭代加深做什么。我一直在努力让这段代码工作，但我做不到。我在网上查看，在 C++ 中找不到此搜索的任何参考。

邻接矩阵的输出：

这是该图的方向版本：

是：

我从理论上知道搜索应该做什么，我可以在某种程度上告诉我我的搜索在做什么，但我不知道如何解决它。任何人都可以提供的任何帮助将不胜感激。

我有一个 Prolog 函数path(A,B,Path)，它产生板上从 A 到 B 的所有有效路径。

此函数的输出如下所示：

等等等等

它生成包含有效路径的无限列表集。我只是想获得这些路径中最短的路径（不管有多少）。也就是说，我想要一个shortest(A,B,Path)能够在板上产生从 A 到 B 的最短有效路径的函数。

我想要的输出是：

我一直在使用setofProlog 中的函数来将所有路径绑定到我对其施加一些长度限制的集合，但我还没有让它工作。

到目前为止，我糟糕的工作看起来像这样。这绝对是错误的，我将不胜感激任何帮助理解如何setof工作以及如何从这组中找到最短的列表。谢谢！

似乎迭代加深搜索应该比 BFS 具有更高的渐近时间复杂度，因为每次增加深度限制时，它都必须从头开始搜索。

但是wiki说不然，为什么？

我有一个算法，它可能会运行无限时间，并在运行时更新结果。它使用类似于Iterative Deepening Search的东西。在指定的时间后，我希望算法停止，这样我就可以使用它一直在计算的结果。

这是我如何使用线程完成此操作的示例：

有没有更好的方法在 Ruby 中对算法进行时间限制？

更新

性能是一个关键因素。

我正在尝试实现状态空间图的深度优先迭代深化搜索。我有一个包含三个顶点的图，它们是两个激活边和两个抑制边。每个节点都有一个二进制值，这就是图的状态。该图可以通过查看其中一个节点是高于阈值还是低于阈值（通过对所有传入节点求和来计算）转换到新状态。每次转换最多会改变一个节点。由于它们是三个节点，因此它们是三个状态转换边，将每个状态留在状态转换图中。

我认为我的 state_change/3 工作正常，例如我可以查询：

它给了我三个正确的答案：

我正在尝试使用 Bratkos Prolog for AI book 中给出的谓词 id_path，这是问题 11.3 的解决方案，但我在使用/调整它时遇到问题。 我想创建从起始节点到其他节点的路径，而不会进入循环 - 我不希望它有重复元素或在路径不存在时卡住。我想让路径说起始状态，然后您可以从起始状态访问一系列状态。如果有一个自我循环，我希望每一种到达那里的方式都包含一次。即我想跟踪我到达状态空间的方式，并使其独一无二，而不仅仅是状态空间在路径中是唯一的。

例如，从 011 开始，我希望用弧线找到长度为 1 的所有三个路径。

然后在下一级所有具有三个节点的路径，显示它需要到达节点的两条弧，然后在下一级，所有具有四个节点的路径显示它需要的三个弧等

如果这有帮助，我也将我的代码放入 SWISH 中？（第一次尝试这个？！）

http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&togetherjs=xydMBkFjQR

根据分支因子“b”和最浅目标深度“d”，迭代深化深度优先搜索和广度优先搜索生成的节点总数是多少

我正在尝试在二维数组（迷宫）中实现迭代深化搜索。

这是我使用堆栈进行的有限深度优先搜索。由于某种原因，它在两个单元格之间来回移动。它没有像应有的那样扩展。我认为我的 DFS 算法有问题。

我对堆栈没有太多经验，我对在哪里推送它以及在哪里弹出感到困惑。如果这里有人能指出我正确的方向，那就太好了！

BFS 需要O(b^d)内存，而已知 IDDFS 只在O(bd)内存中运行。但是，当我分析这两种实现时，它们使用的 RAM 数量完全相同——我错过了什么？

我正在使用Tree具有分支因子或 10 的类来运行测试：

我的实现iddfs：

BFS是

代码实际上并没有做任何事情，只是循环遍历整个树。我正在使用https://github.com/fabianp/memory_profiler来分析代码。

我正在尝试编写一个可以解决魔方的haskell程序。首先我尝试了这个，但没有找到避免编写大量代码的方法，所以我尝试使用 IDA* 搜索这个任务。

但我不知道这里哪种启发式方法合适：我尝试将问题划分为子问题，并测量距离处于简化状态的距离，但结果令人失望：程序无法减少从标准立方体移动三步的立方体在合理的时间内。我尝试测量边缘的一部分，然后对它们求和，或者使用最大值......但这些都不起作用，结果几乎相同。

所以我想知道代码的问题是什么：我使用的启发式是不可接受的吗？还是我的代码导致了一些我没有检测到的无限循环？或两者？以及如何解决这个问题？代码（相关部分）如下：

我知道这个启发式是不一致的，但不确定它是否真的可以接受，也许问题是它的不可接受性？

任何想法，提示和建议都非常感谢，在此先感谢。

为了通过 Alpha-Beta 剪枝提高 Minimax 算法的性能，我实现了迭代深化：

where 方法iterativeDeepening只返回最佳移动的 id。

首先，我不确定这是否是实现迭代深化的正确方法。

其次，我注意到人工智能开始做出错误的动作。迭代深化是否可能影响决策？

在使用转置表和迭代深化时，我测量了算法速度的显着改进，但我真的不想为了速度而牺牲 AI 质量。