蓝桥杯第十五届抱佛脚（五）DFS、BFS及IDS

本文主要是介绍蓝桥杯第十五届抱佛脚（五）DFS、BFS及IDS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥杯第十五届抱佛脚（五）DFS、BFS及IDS

深度优先搜索

DFS(Depth-First Search)即深度优先搜索,是一种用于遍历或搜索树或图的算法。它从根节点开始,尽可能沿着每一条路径直到这条路径最后一个节点被访问了,然后回退,继续访问下一条路径。它的基本思想是尽可能深地搜索树的分支，直到达到叶子节点，然后回溯到上一个分支节点继续搜索。DFS通常使用递归或栈来实现。

DFS遍历树

对于一棵树,深度优先遍历的过程可以分为以下几个步骤:

1. 访问根节点

   • 首先访问树的根节点,通常是输出或处理根节点的值。

2. 遍历左子树

   • 接下来对根节点的左子树进行深度优先遍历。
   • 如果左子树非空,则递归地去遍历左子树。
   • 直到遍历到左子树的最后一个节点为止(即左子树的叶子节点)。

3. 回溯到父节点

   • 当左子树遍历完成后,就会回溯到父节点。

4. 遍历右子树

   • 然后对根节点的右子树进行深度优先遍历。
   • 如果右子树非空,则递归地去遍历右子树。
   • 直到遍历到右子树的最后一个节点为止(即右子树的叶子节点)。

5. 回溯结束

   • 当左右子树都被遍历完成后,此时整棵树也就被完全遍历了。

根据根节点、左子树和右子树被访问的先后顺序不同,深度优先遍历树可分为三种方式:

1. 先序遍历(Preorder Traversal)
   • 先访问根节点,再先序遍历左子树,最后先序遍历右子树。
   • 遍历顺序: 根->左子树->右子树
2. 中序遍历(Inorder Traversal)
   • 先中序遍历左子树,再访问根节点,最后中序遍历右子树。
   • 遍历顺序: 左子树->根->右子树
3. 后序遍历(Postorder Traversal)
   • 先后序遍历左子树,再后序遍历右子树,最后访问根节点。
   • 遍历顺序: 左子树->右子树->根

下面是一个后序遍历二叉树的Java代码示例:

void postOrder(TreeNode root) {if (root == null)return;// 访问优先级：左子树 -> 右子树 -> 根节点postOrder(root.left);postOrder(root.right);list.add(root.val);
}

通过调整访问根节点的位置,我们就可以实现中序和后序遍历。

深度优先遍历树的关键在于每次递归处理完当前节点后,就去遍历其子节点,直到遍历到叶子节点为止。这样通过不断地深挖,最终就可以遍历完整棵树。回溯到父节点时,表示当前子树已经被完全访问过了。

DFS设计原则和原理

1. 递归思想

DFS本质上是一种递归算法。它通过不断地递归调用自身,沿着树或图的每条路径尽可能深入,直到走到底才回溯。因此,在设计DFS算法时,需要贯彻递归思想,将问题分解为多个子问题来求解。

2. 明确终止条件

为了避免无限递归,必须明确定义递归的终止条件。常见的终止条件包括:当前节点为空、当前节点已被访问过、到达目标节点等。当递归到达终止条件时,递归函数应当终止并返回。

3. 延迟绑定

延迟绑定的思想要求在扩展当前节点之前,先去访问当前节点。这样可以保证在遇到终止条件时,当前节点已经被访问过了。DFS在访问一个节点后,再去递归访问它的邻居节点,符合延迟绑定的原则。

4. 记录状态

为避免重复访问,需要在遍历过程中记录节点的状态(是否被访问过)。常用的方法是使用标记数组或者哈希表来存储节点的访问状态。

5. 剪枝优化

在某些情况下,可以根据问题的特点,给出一些剪枝条件。当遍历到某个节点时,如果发现没必要继续遍历它的子节点,就可以直接剪掉,从而减少无效遍历,提高算法效率。

DFS 的设计步骤

当使用深度优先搜索（DFS）解题时，通常遵循以下步骤：

1. 确定题目的状态（包括边界）：

• 确定问题的状态，即图或树的节点表示什么。这些节点可以表示位置、状态、对象等。
• 确定边界条件，包括起始节点、目标节点、可行动作、约束条件等。

2.找到状态转移方式：

