ToB企服应用市场:ToB评测及商务社交产业平台

标题: 分治算法、动态规划、贪心算法、分支限界法和回溯算法的深度对比 [打印本页]

---

作者: 写过一篇    时间: 3 天前
标题: 分治算法、动态规划、贪心算法、分支限界法和回溯算法的深度对比

1. 分治算法 (Divide and Conquer)

核心思想

• 分治法三步曲：
  
  
  • 分解（Divide）：将原问题拆分为多个子问题
    
  • 解决（Conquer）：递归解决子问题
    
  • 归并（Combine）：归并子问题的解得到原问题的解
    
  
  
• 适用场景：子问题相互独立（无重叠）
  

典型应用

• 归并排序
  
• 快速排序
  
• 大整数乘法
  

1.分治算法（归并排序）

1. import java.util.Arrays;
3. public class DivideAndConquer {
5.     // 归并排序的主函数
6.     public static void mergeSort(int[] arr) {
7.         // 如果数组为空或长度小于等于1，则直接返回
8.         if (arr == null || arr.length <= 1) return;
9.         
10.         // 创建一个临时数组用于合并过程中存储数据
11.         int[] temp = new int[arr.length];
12.         
13.         // 调用递归的归并排序函数，传入左边界、右边界和临时数组
14.         mergeSort(arr, 0, arr.length - 1, temp);
15.     }
17.     // 递归的归并排序函数，负责数组的分解和合并
18.     private static void mergeSort(int[] arr, int left, int right, int[] temp) {
19.         // 递归终止条件：当left >= right时，数组已经是单元素或空数组，不需要再分解
20.         if (left < right) {
21.             // 计算中间点
22.             int mid = left + (right - left) / 2;
24.             // 分别对左半部分和右半部分递归排序
25.             mergeSort(arr, left, mid, temp);      // 递归排序左半部分
26.             mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分
28.             // 合并两个已排序的部分
29.             merge(arr, left, mid, right, temp);   // 合并两部分
30.         }
31.     }
33.     // 合并两个已排序的子数组
34.     private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
35.         int i = left, j = mid + 1, k = 0;
36.         
37.         // 比较并合并两个部分，直到一个部分被完全合并
38.         while (i <= mid && j <= right) {
39.             if (arr[i] < arr[j]) {
40.                 // 如果左部分元素小于右部分元素，将左部分元素加入临时数组
41.                 temp[k++] = arr[i++];
42.             } else {
43.                 // 否则将右部分元素加入临时数组
44.                 temp[k++] = arr[j++];
45.             }
46.         }
48.         // 如果左部分还有剩余，直接加入临时数组
49.         while (i <= mid) temp[k++] = arr[i++];
50.         
51.         // 如果右部分还有剩余，直接加入临时数组
52.         while (j <= right) temp[k++] = arr[j++];
54.         // 将临时数组中的数据拷贝回原数组
55.         System.arraycopy(temp, 0, arr, left, k);
56.     }
58.     public static void main(String[] args) {
59.         // 定义一个待排序的数组
60.         int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
62.         // 调用归并排序进行排序
63.         mergeSort(arr);
65.         // 输出排序后的结果
66.         System.out.println("归并排序结果: " + Arrays.toString(arr));
67.     }
68. }

复制代码

重要流程：

• mergeSort：主函数，检查数组的有用性，并创建一个临时数组，然后调用递归函数。
  
• mergeSort（递归）：将数组分解成更小的部分，直到每个部分只有一个元素。
  
• merge：归并两个已排序的子数组，返回一个归并后的排序数组。
  

归并排序的工作原理：

• 分解：递归将数组不绝分别为两个子数组，直到每个子数组的长度为1。
  
• 归并：通过 merge 函数将两个有序的子数组归并成一个更大的有序数组。
  

输出：

当运行时，程序会打印排序后的数组：

1. 归并排序结果: [1, 2, 3, 4, 5, 6, 7, 8]

复制代码

时间复杂度：

归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。尽管归并排序的空间复杂度相对较高（O(n)），但它稳固并且适用于大规模数据的排序。
2. 动态规划 (Dynamic Programming)

核心思想

• 递推优化：通过存储子问题的解（影象化表），制止重复盘算
  
• 适用场景：存在重叠子问题和最优子结构（如最短路径、背包问题）
  

动态规划两要素

• 状态转移方程（递推公式）
  
• 边界条件
  

典型应用

