IDA*与A*算法有什么关系？
tcu*_*222 11 algorithm a-star path-finding
我不明白如何IDA*节省内存空间.从我的理解IDA*是A*迭代加深.
什么是内存量之间的差额A*使用VS IDA*.
最后一次迭代的IDA*行为是否完全相同A*并且使用相同数量的内存.当我跟踪时,IDA*我意识到它还必须记住低于f(n)阈值的节点的优先级队列.
我知道ID-Depth第一次搜索有助于深度优先搜索,允许它首先像搜索一样进行广度,而不必记住每个节点.但我认为它的A*行为首先就像深度一样,因为它忽略了沿途的一些子树.迭代加深如何使用更少的内存？
另一个问题是使用迭代加深的深度优先搜索允许您通过使其首先表现为宽度来找到最短路径.但A*已经返回最佳最短路径(假设启发式是可接受的).迭代加深如何帮助它.我觉得IDA*的最后一次迭代与之相同A*.
Tam*_*red 11
与之IDA*不同的是A*,您不需要保留一组您打算访问的暂定节点,因此,您的内存消耗仅专用于递归函数的局部变量.
虽然这种算法的内存消耗较低,但它有自己的缺陷:
与A*不同,IDA*不使用动态编程,因此通常最终会多次探索相同的节点.(IDA*在Wiki中)
仍然需要为您的案例指定启发式函数,以便不扫描整个图形,但每个时刻所需的扫描内存只是您当前正在扫描而没有其周围节点的路径.
以下是每种算法所需内存的演示:
在A*算法中,所有节点及其周围节点都需要包含在"需要访问"列表中,而IDA*当您到达其预览节点时,您将"懒洋洋地"获取下一个节点,因此您无需将其包含在额外的一套.
正如评论中所提到的,IDA*基本上只是IDDFS启发式:
- 但是IDA*不是还需要存储它打算访问的节点吗，因为它仍然在回溯，并且在回溯时它想要找到下一步的最佳路径。A*需要存储节点，IDA*不是和A*一样但是你在某个f(n)之后停止并重新启动吗？您是说 IDA* 只是 IDDFS，除了启发式方法之外。因为低于阈值的所有节点都被平等对待，并且只要所有子节点的 f(n) 都低于阈值，访问节点的子节点就不是按特定顺序？ (2认同)