问题描述
我不明白 IDA* 如何节省内存空间.从我理解的IDA* 是A* 迭代深化.
A* 和 IDA* 使用的内存量有什么区别.
IDA* 的最后一次迭代不会与 A* 的行为完全一样并使用相同数量的内存.当我跟踪 IDA* 时，我意识到它还必须记住低于 f(n) 阈值的节点的优先级队列.
我知道 ID-Depth 优先搜索有助于深度优先搜索，因为它允许它像搜索一样进行广度优先搜索，而不必记住每个节点.但我认为 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:
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* 算法的重点是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！