迭代加深搜索 (IDS) 或迭代加深深度优先搜索 (IDDFS)

搜索算法是计算机科学和人工智能的重要组成部分。它们用于解决各种问题，从下棋和跳棋等游戏到在地图上找到最短路径。深度优先搜索 (DFS) 方法是最流行的搜索算法之一，它通过沿着每个分支尽可能远地搜索网络或树，然后在回溯。然而，DFS 有一个关键的缺点：如果图包含循环，它可能会陷入无休止的循环。利用迭代加深搜索 (IDS) 或迭代加深深度优先搜索 (IDDFS) 是解决此问题的一种技术。

什么是 IDS？

一种称为 IDS 的搜索算法结合了 DFS 和广度优先搜索 (BFS) 的优点。图使用 DFS 进行探索，但深度限制不断增加，直到找到目标。换句话说，IDS 不断运行 DFS，每次增加深度限制，直到获得所需结果。迭代加深是一种确保搜索是完整的（即，如果存在解决方案，它会找到解决方案）并且高效的（即，它会找到到达目标的路径最短）的方法。

IDS 的伪代码很简单

代码

IDS 是如何工作的？

iterativeDeepeningSearch 函数以根节点和目标节点作为输入，对图执行迭代加深搜索，直到达到目标或搜索空间用完。这是通过定期使用 depthLimitedSearch 函数来完成的，该函数对 DFS 应用深度限制。如果目标在任何深度处找到，搜索将结束并返回目标节点。如果搜索空间用完（直到深度限制的所有节点都已被检查），则搜索返回 None。

depthLimitedSearch 函数通过以节点、目标节点和深度限制作为输入，对具有指定深度限制的图执行 DFS。如果在当前深度处找到目标节点，则搜索返回 FOUND。如果达到深度限制但找不到目标节点，则搜索返回 NOT FOUND。如果任一条件都不满足，则搜索将迭代地继续到节点的后代。

程序

代码

输出

Path found

优点

• IDS 在多个方面优于其他搜索算法。第一个优点是它的完备性，这确保了如果搜索空间中存在解决方案，它就会被找到。这是因为 IDS 会进行深度受限的 DFS，它在提高深度限制之前会检查特定深度限制下的所有节点。
• IDS 的第二个优点是内存效率高。这是因为 IDS 不将搜索区域中的每个节点存储在内存中，从而减少了算法的内存需求。IDS 通过仅存储当前深度限制内的节点来最小化算法的内存占用。
• IDS 的第三个优点是它可用于树和图搜索。这是因为 IDS 是一种通用的搜索算法，它适用于任何搜索空间，包括树或图。

缺点

• IDS 的缺点是可能会多次访问某些节点，这可能会减慢搜索速度。完备性和最优性的好处通常会超过这个缺点。此外，通过使用内存或缓存等策略，可以最大限度地减少重复访问。