• 确定节点之间的关系和转移方式。在图或树中，这可能是节点之间的连接关系、可行的移动方式等。
• 确定如何从一个状态转移到另一个状态。这可能涉及到在状态空间中进行搜索、遍历或移动。

3.找到问题的出口，计数或者某个状态：

• 确定问题的终止条件，即找到目标节点、达到目标状态或满足特定条件。
• 如果是计数问题，确定如何计数满足条件的节点或路径等。

4. 设计搜索：

• 根据问题的性质选择深度优先搜索算法。
• 根据问题的具体要求，设计搜索的过程，包括如何初始化数据结构、如何遍历状态空间、如何更新状态等。
• 在搜索过程中，使用递归或显式栈来实现DFS。
• 在每一步中，探索当前节点的所有可能的邻居节点，并递归调用DFS来继续探索。
• 在递归调用的过程中，确保合理处理状态的标记和状态的恢复，以避免死循环或错误结果。

通过以上步骤，可以设计出正确且高效的DFS算法来解决问题。在实际应用中，DFS通常用于寻找所有可能的解决方案或路径，或者用于搜索状态空间中的特定状态。

DFS模板

递归版本:

• 首先判断当前节点是否满足终止条件,如果满足则直接返回。
• 然后执行一些操作,例如处理当前节点的值或状态。
• 将当前节点标记为已访问。
• 递归遍历所有未被访问的相邻节点。
• 在递归返回时,可以执行一些回溯操作,如恢复之前的状态。

void dfs(Node node, /* 其他参数 */) {// 终止条件if (/* 越界或达到终止状态 */) {return;}// 做一些操作// ...// 访问当前节点visited.add(node);// 遍历所有相邻节点for (Node neighbor : getNeighbors(node)) {if (!visited.contains(neighbor)) {dfs(neighbor, /* 其他参数 */);}}// 可选的回溯操作// ...
}

非递归版本:

• 使用一个栈和一个集合,分别存储待访问节点和已访问节点。
• 先将起始节点压入栈中。
• 每次从栈中弹出一个节点,如果该节点未被访问,则执行相应操作,并将它所有未访问过的相邻节点压入栈中。
• 重复上述步骤,直到栈为空。

void dfs(Node start, /* 其他参数 */) {Stack<Node> stack = new Stack<>();Set<Node> visited = new HashSet<>();stack.push(start);while (!stack.isEmpty()) {Node node = stack.pop();if (visited.contains(node)) {continue;}// 做一些操作// ...visited.add(node);// 将所有未访问过的相邻节点加入栈for (Node neighbor : getNeighbors(node)) {if (!visited.contains(neighbor)) {stack.push(neighbor);}}}
}

这两种实现方式都需要获取当前节点的相邻节点,这个操作由 getNeighbors 函数完成,具体实现取决于问题的数据结构。

DFS 例题

二叉树的最大深度

输入：root = [3,9,20,null,null,15,7]
输出：3

输入：root = [1,null,2]
输出：2

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}

相同的树

输入：p = [1,2,3], q = [1,2,3]
输出：true

输入：p = [1,2], q = [1,null,2]
输出：false

输入：p = [1,2,1], q = [1,1,2]
输出：false

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null){return true;}else if(p == null || q == null){return false;}else if(p.val != q.val){return false;}else{return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}}
}

求根节点到叶节点数字之和

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

