迭代深化A*算法

深度优先搜索和A*搜索的最大优点结合在启发式搜索算法中，称为A*算法(IDA*)。用最优搜索方法找到网络或树中起始状态和目标状态之间的最短路径。IDA*算法比A*算法使用更少的内存，因为它只是跟踪当前节点及其相关成本，而不是跟踪已检查的整个搜索空间。本文将研究IDA*算法的操作，以及它的优缺点和实际应用。

启发式搜索算法导论

为了确定问题的最佳解决方案，启发式搜索算法以一种有系统的方式探索搜索区域。他们被应用于许多领域，包括机器人、视频游戏和自然语言处理。启发式搜索算法利用启发式函数来评估当前状态与目标状态之间的距离，以确定从起始状态到目标状态的最短路径。有各种启发式搜索算法，包括A*搜索、统一代价搜索(UCS)、深度优先搜索(DFS)和广度优先搜索(BFS)。

A*搜索算法

A*搜索算法是一种著名的启发式搜索方法，它使用启发式函数计算当前状态与目标状态之间的距离。A*搜索法将起始节点到当前节点的实际代价和当前节点到目标节点的预测代价相加，确定每个节点的代价。估计当前节点和期望节点之间距离的启发式函数用于确定估计成本。然后，算法选择成本最低的节点，使其增长，并一直这样做，直到到达目标节点。

只要启发式函数是可接受且一致的，A*搜索算法就能保证找到到达目标节点的最短路径。这使它成为一种理想的搜索方法。如果启发式函数从不高估目标节点的距离，则认为它是可接受的。根据三角不等式，一致性启发式函数是当前节点到目标节点的估计代价小于等于实际代价加上下一个节点到目标节点的估计代价。

迭代深化A*算法

在内存利用率方面，IDA*算法优于A*搜索算法。通过A*搜索方法将整个检查的搜索空间保存在内存中，这对于大型搜索空间来说可能是内存密集型的。相反，IDA*方法只保存当前节点及其相关成本，而不是整个搜索区域。

为了探索搜索空间，IDA*方法采用深度优先搜索。从一个等于启发式函数从开始节点到目标节点的预期代价的阈值开始。之后，它通过从开始节点开始的深度优先搜索，扩展总价格小于或等于阈值的节点。如果目标节点被定位，该方法以最佳答案结束。如果超过阈值，该算法将阈值提高到未扩展节点的最小代价。一旦目标节点被定位，算法就会重复这个过程。

IDA*方法是全面和最优的，因为它总是找到最好的解决方案，如果存在，如果没有发现，它就停止搜索。该技术使用更少的内存，因为它只节省当前节点及其相关成本，而不是已经研究过的整个搜索空间。路由、调度和游戏是实际应用程序中经常使用IDA*方法的几个例子。

迭代深化A*算法(IDA*)

IDA*算法包括以下步骤:

• 从初始成本限制开始。

该算法从初始代价限制开始，通常设置为到达目标节点的最优路径的启发式代价估计。

• 在开销限制内执行深度优先搜索(DFS)。

该算法从起始节点开始执行DFS搜索，直到到达代价超过当前代价限制的节点。

• 检查目标节点。

如果在DFS搜索过程中找到目标节点，则算法返回到目标节点的最优路径。

• 更新成本限制。

如果在DFS搜索过程中没有找到目标节点，则算法将代价限制更新为在搜索过程中扩展的任何节点的最小代价。

• 重复这个过程，直到找到目标。

该算法重复这个过程，每次增加成本限制，直到找到目标节点。

示例实现

让我们看一个图的例子，看看迭代深化a * (IDA*)技术是如何工作的。假设我们有下图，其中括号中的数字表示节点之间的旅行费用:

我们希望使用IDA*算法找到从节点A到节点F的最优路径。第一步是设定初始成本限制。让我们使用最优路径的启发式估计，即7(从A到C再到F的成本总和)。

1. 设置开销限制为7。
2. 从节点A开始搜索。
3. 展开节点A，生成它的邻居B和C。
4. 评估从A到B和A到C路径的启发式代价，分别为5和10。
5. 由于到达B的路径的代价小于代价限制，所以继续从节点B开始搜索。
6. 展开节点B，生成它的邻居D和E。
7. 评估从A到D和A到E路径的启发式代价，分别为10和9。
8. 由于到D的路径的成本超过了成本限制，所以返回到节点B。
9. 求从A到C路径的启发式代价为10。
10. 由于到达C的路径的代价小于代价限制，所以继续从节点C开始搜索。
11. 展开节点C，生成它的邻居F。
12. 求从A到F路径的启发式代价，即7。
13. 由于到达F的路径的代价小于代价限制，返回最优路径，即A - C - F。

我们已经完成了，因为在初始定价范围内找到了理想路线。我们会将成本限制调整为在整个搜索过程中扩大的任何节点的最低成本，然后重复该过程，直到在成本限制内无法找到最佳路径的目标节点。

IDA*方法是一种强大且适应性强的搜索算法，可用于识别各种情况下的最佳行动方案。它有效地搜索巨大的状态空间，如果存在最优解，则通过结合DFS和A*搜索的优点来找到它。

优势

• 完备性:IDA*方法是一种完备搜索算法，这意味着，如果存在最优解，就会发现它。
• 内存效率:IDA*方法一次只在内存中保留一条路径，使其具有内存效率。
• 灵活性:根据应用程序的不同，可以将IDA*方法与许多启发式函数一起使用。
• 性能:IDA*方法有时优于其他搜索算法，如均匀代价搜索(UCS)或广度优先搜索(BFS) (UCS)。
• IDA*算法是增量的，这意味着它可以在任何时候停止，并在以后的时间继续，而不会丢失任何进展。
• 只要所使用的启发式函数是可接受的，IDA*方法总是会发现最佳解决方案(如果存在的话)。这意味着算法将始终选择直接通往目标节点的路由。

缺点

• 对于巨大的搜索区域无效。对于巨大的搜索空间来说，IDA*可能是难以置信的无效，这是它最大的缺点之一。由于IDA*在每次迭代中使用深度优先搜索来扩展相同的节点，这可能会导致重复计算。
• 被困在附近的最小值。IDA*陷入局部极小值的能力是另一个缺点。
• 非常依赖于启发式函数的有效性。所使用的启发式函数的有效性严重影响IDA*的性能。
• 尽管IDA*在一次只保存一条路径方面具有内存效率，但在某些情况下可能仍然需要使用大量内存。
• 局限于具有明确客观状态的问题。IDA*用于明确定义和可识别所需状态的问题。