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

发布于 10-06 12:07 字数 1703 浏览 8 评论 0原文

我在理解人工智能(AI)中使用的一些搜索算法时遇到了一些困难。

  • A*IDA*(迭代深度A星)?只是启发式函数吗?如果是这样,我仍然无法想象 IDA* 是如何工作的.. :/
  • IDA*BFS(广度优先搜索)(当扩展深度仅为 1 级时,我的意思是 - 仅“向下”一层一层地移动, IDA*BFS 之间有什么区别吗?
  • IDDFS(迭代深度深度优先搜索)IDA*相同,除了启发式函数(相当于中的0) IDDFS
  • IDDFS到底是什么 - 向下移动仅一个级别,然后使用DFS(深度优先搜索)?如果是这样,通过这种方式,许多状态的计算(扩展)远多于状态。或者就像这样 - 使用具有特定深度的DFS,然后存储“叶子”(最后扩展的节点) ,并迭代它们以再次使用DFS(这实际上是BFS?)
  • “迭代”从何而来?正如我所见,IDDFS根本不是迭代的,它仍然是递归的,只是混合了BFSDFS?还是我错了?或者这个“迭代”与递归的反面无关?
  • 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

枫林﹌晚霞¤2024-10-13 12:07:14

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

这个想法是深度优先搜索是有效的,但不一定很快就能找到正确的答案。因此,执行 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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文