需要一些帮助来了解搜索算法（A*，IDA*，DFS，BFS，IDDFS等）

Question

我有一些麻烦理解AI（人工智能）中使用的一些搜索算法。

• 确切的区别是什么 一个* 和 ida*（迭代深处一颗星星）？只是启发式功能吗？如果是这样，我仍然无法想象IDA*如何工作..：/
• 是 ida* 与 BFS（广度优先搜索） （当扩展的深度仅为1级时，我的意思是 - 仅移动一个级别的“向下”，是否有任何区别 ida* 和 BFS)
• 是 IDDFS（迭代深度深度搜索） 与 ida*, ，除了启发式功能（等于0 IDDFS)
• 到底是什么 IDDFS - 向下移动 只有一个 等级，然后使用 DFS（深度优先搜索）？如果是这样，这样，许多状态的计算（扩展）远远超过了。或者是这样 - 使用 DFS 具有特定的深度，然后存储“叶子”（最后一个扩展的节点），然后遍历它们以使用 DFS 再次（实际上是 BFS?)
• 在哪里 ”迭代“来了？正如我所看到的， IDDFS 根本不是迭代的，它仍然是递归的，只是混合 BFS 和 DFS？还是我错了？或这个 ”迭代“与递归相反无关吗？
• 什么是 ”迭代“ 为了 ida* ?

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

示例将是理解算法的最佳方法。但是我找不到。即使在 Topcoder 我什么都没找到有关ida*的东西。

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

非常感谢！

---

编辑： 在这里一些不错的文章, ，但它们太理论上了。没有例子，没有任何特定的事情。但仍然非常有用。我会推荐他们（=

Answer 1

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

这个想法是，深度优先的搜索是有效的，但不一定会很快在任何时候取得正确的答案。因此，将DFS达到1的深度1。如果您没有找到答案，请将其深度为2。重复直到找到答案或决定放弃。这会自动为您提供搜索树上的最短路径，因为如果有长度n，则永远不会搜索长度n + 1的路径。

您需要做的是要更改深度优先的搜索，以便它会深入nodes（即，如果您深度为n，请不要生成新的节点），并以增加N。存储除n的价值以及您为DFS所做的任何内容的任何内容。

迭代迭代地增加了搜索的深度。鉴于分支因子大于两个，这种性能可能会出奇地好，因为在这种情况下，大多数深度结合DFS的成本都达到最低水平。

首先学习迭代加深DFS，然后将其应用于IDA*。我在十五年前就读过有关这些搜索的早期论文，但不记得IDA*的运作良好，但是您的主要问题是您首先不了解迭代性的加深。