8

我在理解 AI（人工智能）中使用的一些搜索算法时遇到了一些麻烦。

  • A*和IDA* (Iterative Deeping A Star)之间的确切区别是什么？仅仅是启发式函数吗？如果是这样，我仍然无法想象 IDA* 是如何工作的……：/
  • IDA*是否与BFS（广度优先搜索）相同（当扩展深度仅为 1 级时，我的意思是 - 仅“向下”一层一层地移动，IDA*和BFS之间有什么区别）
  • IDDFS (Iterative-Deeping Depth-First Search)是否与IDA*相同，除了启发式函数（相当于IDDFS中的 0 ）
  • IDDFS到底是什么——只向下移动一层，然后使用DFS（深度优先搜索）？如果是这样，那么通过这种方式计算（扩展）的状态远远多于状态。或者就像这样 - 使用具有特定深度的DFS，然后存储“叶子”（最后扩展的节点），并遍历它们以使用再次DFS（实际上，它是BFS吗？）
  • “迭代”从何而来？如我所见，IDDFS根本不是迭代的，它仍然是递归的，只是混合了BFS和DFS？还是我错了？或者这个“迭代”与递归的反义词无关？
  • 什么是IDA*的“迭代” ？

请您提供一些例子吗？我整天阅读这些算法，我知道它们的优缺点、复杂性等，但我就是找不到任何好的例子（除了 A*；我知道 BFS 和 DFS，其他的困扰我）。我在不同的地方找到了一些 IDA* 的伪代码，但它们都完全不同。

示例将是理解算法的最佳方式..但我找不到。即使在TopCoder中，我也没有找到任何关于 IDA* 的信息。

我已经阅读了 wiki 文章，并且正在寻找新的东西（：

非常感谢！

编辑： 这里有一些不错的文章，但它们太理论化了。没有例子，没有任何具体的东西。但还是很有用的。我会推荐他们（=

4

1 回答 1

4

让我们从迭代深化深度优先搜索开始。

这个想法是深度优先搜索是有效的，但不一定会很快找到正确的答案。所以，做一个深度为 1 的 DFS。如果你还没有找到答案，那么做深度为 2。重复直到你找到答案，或者决定放弃。这会自动为您提供搜索树上的最短路径，因为如果存在长度为 N 的路径，您永远不会搜索长度为 N + 1 的路径。

您需要做的是更改深度优先搜索，使其深入 N 个节点（即，如果您的深度为 N，则不要生成新节点），并以增加 N 的方式调用它。您不需要存储除 N 的值之外的任何内容以及您为 DFS 所做的任何事情。

迭代伴随着迭代地增加搜索深度。如果分支因子大于 2，性能可能会非常好，因为在这种情况下，深度有界 DFS 的大部分成本都处于最低水平。

首先学习迭代深化 DFS，然后将其应用于 IDA*。十五年前，我阅读了一篇关于这些搜索的早期 Korf 论文，不记得 IDA* 是如何工作的很好，但您的主要问题是您一开始就不了解迭代深化。

于 2010-12-07T22:07:47.393 回答