需要一些帮助来理解搜索算法(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 (=
让我们从迭代加深深度优先搜索开始。
这个想法是深度优先搜索是有效的,但不一定很快就能找到正确的答案。因此,执行 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.