• 斐波那契数列（影象化优化）
  
• 0-1背包问题
  
• 最长公共子序列（LCS）
  

• 动态规划（0-1背包问题）
  

1. public class DynamicProgramming {
2.    
3.     // 0-1背包问题的动态规划解法
4.     public static int knapsack(int[] weights, int[] values, int capacity) {
5.         int n = weights.length; // 物品的数量
6.         // dp[i][w]表示前i个物品，背包容量为w时的最大价值
7.         int[][] dp = new int[n + 1][capacity + 1];
8.         
9.         // 遍历每个物品
10.         for (int i = 1; i <= n; i++) {
11.             // 遍历每个可能的背包容量
12.             for (int w = 1; w <= capacity; w++) {
13.                 // 当前物品的重量超过了背包的容量，不能放入背包
14.                 if (weights[i-1] > w) {
15.                     dp[i][w] = dp[i-1][w];  // 不选择当前物品
16.                 } else {
17.                     // 选择放入当前物品或不放入当前物品
18.                     dp[i][w] = Math.max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);
19.                 }
20.             }
21.         }
22.         // 最终返回背包容量为capacity时，能够获得的最大价值
23.         return dp[n][capacity];
24.     }
26.     public static void main(String[] args) {
27.         // 物品的重量数组
28.         int[] weights = {2, 3, 4, 5};
29.         // 物品的价值数组
30.         int[] values = {3, 4, 5, 6};
31.         // 背包的容量
32.         int capacity = 5;
33.         
34.         // 计算并输出0-1背包问题的最大价值
35.         System.out.println("0-1背包最大价值: " + knapsack(weights, values, capacity)); // 输出7
36.     }
37. }

复制代码

knapsack函数：

• 这个函数使用动态规划来解决 0-1 背包问题。输入参数是物品的重量数组 weights、物品的价值数组 values 和背包的最大容量 capacity。
  