class Solution {int totalSum = 0;public int sumNumbers(TreeNode root) {if(root == null) return 0;dfs(root, 0);return totalSum;}private void dfs(TreeNode node, int currentSum) {// 如果当前节点为空，则返回if(node == null) return;// 更新当前累积和currentSum = currentSum * 10 + node.val;// 如果当前节点是叶子节点，则将当前累积和加到totalSum中if(node.left == null && node.right == null) {totalSum += currentSum;return;}// 递归处理当前节点的左右子节点dfs(node.left, currentSum);dfs(node.right, currentSum);}
}

广度优先搜索

BFS(Breadth-First Search)即广度优先搜索,是一种用于遍历或搜索树或图的算法。它的基本思想是从根节点开始，逐层地向外扩展搜索，直到找到目标节点或遍历完所有节点。BFS通常使用队列来实现。

BFS遍历树

广度优先搜索树的构建过程通常按照以下步骤进行：

1. 初始化：将起始节点放入队列，并标记为已访问。
2. 循环处理队列：重复以下步骤直到队列为空。
   • 从队列中取出一个节点。
   • 对于该节点的每个未被访问过的相邻节点：
     • 将相邻节点加入队列。
     • 标记相邻节点为已访问。
     • 将当前节点作为相邻节点的父节点（用于构建搜索树）。
3. 构建搜索树：在处理过程中记录节点的父节点关系，以构建搜索树。
4. 结束：当队列为空时，搜索结束。

例题：二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

思路分析：

题目要求我们一层一层输出树的结点的值，很明显需要使用「广度优先遍历」实现；

广度优先遍历借助「队列」实现；

注意：

• 这样写 for (int i = 0; i < queue.size(); i++) { 代码是不能通过测评的，这是因为 queue.size() 在循环中是变量（ Python 除外）。

• 正确的做法是：每一次在队列中取出元素的个数须要先暂存起来；子结点入队的时候，非空的判断很重要：在队列的队首元素出队的时候，一定要在左（右）子结点非空的时候才将左（右）子结点入队。

具体步骤如下：

1. 首先将根节点放入队列中。

2. 从队列中取出一个节点，并访问它。

3. 将该节点的左右子节点（如果存在）依次放入队列中。

4. 重复步骤2和步骤3，直到队列为空。

层序遍历的过程可以用以下伪代码表示：

层序遍历(root):如果根节点为空，直接返回创建一个空队列将根节点放入队列中当队列不为空时，执行以下循环：从队列中取出一个节点node访问节点node如果节点node有左子节点，将左子节点放入队列中如果节点node有右子节点，将右子节点放入队列中

以下是添加了关键注释的Java示例代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class LevelOrderTraversal {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result; // 如果根节点为空，直接返回空结果列表}Queue<TreeNode> queue = new LinkedList<>(); // 创建一个队列用于层序遍历queue.offer(root); // 将根节点入队while (!queue.isEmpty()) { // 循环直到队列为空int levelSize = queue.size(); // 当前层的节点数量List<Integer> currentLevel = new ArrayList<>(); // 当前层的节点值列表// 处理当前层的所有节点for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll(); // 出队一个节点currentLevel.add(node.val); // 将节点值添加到当前层列表// 将节点的左右子节点（如果存在）加入队列if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}result.add(currentLevel); // 将当前层的节点值列表添加到结果列表中}return result; // 返回层序遍历结果}public static void main(String[] args) {// 创建一棵示例二叉树//       3//      / \//     9  20//       /  \//      15   7TreeNode root = new TreeNode(3);root.left = new TreeNode(9);root.right = new TreeNode(20);root.right.left = new TreeNode(15);root.right.right = new TreeNode(7);// 进行层序遍历LevelOrderTraversal traversal = new LevelOrderTraversal();List<List<Integer>> result = traversal.levelOrder(root);System.out.println(result); // 输出: [[3], [9, 20], [15, 7]]}
}

这段代码对二叉树的层序遍历进行了注释说明，包括了算法的关键步骤和数据结构的使用。

1. 基本过程
   • 首先将要被访问的搜索根节点放入队列中。
   • 从队列中取出一个节点进行访问,并且将它所有未曾访问过的邻接节点放入队列。
   • 重复上述过程,直到队列为空。
2. 实现方式
   • 利用队列这种数据结构,先进先出的顺序对节点进行访问。
   • 需要使用一个额外的集合(如Set)来记录已访问过的节点,避免重复访问。
3. 遍历特点
   • 从根节点开始依次按层次遍历整个图/树。
   • 无论目标节点离根节点有多远,BFS都可以找到长度最小的路径。
   • 使用队列先进先出的顺序保证离根节点最近的节点先被访问。
4. 应用场景
   • 求最短路径(BFS可以找到从起点到终点的最短路径)
   • 在棋盘游戏中找到最少移动步数
   • 解决迷宫问题
   • 二叉树的层次遍历
   • 遍历图的连通分量
5. 复杂度分析
   • 时间复杂度：O(V+E)，其中V为顶点个数,E为边数
   • 空间复杂度：O(V)，最坏情况下需要存储所有顶点
6. 优缺点
   • 优点:可以找到目标节点到源节点的最短路径; 算法简单,易于理解和实现
   • 缺点:对于无解的情况,会遍历整个树/图,无法及时停止;较大的树/图会占用较多内存空间

下面是一个Java代码示例,对一个无向图进行BFS遍历:

// 使用邻接表存储图结构
Map<Integer, List<Integer>> graph = new HashMap<>();void bfs(int start) {Queue<Integer> queue = new LinkedList<>();Set<Integer> visited = new HashSet<>();// 将起点加入队列和visitedqueue.offer(start);visited.add(start);while (!queue.isEmpty()) {int node = queue.poll();System.out.print(node + " "); // 访问当前节点// 将当前节点的所有未访问邻居加入队列for (int neighbor : graph.get(node)) {if (!visited.contains(neighbor)) {queue.offer(neighbor);visited.add(neighbor);}}}
}

这段代码首先从起始节点 start 开始,将其放入队列并标记为已访问。然后不断从队列中取出一个节点,访问它,并将它所有未访问过的邻接节点放入队列。重复这个过程直到队列为空。

BFS设计原则和原理

设计原则：

1. 广度优先：BFS 的核心思想是从起始节点开始，逐层地探索图或树的节点，即先访问当前节点的所有邻居节点，然后再访问邻居节点的邻居节点，以此类推，直到找到目标节点或者遍历完整个图/树。

2. 利用队列：BFS 使用队列来存储待访问的节点。从起始节点开始，先将起始节点加入队列，然后依次处理队列中的节点，并将它们的邻居节点加入队列。这样能够保证按照广度优先的顺序进行搜索。

原理：

1. 节点访问：从起始节点开始，首先将其加入队列，并标记为已访问。然后，从队列中取出一个节点，访问该节点，并将其未被访问过的邻居节点加入队列。重复这个过程，直到队列为空。

2. 标记已访问节点：为了防止重复访问节点，需要在访问节点时对其进行标记。通常使用布尔数组或哈希集合来记录已访问的节点。

3. 最短路径：由于BFS的特性，它能够保证找到的路径是最短路径。因为BFS会按照距离递增的顺序逐层访问节点，所以当找到目标节点时，其所在层级就是最短路径的长度。

4. 应用：BFS可以用于解决很多问题，比如寻找两个节点之间的最短路径、无权图的最短路径问题、拓扑排序、生成迷宫等。

BFS的设计步骤

确实，在设计解题算法时，无论是BFS还是DFS，通常都会遵循一些相似的步骤和原则。下面是按照定义设计解题算法时的一般步骤：

1. 确定题目的状态（包括边界）：

• 确定问题的状态，即图或树的节点表示什么。这些节点可以表示位置、状态、对象等。
• 确定边界条件，包括起始节点、目标节点、可行动作、约束条件等。

2. 找到状态转移方式：

• 确定节点之间的关系和转移方式。在图或树中，这可能是节点之间的连接关系、可行的移动方式等。
• 确定如何从一个状态转移到另一个状态。这可能涉及到在状态空间中进行搜索、遍历或移动。

3. 找到问题的出口，计数或者某个状态：

• 确定问题的终止条件，即找到目标节点、达到目标状态或满足特定条件。
• 如果是计数问题，确定如何计数满足条件的节点或路径等。

4. 设计搜索：

• 根据问题的性质选择合适的搜索算法，如BFS、DFS等。
• 根据问题的具体要求，设计搜索的过程，包括如何初始化数据结构、如何遍历状态空间、如何更新状态等。
• 在搜索过程中，根据问题的需要进行节点访问、状态转移、结果判断等操作。

在实际应用中，BFS和DFS通常可以相互转换，选择其中一种搜索方式取决于问题的性质和要求。

BFS模板

以下是一个典型的BFS（广度优先搜索）算法模板的实现，用于解决图或树的遍历问题：

public class BFS {public void bfs(Map<Integer, List<Integer>> graph, int start) {Set<Integer> visited = new HashSet<>(); // 用集合记录已访问的节点Queue<Integer> queue = new LinkedList<>(); // 初始化队列queue.offer(start); // 将起始节点加入队列while (!queue.isEmpty()) { // 当队列不为空时循环int node = queue.poll(); // 从队列头部取出一个节点if (visited.contains(node)) {continue; // 如果节点已经访问过，则跳过当前循环}// 在这里可以根据需要对节点进行操作，例如打印节点值System.out.println(node);visited.add(node); // 将当前节点标记为已访问// 将当前节点的未访问过的邻居节点加入队列for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {if (!visited.contains(neighbor)) {queue.offer(neighbor);}}}}// 示例用法public static void main(String[] args) {// 创建一个示例图Map<Integer, List<Integer>> graph = new HashMap<>();graph.put(0, Arrays.asList(1, 2));graph.put(1, Arrays.asList(0, 3, 4));graph.put(2, Arrays.asList(0, 5));graph.put(3, Arrays.asList(1));graph.put(4, Arrays.asList(1));graph.put(5, Arrays.asList(2));// 从节点 0 开始进行 BFS 遍历BFS bfs = new BFS();bfs.bfs(graph, 0);}
}

这个模板包含了BFS算法的基本结构：

1. 使用集合 visited 记录已访问的节点，以避免重复访问。
2. 使用队列 queue 存储待访问的节点，起始时将起始节点加入队列。
3. 在循环中，从队列中取出一个节点进行处理，并将其邻居节点加入队列。
4. 在处理节点时，可以根据需求进行相关操作，比如打印节点值或将节点添加到结果列表中。

通过这个模板，可以方便地进行BFS遍历，解决各种图或树的遍历问题。

BFS例题

扫雷游戏

输入：board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
输出：[["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

输入：board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
输出：[["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

public class Solution {private int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};private int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};public char[][] updateBoard(char[][] board, int[] click) {int x = click[0], y = click[1];if (board[x][y] == 'M') {// 点到了地雷board[x][y] = 'X';} else {bfs(board, x, y);}return board;}private void bfs(char[][] board, int x, int y) {Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{x, y});board[x][y] = 'B';  // 先假定为'B', 后续根据周围情况再修改while (!queue.isEmpty()) {int[] pos = queue.poll();int count = 0;// 统计周围地雷数量for (int i = 0; i < 8; i++) {int nx = pos[0] + dx[i];int ny = pos[1] + dy[i];if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length && board[nx][ny] == 'M') {count++;}}if (count > 0) {// 周围有地雷，更新为地雷数量board[pos[0]][pos[1]] = (char) ('0' + count);} else {// 周围无地雷，对周围的'E'进行相同操作for (int i = 0; i < 8; i++) {int nx = pos[0] + dx[i];int ny = pos[1] + dy[i];if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length && board[nx][ny] == 'E') {board[nx][ny] = 'B';  // 先标记为'B'，防止重复加入队列queue.offer(new int[]{nx, ny});}}}}}
}

岛屿数量

输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
输出：1

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出：3

public class Solution {// 定义移动方向数组dx和dy，分别代表在水平和垂直方向上的移动。// dx和dy一起使用，可以表示上下左右四个方向的移动。private int[] dx = {-1, 1, 0, 0};private int[] dy = {0, 0, -1, 1};public int numIslands(char[][] grid) {// 如果网格为空或者网格的行数为0，返回0个岛屿if (grid == null || grid.length == 0) {return 0;}int numIslands = 0; // 初始化岛屿计数器int m = grid.length; // 网格的行数int n = grid[0].length; // 网格的列数// 遍历整个网格for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 当遇到一个未访问过的'1'（陆地），启动BFSif (grid[i][j] == '1') {numIslands++; // 增加岛屿数量bfs(grid, i, j); // 使用BFS来标记整个岛屿}}}return numIslands; // 返回岛屿总数}private void bfs(char[][] grid, int x, int y) {int m = grid.length; // 网格的行数int n = grid[0].length; // 网格的列数Queue<int[]> queue = new LinkedList<>(); // 创建一个用于BFS的队列queue.offer(new int[]{x, y}); // 将当前位置加入队列grid[x][y] = '0'; // 标记当前位置为已访问// 当队列不为空时，持续进行搜索while (!queue.isEmpty()) {int[] current = queue.poll(); // 从队列中取出一个元素// 检查当前元素的四个方向for (int i = 0; i < 4; i++) {int nx = current[0] + dx[i]; // 计算新的横坐标int ny = current[1] + dy[i]; // 计算新的纵坐标// 如果新坐标在网格范围内且是未访问的陆地if (nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] == '1') {queue.offer(new int[]{nx, ny}); // 将新坐标加入队列grid[nx][ny] = '0'; // 标记新坐标为已访问}}}}
}

迭代深化搜索(IDS)

迭代深化搜索（Iterative Deepening Search，IDS）是一种结合了深度优先搜索（DFS）和广度优先搜索（BFS）的搜索策略。它综合了DFS的空间效率和BFS的完备性与最优性。IDS对于解决状态空间未知或非常大的问题特别有效。

工作原理

IDS是通过限制深度的方式进行多次的DFS。它首先对深度进行限制，然后进行DFS，每次DFS的深度限制依次增加，直到找到解决方案或达到特定条件。

步骤

1. 初始化深度限制：初始深度限制通常设置为0或1。

2. 执行有限深度的DFS：进行深度限制的DFS。如果找到解决方案，则停止搜索；如果未找到，则增加深度限制。

3. 增加深度限制：在每次未找到解决方案的DFS后，增加深度限制，通常是递增1。

4. 重复搜索：重复步骤2和3，直到找到解决方案或达到某个预设的深度限制。

优缺点及应用场景

优点：

• 空间效率高：由于每次只需要存储单个路径，因此与BFS相比，IDS在空间复杂度上更加有效。
• 完备性和最优性：如果搜索空间是有限的，IDS能够保证找到解决方案。在带权路径的问题中，通过适当设计，IDS也能保证找到最优解。
• 适用于未知深度的搜索：在不知道解决方案深度的情况下，IDS能够逐步深入，直到找到解。

缺点：

• 时间消耗可能较大：特别是当解决方案处于较深的层级时，IDS需要多次遍历上层节点，可能会导致较大的时间开销。

应用场景：

• 拼图游戏：如8-puzzle（八数码问题）或其他滑动块谜题。
• 路线规划：在路线或路径未知的情况下，查找到达目标的路线。
• 人工智能：在游戏AI中用于搜索最佳移动或决策，特别是在深度未知的情况下。

实现模板

public class IterativeDeepeningSearch {/*** 进行迭代深化搜索。** @param start 起始节点。* @param goal 目标节点。*/void iterativeDeepeningSearch(Node start, Node goal) {// 从深度0开始，逐渐增加深度限制进行搜索for (int depth = 0; ; depth++) {Set<Node> visited = new HashSet<>(); // 用于记录已访问的节点boolean result = depthLimitedSearch(start, goal, depth, visited);// 如果找到了目标节点，或者已经达到某个条件，则停止搜索if (result) {break;}}}/*** 有限深度的深度优先搜索。** @param node 当前节点。* @param goal 目标节点。* @param depth 当前的深度限制。* @param visited 已访问的节点集合。* @return 如果找到目标节点，返回true；否则返回false。*/boolean depthLimitedSearch(Node node, Node goal, int depth, Set<Node> visited) {// 检查是否达到目标节点，并且是否处于深度限制内if (depth == 0 && node.equals(goal)) {return true; // 找到目标节点}// 如果还有深度可以继续搜索if (depth > 0) {visited.add(node); // 标记当前节点为已访问for (Node child : node.getChildren()) { // 遍历所有子节点// 检查未访问的子节点，并递归地进行深度限制搜索if (!visited.contains(child) && depthLimitedSearch(child, goal, depth - 1, visited)) {return true; // 如果在子树中找到目标，返回true}}}return false; // 在当前深度限制下，没有找到目标节点}// Node类的定义（示例）static class Node {private int value; // 节点的值private List<Node> children; // 节点的子节点列表public Node(int value) {this.value = value;this.children = new ArrayList<>();}public void addChild(Node child) {children.add(child);}public List<Node> getChildren() {return children;}@Overridepublic boolean equals(Object obj) {if (this == obj) return true;if (obj == null || getClass() != obj.getClass()) return false;Node node = (Node) obj;return value == node.value;}@Overridepublic int hashCode() {return Objects.hash(value);}}// 示例用法public static void main(String[] args) {// 示例代码，创建节点并添加子节点Node start = new Node(1);Node goal = new Node(5);// 进行迭代深化搜索new IterativeDeepeningSearch().iterativeDeepeningSearch(start, goal);}
}

在此代码中，iterativeDeepeningSearch 函数控制搜索的整体流程，不断增加深度限制进行搜索，直到找到目标节点或达到某个条件。depthLimitedSearch 函数实现了具有深度限制的深度优先搜索逻辑。每次调用时，都会检查当前节点是否是目标节点，并递归地对子节点进行相同的检查，直到达到深度限制。通过这种方式，迭代深化搜索能够有效地结合深度优先搜索的空间效率和广度优先搜索的完备性。

这篇关于蓝桥杯第十五届抱佛脚（五）DFS、BFS及IDS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！