我在理解 AI(人工智能)中使用的一些搜索算法时遇到了一些困难。
- A* 之间的确切区别是什么？和 IDA* (Iterative Deeping A Star) ？只是启发式功能吗？如果是这样，我仍然无法想象 IDA* 是如何工作的……:/
- IDA*是否与BFS (Breadth-First search)相同？ (当扩展的深度只有 1 级时，我的意思是 - 只是“向下”移动一级，IDA* 和 BFS 之间有什么区别吗)<
- 是IDDFS (Iterative-Deeping Depth-First Search)与IDA*相同，除了启发式函数(相当于IDDFS中的0)
- IDDFS 到底是什么 - 向下移动一个级别，然后使用 DFS (Depth-First Search) ？如果是这样，那么很多状态的计算(扩展)比一个多得多。或者它是这样的 - 使用具有特定深度的 DFS，然后存储“叶子”(最后扩展的节点) ，并遍历它们以再次使用 DFS(实际上是 BFS？)
- “迭代”从何而来？如我所见，IDDFS 根本不是迭代的，它仍然是递归的，只是混合了 BFS 和 DFS？还是我错了？或者这个“迭代”与递归的对立面无关？
- IDA* 的“迭代”是什么？
能否请您提供一些示例？我整天都在阅读这些算法，我知道它们的优缺点、复杂性等，但我就是找不到任何好的例子(除了 A*；我知道 BFS 和 DFS，其他的让我很烦)。我在不同的地方找到了一些 IDA* 的伪代码，但它们完全不同。
示例将是理解算法的最佳方式..但我找不到。即使在 TopCoder我没有找到任何关于 IDA* 的信息。
我已经阅读了 wiki 文章并且正在寻找新的东西 (:
非常感谢!
编辑: Here some nice articles , 但它们太理论化了。没有例子，没有任何具体的事情。但还是很有用的。我会推荐他们 (=
最佳答案
让我们从迭代加深深度优先搜索开始。
想法是深度优先搜索是高效的，但不一定会很快找到正确答案。所以，做一个深度为 1 的 DFS。如果你还没有找到答案，就做一个深度为 2 的 DFS。重复直到你找到答案，或者决定放弃。这会自动为您提供搜索树上的最短路径，因为如果存在长度为 N 的路径，您永远不会搜索长度为 N + 1 的路径。
你需要做的是改变深度优先搜索，使其深入 N 个节点(即，如果深度为 N，则不要生成新节点)，并用递增的 N 调用它。你除了 N 的值以及您为 DFS 所做的任何操作之外，不要存储任何内容。
迭代伴随着迭代增加搜索深度。如果分支因子大于 2，则性能可能出奇地好，因为在这种情况下，深度有界 DFS 的大部分成本都处于所达到的最低水平。
首先学习迭代深化 DFS，然后将其应用于 IDA*。我在 15 多年前读过一篇关于这些搜索的早期 Korf 论文，但不记得 IDA* 是如何很好地工作的，但你的主要问题是你一开始就不了解迭代加深。
关于algorithm - 需要一些帮助来理解搜索算法(A*、IDA*、DFS、BFS、IDDFS 等)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4381902/