• dp[w]表示思量前 i 个物品时，在背包容量为 w 时的最大价值。
  对每一个物品 i 和每一个背包容量 w，通过选择是否将当前物品放入背包来更新 dp[w]。
  
  
  
  • 假如当前物品的重量大于背包的剩余容量 w，那么不能放入该物品，此时 dp[w] = dp[i-1][w]。
    
  • 假如当前物品的重量不大于背包容量 w
    ，那么我们必要选择将该物品放入背包照旧不放入：
    
    
    
    • 不放入：dp[w] = dp[i-1][w]
      
    • 放入：dp[w] = values[i-1] + dp[i-1][w - weights[i-1]]，即将该物品放入背包并加上该物品的价值。
      
    
    
  • 选择放入或不放入时，选择较大的那个值
    
     
  
  
  • main函数：
    
    
    
    • 定义了一个物品的重量数组 weights，物品的价值数组 values，以及背包的容量 capacity。
      
    • 调用 knapsack 函数来盘算在给定背包容量下，可以或许得到的最大价值，并输出结果。
      
    
    
  输出：
  
  当运行时，程序会输出：
  
  1. 0-1背包最大价值: 7

  复制代码
  表明：
  
  在这个例子中，有四个物品，分别具有以下重量和价值：
     
  
  
  
  • 物品1：重量=2，价值=3
    
  • 物品2：重量=3，价值=4
    
  • 物品3：重量=4，价值=5
    
  • 物品4：重量=5，价值=6
    
  背包的容量为5。通过动态规划盘算得出最大可以或许得到的价值为7。选择的物品是：
     
  
  
  
  • 物品1（重量2，价值3）
    
  • 物品2（重量3，价值4） 总价值为3 + 4 = 7。
    
  时间复杂度：
  
  该算法的时间复杂度为 O(n * capacity)，其中 n 是物品的数目，capacity 是背包的容量。这个复杂度适用于解决中等规模的背包问题。
  空间复杂度：
  
  空间复杂度为 O(n * capacity)，用于存储 dp 数组的状态。
  3. 贪心算法 (Greedy Algorithm)
  
  ** 核心思想**
  
     
  
  
  
  • 局部最优导向全局最优：每一步选择当前最优解（无需思量团体）
    
  • 适用场景：问题满意贪心选择性质和最优子结构（如活动选择、哈夫曼编码）
    
  典型应用
  
     
  
  
  
  • Dijkstra最短路径算法
    
  • 霍夫曼编码
    
  • 活动选择问题
    
  贪心算法（活动选择问题）
  
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Comparator;
  5. public class GreedyAlgorithm {
  7.     // 活动选择问题的贪心算法
  8.     public static ArrayList<int[]> activitySelection(int[] start, int[] end) {
  9.         int n = start.length; // 获取活动的数量
  10.         int[][] activities = new int[n][2]; // 创建一个二维数组来存储每个活动的开始时间和结束时间
  11.         
  12.         // 将活动的开始时间和结束时间存储到二维数组中
  13.         for (int i = 0; i < n; i++) {
  14.             activities[i][0] = start[i];
  15.             activities[i][1] = end[i];
  16.         }
  18.         // 按照活动的结束时间对活动进行排序（从小到大）
  19.         Arrays.sort(activities, Comparator.comparingInt(a -> a[1])); // 按结束时间排序
  21.         // 存储选择的活动
  22.         ArrayList<int[]> selected = new ArrayList<>();
  23.         
  24.         // 将第一个活动加入到选择的列表中
  25.         selected.add(activities[0]);
  26.         
  27.         // 记录上一个被选择活动的结束时间
  28.         int lastEnd = activities[0][1];
  30.         // 从第二个活动开始检查
  31.         for (int i = 1; i < n; i++) {
  32.             // 如果当前活动的开始时间大于上一个活动的结束时间
  33.             if (activities[i][0] > lastEnd) {
  34.                 // 选择当前活动
  35.                 selected.add(activities[i]);
  36.                 // 更新上一个活动的结束时间为当前活动的结束时间
  37.                 lastEnd = activities[i][1];
  38.             }
  39.         }
  41.         // 返回所有选择的活动
  42.         return selected;
  43.     }
  45.     public static void main(String[] args) {
  46.         // 活动的开始时间
  47.         int[] start = {1, 3, 0, 5, 8, 5};
  48.         // 活动的结束时间
  49.         int[] end = {2, 4, 6, 7, 9, 9};
  51.         // 调用活动选择函数，得到所有选择的活动
  52.         ArrayList<int[]> result = activitySelection(start, end);
  54.         // 输出选择的活动的时间段
  55.         System.out.print("选择的活动时间段: ");
  56.         for (int[] act : result) {
  57.             System.out.print(Arrays.toString(act) + " ");
  58.         }
  59.         // 输出: [1, 2] [3, 4] [5, 7] [8, 9]
  60.     }
  61. }

  复制代码
  activitySelection函数：
     
  
  
  
  • 输入： 活动的开始时间数组 start 和结束时间数组 end。
    
  • 过程：
    
    
    • 将每个活动的开始时间和结束时间存入二维数组 activities 中。
      
    • 按照活动的结束时间对活动举行排序。这里使用了 Arrays.sort() 并通过 Comparator.comparingInt(a -> a[1]) 按照每个活动的结束时间举行升序排列。
      
    • 然后从第一个活动开始选择，每次选择一个活动时，只有当当前活动的开始时间大于上一个被选择活动的结束时间时，才能选择当前活动。
      
    • 每次选择成功后，更新上一个被选择活动的结束时间，并继承检查下一个活动。
      
    
    
  • 输出： 返回一个 ArrayList，表示被选择的活动。
    
  main函数：
     
  
  
  
  • 定义了一个活动的开始时间数组 start 和结束时间数组 end，然后调用 activitySelection 函数盘算最优的活动选择。
    
  • 输出选中的活动时间段。
    
  输出：
  
  1. 选择的活动时间段: [1, 2] [3, 4] [5, 7] [8, 9]

  复制代码
  活动选择过程：
  
     
  
  
  • 按结束时间排序后得到的活动顺序：
    
    
    
    • 活动 [1, 2]
      
    • 活动 [3, 4]
      
    • 活动 [0, 6]
      
    • 活动 [5, 7]
      
    • 活动 [8, 9]
      
    • 活动 [5, 9]
      
    
    
  • 贪心算法按照结束时间从小到大选择：
    
    
    
    • 选择第一个活动 [1, 2]。
      
    • 选择第二个活动 [3, 4]，由于它的开始时间大于 [1, 2] 的结束时间。
      
    • 选择第四个活动 [5, 7]，由于它的开始时间大于 [3, 4] 的结束时间。
      
    • 选择第五个活动 [8, 9]，由于它的开始时间大于 [5, 7] 的结束时间。
      
    
    
  时间复杂度：
  
     
  
  
  
  • 排序活动的时间复杂度是 O(n log n)，其中 n 是活动的数目。
    
  • 遍历活动选择符合活动的时间复杂度是 O(n)。
    
  • 总体时间复杂度为 O(n log n)。
    
  空间复杂度：
  
     
  
  
  
  • 使用了 O(n) 的空间来存储活动数组 activities 和结果数组 selected，因此空间复杂度为 O(n)。
    
  
  

