需要一些帮助来理解搜索算法(A*,IDA*,DFS,BFS,IDDFS等)

Question

我在理解用于AI(人工智能)的一些搜索算法时遇到了一些麻烦.

• A*和IDA*(Iterative Deeping A Star)之间的确切区别是什么？只是启发式功能？如果是这样,我仍然无法想象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*的信息.

我已经阅读了维基文章,我正在寻找新的东西(:

非常感谢!

---

编辑: 这里有一些很好的文章,但它们太理论化了.没有例子,没有任何具体的东西.但仍然非常有用.我推荐他们(=

Answer 1

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

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

您需要做的就是更改深度优先搜索，使其深入 N 个节点（即，如果深度为 N，则不会生成新节点），并以递增的 N 来调用它。您不需要存储超过 N 值的任何内容以及您为 DFS 所做的任何操作。

迭代伴随着迭代地增加搜索深度。如果分支因子大于 2，则性能可能会出奇的好，因为在这种情况下，深度受限 DFS 的大部分成本都达到了最低水平。

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