IDA *与A *算法的区别是什么 [英] What is the point of IDA* vs A* algorithm

问题描述

我不明白 IDA * 如何节省内存空间。
据我了解， IDA * 是 A * ，而且迭代式加深。

A * 使用的内存量与 IDA *之间的内存量有什么区别 code>。





IDA *的最后迭代不是的行为c> A * 并使用相同数量的内存。当我跟踪 IDA * 时，我意识到它还必须记住 f（n）阈值。

我了解ID深度优先搜索通过允许深度优先搜索来帮助深度优先搜索，而不必记住每个节点。但是我认为 A * 的行为首先像深度一样，因为它忽略了沿途的一些子树。迭代加深如何使其使用更少的内存？

另一个问题是通过深度加深进行迭代加深的优先搜索，您可以通过使其像宽度一样先找到最短路径。但是 A * 已经返回最佳的最短路径（假设启发式是可以接受的）。迭代深化如何提供帮助。我觉得IDA *的最后一次迭代与 A * 相同。

解决方案

在 IDA * 中，与 A * 不同，您不需要保留一组暂定节点您打算访问，因此，您的内存消耗仅专用于递归函数的局部变量。

尽管此算法的内存消耗较低，但是它有自己的算法缺陷：

与A *不同，IDA *不利用动态编程，因此经常会多次探索相同的节点。

在 A * 算法中所有节点及其周围的节点都需要包含在需要访问列表中，而在 IDA * 中，到达节点后懒惰地获得下一个节点预览节点，因此您无需将其包含在额外的集合中。

如评论中所述，

I don't understand how IDA* saves memory space. From how I understand IDA* is A* with iterative deepening.

What's the difference between the amount of memory A* uses vs IDA*.

Wouldn't the last iteration of IDA* behave exactly like A* and use the same amount of memory. When I trace IDA* I realize that it also has to remember a priority queue of the nodes that are below the f(n) threshold.

I understand that ID-Depth first search helps depth first search by allowing it to do a breadth first like search while not having to remember every every node. But I thought A* already behaves like depth first as in it ignores some sub-trees along the way. How does Iteratively deepening make it use less memory?

Another question is Depth first search with iterative deepening allows you to find the shortest path by making it behave breadth first like. But A* already returns optimal shortest path (given that heuristic is admissible). How does iterative deepening help it. I feel like IDA*'s last iteration is identical to A*.

解决方案

In IDA*, unlike A*, you don't need to keep a set of tentative nodes which you intend to visit, therefore, your memory consumption is dedicated only to the local variables of the recursive function.

Although this algorithm is lower on memory consumption, it has its own flaws:

Unlike A*, IDA* doesn't utilize dynamic programming and therefore often ends up exploring the same nodes many times. (IDA* In Wiki)

The heuristic function still needs to be specified for your case in order to not scan the whole graph, yet the scan's memory required in every moment is only the path you are currently scanning without its surrounding nodes.

Here is a demo of the memory required in each algorithm:

In the A* algorithm all of the nodes and their surrounding nodes needs to be included in the "need to visit" list while in the IDA* you get the next nodes "lazily" when you reach its previews node so you don't need to include it in an extra set.

As mentioned in the comments, IDA* is basically just IDDFS with heuristics:

这篇关于IDA *与A *算法的区别是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！