4. 分支限界法 (Branch and Bound)

核心思想

• 剪枝优化搜索：通过上下界限定搜索空间，优先扩展最有希望的分支
  
• 适用场景：组合优化问题（如旅行商问题、使命分配）
  

典型应用

• 旅行商问题（TSP）
  
• 使命分配问题
  
• 整数规划
  

• 分支限界法（使命分配问题）
  

1. import java.util.Arrays;
2. import java.util.PriorityQueue;
4. public class BranchAndBound {
5.     // 内部静态类 Node，表示分支限界法中的状态节点
6.     static class Node implements Comparable<Node> {
7.         int[] assigned;  // 已分配的任务索引，assigned[i]表示工人i分配的任务
8.         int cost;        // 当前路径的成本（已分配工人的总成本）
9.         int worker;      // 已分配的工人数量
10.         int bound;       // 当前节点的下界（用于剪枝优化）
12.         public Node(int[] assigned, int cost, int worker) {
13.             this.assigned = Arrays.copyOf(assigned, worker); // 复制数组，避免引用冲突
14.             this.cost = cost;
15.             this.worker = worker;
16.         }
18.         // 优先队列根据节点的 bound（下界）排序
19.         @Override
20.         public int compareTo(Node other) {
21.             return Integer.compare(this.bound, other.bound);
22.         }
23.     }
25.     /**
26.      * 解决任务分配问题的分支限界算法
27.      * @param costMatrix 代价矩阵，costMatrix[worker][job] 表示工人分配任务的成本
28.      * @return 最小成本
29.      */
30.     public static int assignJobs(int[][] costMatrix) {
31.         int n = costMatrix.length;  // 工人和任务的总数
32.         PriorityQueue<Node> pq = new PriorityQueue<>(); // 优先队列（按bound升序排列）
33.         pq.add(new Node(new int[0], 0, 0));
34.         int minCost = Integer.MAX_VALUE;
36.         // 主循环处理队列中的节点
37.         while (!pq.isEmpty()) {
38.             Node node = pq.poll(); // 取出当前最优（下界最小）的节点
39.             // 如果所有工人都已分配任务，更新最小成本
40.             if (node.worker == n) {
41.                 if (node.cost < minCost) {
42.                     minCost = node.cost;
43.                 }
44.                 continue;
45.             }
47.             // 尝试为当前工人（node.worker）分配每一个可能的任务
48.             for (int job = 0; job < n; job++) {
49.                 // 检查该任务是否已分配给其他工人
50.                 if (isJobFree(node.assigned, job)) {
51.                     // 创建新的分配数组，将当前工人的任务添加到尾部
52.                     int[] newAssigned = Arrays.copyOf(node.assigned, node.worker + 1);
53.                     newAssigned[node.worker] = job;
54.                     // 计算新的总成本（历史成本 + 当前工人执行任务的成本）
55.                     int newCost = node.cost + costMatrix[node.worker][job];
56.                     // 创建新节点（worker数量+1）
57.                     Node nextNode = new Node(newAssigned, newCost, node.worker + 1);
58.                     // 计算当前新节点的下界（剪枝判断依据）
59.                     nextNode.bound = calculateBound(nextNode, costMatrix);
60.                     // 如果下界小于当前已知最小成本，才继续扩展
61.                     if (nextNode.bound < minCost) {
62.                         pq.add(nextNode);
63.                     }
64.                 }
65.             }
66.         }
67.         return minCost;
68.     }
70.     /**
71.      * 检查任务是否未被分配
72.      * @param assigned 已分配的任务数组
73.      * @param job      待检测的任务索引
74.      * @return 如果任务未被分配则返回 true
75.      */
76.     private static boolean isJobFree(int[] assigned, int job) {
77.         for (int j : assigned) {
78.             if (j == job) return false;
79.         }
80.         return true;
81.     }
83.     /**
84.      * 计算节点的下界（包含已确定成本和剩余节点的最小可能成本）
85.      * 改进后的逻辑：剩余每个工人选择其未分配任务的最小成本之和
86.      */
87.     private static int calculateBound(Node node, int[][] costMatrix) {
88.         int bound = node.cost;  // 起始值为当前已确定的成本
89.         int n = costMatrix.length;
90.         // 遍历未分配的工人
91.         for (int w = node.worker; w < n; w++) {
92.             int minJobCost = Integer.MAX_VALUE;
93.             // 遍历所有任务，检查是否未被分配
94.             for (int j = 0; j < n; j++) {
95.                 if (isJobFree(node.assigned, j)) {
96.                     if (costMatrix[w][j] < minJobCost) {
97.                         minJobCost = costMatrix[w][j];
98.                     }
99.                 }
100.             }
101.             if (minJobCost != Integer.MAX_VALUE) {
102.                 bound += minJobCost; // 累加每个未分配工人的最小可能成本
103.             }
104.         }
105.         return bound;
106.     }
108.     public static void main(String[] args) {
109.         int[][] costMatrix = {
110.             {9, 2, 7, 8},
111.             {6, 4, 3, 7},
112.             {5, 8, 1, 8},
113.             {7, 6, 9, 4}
114.         };
115.         int result = assignJobs(costMatrix);
116.         System.out.println("最小任务分配成本: " + result); // 正确输出13
117.     }
118. }

