需要一些帮助来理解搜索算法（A*、IDA*、DFS、BFS、IDDFS 等）
我在理解人工智能（AI）中使用的一些搜索算法时遇到了一些困难。
- A* 和 IDA*（迭代深度A星）？只是启发式函数吗？如果是这样，我仍然无法想象 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* 的信息。
我已经阅读了维基文章，并且正在寻找新的东西（：
非常感谢！
编辑： 这里有一些不错的文章，但它们太理论化了。没有例子，没有任何具体的东西。但仍然非常有用。我推荐它们(=
I have some troubles understanding some of the algorithms for searching, used in AI (artificial intelligence).
- What is the exact difference between A* and IDA* (Iterative Deeping A Star)? Is just the heuristic function? If so, I still just can't imagine how IDA* works.. :/
- Is IDA* the same as BFS (Breadth-First search) (when the depth of expanding is just 1 level, I mean - moving just one by one level "down", is there any difference between IDA* and BFS)
- Is IDDFS (Iterative-Deeping Depth-First Search) the same as IDA*, except the heuristic function (which is equivalent to 0 in IDDFS)
- What exactly is IDDFS - moving down just one level, then using DFS (Depth-First Search)? If so, this way lots of the states are calculated (expanded) much more than ones.. Or it's like this - use DFS with particular depth, then store the "leaves" (the last expanded nodes), and iterate through them to use DFS again (which, actually, is BFS?)
- Where "iterative" comes from? As I see, IDDFS is not iterative at all, it's still recursiive, just mixes BFS and DFS? Or I'm wrong? Or this "iterative" has nothing to do with the opposite of recursion?
- What is "iterative" for IDA* ?
Could you, please, provide some examples? I read all day about these algorithms, I know their advantages and disadvantages, the complexity, etc., but I just couldn't find any good examples (except for A*; I know BFS and DFS, the others bother me). I found some pseudo-code for IDA* on different places, but they were all completely different.
Examples would be the best way to understand algorithms..but I can't find. Even in TopCoder I didn't find anything about IDA*.
I've read the wiki articles and I'm looking for something new (:
Thanks a lot!
EDIT: Here some nice articles, but they are too theoretical. No examples, no any specific things. But still very useful. I'd recommend them (=
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
让我们从迭代加深深度优先搜索开始。
这个想法是深度优先搜索是有效的，但不一定很快就能找到正确的答案。因此，执行 DFS 深度为 1。如果还没有找到答案，则执行深度为 2。重复直到找到答案，或者决定放弃。这会自动为您提供搜索树上的最短路径，因为如果存在长度为 N 的路径，则您永远不会搜索长度为 N + 1 的路径。
您需要执行的操作是更改深度优先搜索，以便它将深入 N 个节点（即，如果深度为 N，则不要生成新节点），并以递增的 N 来调用它。您不会存储超过 N 值的任何内容以及您为 DFS 所做的任何操作。
迭代伴随着迭代地增加搜索深度。如果分支因子大于 2，则性能可能会出奇的好，因为在这种情况下，深度受限 DFS 的大部分成本都达到了最低水平。
首先学习迭代深化 DFS，然后将其应用到 IDA*。我在十五年前读过一篇关于这些搜索的早期 Korf 论文，并且不记得 IDA* 是如何很好地工作的，但您的主要问题是您一开始就不理解迭代深化。
Let's start with iterative deepening depth-first search.
The idea is that depth-first search is efficient, but won't necessarily hit the right answer any time soon. So, do a DFS to a depth of 1. If you haven't found the answer, do it to a depth of 2. Repeat until you find the answer, or decide to give up. This automatically gives you the shortest path on the search tree, since you never search for a path of length N + 1 if there is one of length N.
What you need to do to implement is to change a depth-first search so it will go N nodes deep (i.e., don't generate new nodes if you're N deep), and call it with increasing N. You don't store anything more than the value of N and whatever you'd do for DFS.
The iteration comes with iteratively increasing the depth of search. The performance can be surprisingly good, given a branching factor greater than two, as in that case most of the cost of a depth-bounded DFS is at the lowest level reached.
Learn iterative deepening DFS first, then apply that to IDA*. I read an early Korf paper on these searches over fifteen years ago, and don't remember how IDA* works very well, but your main problem is that you don't understand iterative deepening in the first place.