复制代码

1. 输入代价矩阵:
2. Worker\Task | Task0 | Task1 | Task2 | Task3
3. ---------------------------------------------
4. Worker0     |   9   |   2   |   7   |   8   
5. Worker1     |   6   |   4   |   3   |   7   
6. Worker2     |   5   |   8   |   1   |   8   
7. Worker3     |   7   |   6   |   9   |   4   
9. 最优路径（红色标记）：
10. Worker0 → Task1（成本2）
11. Worker1 → Task2（成本3）
12. Worker2 → Task2（成本1）※ 该任务已被分配 → 实际选择 Task2 → 发生冲突，说明逻辑需要递归剪枝调整
13. Worker3 → Task3（成本4）
15. 总和：2 + 3 + 1 + 4 =  ※ 但正确解应由：
16. Worker0→Task1(2), Worker1→Task2(3), Worker2→Task2(此处冲突需纠正), 实际正确分配方案为 Worker0→Task1(2), Worker1→Task0(6), Worker2→Task2(1), Worker3→Task3(4)，总成本13

复制代码

代码运行结果

1. 最小任务分配成本: 13

复制代码

5. 搜索+回溯算法 (Backtracking)

核心思想

• 试探性搜索：递归探索全部大概性，发现不可行时实时回溯
  
• 适用场景：组合问题、迷宫问题、N皇后问题、数独
  

典型应用

• 八皇后问题
  
• 全排列问题
  
• 数独求解
  

• 回溯算法（N皇后问题
  

1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.List;
5. public class Backtracking {
6.     /**
7.      * 解决N皇后问题的入口方法
8.      * @param n 棋盘大小(N x N)
9.      * @return 所有合法解的集合（每个解表示为一个字符串列表）
10.      */
11.     public static List<List<String>> solveNQueens(int n) {
12.         List<List<String>> solutions = new ArrayList<>();
13.         // 初始化棋盘，'.'表示空位，'Q'表示皇后
14.         char[][] board = new char[n][n];
15.         for (int i = 0; i < n; i++) {
16.             Arrays.fill(board[i], '.'); // 填充每行为空行
17.         }
18.         backtrack(board, 0, solutions); // 从第0行开始递归
19.         return solutions;
20.     }
22.     /**
23.      * 核心回溯方法
24.      * @param board 当前棋盘状态
25.      * @param row 当前处理的行
26.      * @param solutions 存储所有解的结果集
27.      */
28.     private static void backtrack(char[][] board, int row, List<List<String>> solutions) {
29.         // 终止条件：所有行均已放置皇后
30.         if (row == board.length) {
31.             solutions.add(formatBoard(board)); // 将当前解保存
32.             return;
33.         }
34.         // 尝试在当前行的每一列放置皇后
35.         for (int col = 0; col < board.length; col++) {
36.             if (isValid(board, row, col)) {  // 检查当前位置是否合法
37.                 board[row][col] = 'Q';
38.                 backtrack(board, row + 1, solutions);  // 递归处理下一行
39.                 board[row][col] = '.';  // ★ 回溯：撤销当前选择 ★
40.             }
41.         }
42.     }
44.     /**
45.      * 验证在(row, col)位置放置皇后是否合法
46.      * 检查规则：同列无Q，45度/135度对角线上无Q
47.      */
48.     private static boolean isValid(char[][] board, int row, int col) {
49.         // 遍历检查当前列及对角线（只需检查上方已放置的行）
50.         for (int i = 0; i < row; i++) {
51.             // 检查同一列是否已有皇后
52.             if (board[i][col] == 'Q') return false;
53.             int diff = row - i;  // 行差（当前行row与历史行i的差）
54.             // 检查左上对角线（列差与行差相等则为对角线）
55.             if (col - diff >= 0 && board[i][col - diff] == 'Q') return false;
56.             // 检查右上对角线（同上原理）
57.             if (col + diff < board.length && board[i][col + diff] == 'Q') return false;
58.         }
59.         return true;
60.     }
62.     /**
63.      * 将棋盘转换为字符串列表形式
64.      * 例如：["..Q.", "Q...", "...Q", ".Q.."]
65.      */
66.     private static List<String> formatBoard(char[][] board) {
67.         List<String> formatted = new ArrayList<>();
68.         for (char[] row : board) {
69.             formatted.add(new String(row)); // 将每一行char[]转为字符串
70.         }
71.         return formatted;
72.     }
74.     public static void main(String[] args) {
75.         int n = 4;
76.         List<List<String>> solutions = solveNQueens(n);
77.         System.out.println(n + "皇后问题的解法数量: " + solutions.size());  // 输出2
78.         // 打印解示例
79.         for (List<String> solution : solutions) {
80.             System.out.println("\n解法示例：");
81.             for (String row : solution) {
82.                 System.out.println(row);
83.             }
84.         }
85.     }
86. }

复制代码

代码运行结果

1. 4皇后问题的解法数量: 2
3. 解法示例：
4. .Q..
5. ...Q
6. Q...
7. ..Q.
9. 解法示例：
10. ..Q.
11. Q...
12. ...Q
13. .Q..

复制代码

回溯的关键操纵
当某行全部位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操纵）
时间复杂度分析

• 最坏环境：O(n! * n²)，其中n是棋盘大小
  （遍历全部排列组合，每个验证检查斲丧O(n)时间）
  
• 实际运行：通过实时剪枝（提前发现非法位置），大大减少搜索空间
  

五大核心算法构建了盘算机问题求解的立体框架，每种方法都对应着独特的头脑范式与应用场景：
方法论维度

• 分治算法表现模块化解构的哲学，通过递归拆分实现化繁为简
  
• 动态规划以空间换时间，通过状态转移方程构建结构性影象
  
• 贪心算法专注当下最优决议，以局部最优构造全局近似解
  
• 分支界限法建立智能搜索树，通过剪枝优化遍历效率
  
• 回溯算法采用试错机制，利用状态重置探索解空间
  

t.println(“\n解法示例：”);
for (String row : solution) {
System.out.println(row);
}
}
}
}

1. 代码运行结果```java4皇后问题的解法数量: 2
3. 解法示例：
4. .Q..
5. ...Q
6. Q...
7. ..Q.
9. 解法示例：
10. ..Q.
11. Q...
12. ...Q
13. .Q..

复制代码

回溯的关键操纵
当某行全部位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操纵）
时间复杂度分析

• 最坏环境：O(n! * n²)，其中n是棋盘大小
  （遍历全部排列组合，每个验证检查斲丧O(n)时间）
  
• 实际运行：通过实时剪枝（提前发现非法位置），大大减少搜索空间
  

五大核心算法构建了盘算机问题求解的立体框架，每种方法都对应着独特的头脑范式与应用场景：
方法论维度

• 分治算法表现模块化解构的哲学，通过递归拆分实现化繁为简
  
• 动态规划以空间换时间，通过状态转移方程构建结构性影象
  
• 贪心算法专注当下最优决议，以局部最优构造全局近似解
  
• 分支界限法建立智能搜索树，通过剪枝优化遍历效率
  
• 回溯算法采用试错机制，利用状态重置探索解空间
  

工程实践中通常复合使用多种算法，比方在回溯框架内结合贪心剪枝策略，或在动态规划中融合分治思想。理解各算法的本质接洽与演进关系（如动态规划实质是分治+备忘录的进化形态），才能针对详细问题设计出兼顾时间效率和实现复杂度的混合解法。发起通过LeetCode等算法平台举行组合练习，作育敏锐的算法嗅觉与方案决议本领。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4