分治算法、动态规划、贪心算法、分支限界法和回溯算法的深度对比 ...

写过一篇 · 3 天前

1. 分治算法 (Divide and Conquer)

核心思想

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

典型应用

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

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

import java.util.Arrays;
public class DivideAndConquer {
// 归并排序的主函数
public static void mergeSort(int[] arr) {
// 如果数组为空或长度小于等于1，则直接返回
if (arr == null || arr.length <= 1) return;
// 创建一个临时数组用于合并过程中存储数据
int[] temp = new int[arr.length];
// 调用递归的归并排序函数，传入左边界、右边界和临时数组
mergeSort(arr, 0, arr.length - 1, temp);
}
// 递归的归并排序函数，负责数组的分解和合并
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
// 递归终止条件：当left >= right时，数组已经是单元素或空数组，不需要再分解
if (left < right) {
// 计算中间点
int mid = left + (right - left) / 2;
// 分别对左半部分和右半部分递归排序
mergeSort(arr, left, mid, temp); // 递归排序左半部分
mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分
// 合并两个已排序的部分
merge(arr, left, mid, right, temp); // 合并两部分
}
}
// 合并两个已排序的子数组
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, k = 0;
// 比较并合并两个部分，直到一个部分被完全合并
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
// 如果左部分元素小于右部分元素，将左部分元素加入临时数组
temp[k++] = arr[i++];
} else {
// 否则将右部分元素加入临时数组
temp[k++] = arr[j++];
}
}
// 如果左部分还有剩余，直接加入临时数组
while (i <= mid) temp[k++] = arr[i++];
// 如果右部分还有剩余，直接加入临时数组
while (j <= right) temp[k++] = arr[j++];
// 将临时数组中的数据拷贝回原数组
System.arraycopy(temp, 0, arr, left, k);
}
public static void main(String[] args) {
// 定义一个待排序的数组
int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
// 调用归并排序进行排序
mergeSort(arr);
// 输出排序后的结果
System.out.println("归并排序结果: " + Arrays.toString(arr));
}
}

复制代码

重要流程：

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

归并排序的工作原理：

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

输出：

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

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

复制代码

时间复杂度：

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

核心思想

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

动态规划两要素

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

典型应用

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

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

public class DynamicProgramming {
// 0-1背包问题的动态规划解法
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length; // 物品的数量
// dp[i][w]表示前i个物品，背包容量为w时的最大价值
int[][] dp = new int[n + 1][capacity + 1];
// 遍历每个物品
for (int i = 1; i <= n; i++) {
// 遍历每个可能的背包容量
for (int w = 1; w <= capacity; w++) {
// 当前物品的重量超过了背包的容量，不能放入背包
if (weights[i-1] > w) {
dp[i][w] = dp[i-1][w]; // 不选择当前物品
} else {
// 选择放入当前物品或不放入当前物品
dp[i][w] = Math.max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);
}
}
}
// 最终返回背包容量为capacity时，能够获得的最大价值
return dp[n][capacity];
}
public static void main(String[] args) {
// 物品的重量数组
int[] weights = {2, 3, 4, 5};
// 物品的价值数组
int[] values = {3, 4, 5, 6};
// 背包的容量
int capacity = 5;
// 计算并输出0-1背包问题的最大价值
System.out.println("0-1背包最大价值: " + knapsack(weights, values, capacity)); // 输出7
}
}

复制代码

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 函数来盘算在给定背包容量下，可以或许得到的最大价值，并输出结果。

输出：

当运行时，程序会输出：

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最短路径算法

霍夫曼编码

活动选择问题

贪心算法（活动选择问题）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class GreedyAlgorithm {
// 活动选择问题的贪心算法
public static ArrayList<int[]> activitySelection(int[] start, int[] end) {
      int n = start.length; // 获取活动的数量
      int[][] activities = new int[n][2]; // 创建一个二维数组来存储每个活动的开始时间和结束时间

      // 将活动的开始时间和结束时间存储到二维数组中
      for (int i = 0; i < n; i++) {
         activities[i][0] = start[i];
         activities[i][1] = end[i];
      }
      // 按照活动的结束时间对活动进行排序（从小到大）
      Arrays.sort(activities, Comparator.comparingInt(a -> a[1])); // 按结束时间排序
      // 存储选择的活动
      ArrayList<int[]> selected = new ArrayList<>();

      // 将第一个活动加入到选择的列表中
      selected.add(activities[0]);

      // 记录上一个被选择活动的结束时间
      int lastEnd = activities[0][1];
      // 从第二个活动开始检查
      for (int i = 1; i < n; i++) {
         // 如果当前活动的开始时间大于上一个活动的结束时间
         if (activities[i][0] > lastEnd) {
            // 选择当前活动
            selected.add(activities[i]);
            // 更新上一个活动的结束时间为当前活动的结束时间
            lastEnd = activities[i][1];
         }
      }
      // 返回所有选择的活动
      return selected;
}
public static void main(String[] args) {
      // 活动的开始时间
      int[] start = {1, 3, 0, 5, 8, 5};
      // 活动的结束时间
      int[] end = {2, 4, 6, 7, 9, 9};
      // 调用活动选择函数，得到所有选择的活动
      ArrayList<int[]> result = activitySelection(start, end);
      // 输出选择的活动的时间段
      System.out.print("选择的活动时间段: ");
      for (int[] act : result) {
         System.out.print(Arrays.toString(act) + " ");
      }
      // 输出: [1, 2] [3, 4] [5, 7] [8, 9]
}
}
复制代码
activitySelection函数：

输入： 活动的开始时间数组 start 和结束时间数组 end。

过程：

将每个活动的开始时间和结束时间存入二维数组 activities 中。

按照活动的结束时间对活动举行排序。这里使用了 Arrays.sort() 并通过 Comparator.comparingInt(a -> a[1]) 按照每个活动的结束时间举行升序排列。

然后从第一个活动开始选择，每次选择一个活动时，只有当当前活动的开始时间大于上一个被选择活动的结束时间时，才能选择当前活动。

每次选择成功后，更新上一个被选择活动的结束时间，并继承检查下一个活动。

输出： 返回一个 ArrayList，表示被选择的活动。

main函数：

定义了一个活动的开始时间数组 start 和结束时间数组 end，然后调用 activitySelection 函数盘算最优的活动选择。

输出选中的活动时间段。

输出：

选择的活动时间段: [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）

使命分配问题

整数规划

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

import java.util.Arrays;
import java.util.PriorityQueue;
public class BranchAndBound {
// 内部静态类 Node，表示分支限界法中的状态节点
static class Node implements Comparable<Node> {
      int[] assigned;  // 已分配的任务索引，assigned[i]表示工人i分配的任务
      int cost;       // 当前路径的成本（已分配工人的总成本）
      int worker;    // 已分配的工人数量
      int bound;    // 当前节点的下界（用于剪枝优化）
      public Node(int[] assigned, int cost, int worker) {
         this.assigned = Arrays.copyOf(assigned, worker); // 复制数组，避免引用冲突
         this.cost = cost;
         this.worker = worker;
      }
      // 优先队列根据节点的 bound（下界）排序
      @Override
      public int compareTo(Node other) {
         return Integer.compare(this.bound, other.bound);
      }
}
/**
   * 解决任务分配问题的分支限界算法
   * @param costMatrix 代价矩阵，costMatrix[worker][job] 表示工人分配任务的成本
   * @return 最小成本
   */
public static int assignJobs(int[][] costMatrix) {
      int n = costMatrix.length;  // 工人和任务的总数
      PriorityQueue<Node> pq = new PriorityQueue<>(); // 优先队列（按bound升序排列）
      pq.add(new Node(new int[0], 0, 0));
      int minCost = Integer.MAX_VALUE;
      // 主循环处理队列中的节点
      while (!pq.isEmpty()) {
         Node node = pq.poll(); // 取出当前最优（下界最小）的节点
         // 如果所有工人都已分配任务，更新最小成本
         if (node.worker == n) {
            if (node.cost < minCost) {
                  minCost = node.cost;
            }
            continue;
         }
         // 尝试为当前工人（node.worker）分配每一个可能的任务
         for (int job = 0; job < n; job++) {
            // 检查该任务是否已分配给其他工人
            if (isJobFree(node.assigned, job)) {
                  // 创建新的分配数组，将当前工人的任务添加到尾部
                  int[] newAssigned = Arrays.copyOf(node.assigned, node.worker + 1);
                  newAssigned[node.worker] = job;
                  // 计算新的总成本（历史成本 + 当前工人执行任务的成本）
                  int newCost = node.cost + costMatrix[node.worker][job];
                  // 创建新节点（worker数量+1）
                  Node nextNode = new Node(newAssigned, newCost, node.worker + 1);
                  // 计算当前新节点的下界（剪枝判断依据）
                  nextNode.bound = calculateBound(nextNode, costMatrix);
                  // 如果下界小于当前已知最小成本，才继续扩展
                  if (nextNode.bound < minCost) {
                     pq.add(nextNode);
                  }
            }
         }
      }
      return minCost;
}
/**
   * 检查任务是否未被分配
   * @param assigned 已分配的任务数组
   * @param job    待检测的任务索引
   * @return 如果任务未被分配则返回 true
   */
private static boolean isJobFree(int[] assigned, int job) {
      for (int j : assigned) {
         if (j == job) return false;
      }
      return true;
}
/**
   * 计算节点的下界（包含已确定成本和剩余节点的最小可能成本）
   * 改进后的逻辑：剩余每个工人选择其未分配任务的最小成本之和
   */
private static int calculateBound(Node node, int[][] costMatrix) {
      int bound = node.cost;  // 起始值为当前已确定的成本
      int n = costMatrix.length;
      // 遍历未分配的工人
      for (int w = node.worker; w < n; w++) {
         int minJobCost = Integer.MAX_VALUE;
         // 遍历所有任务，检查是否未被分配
         for (int j = 0; j < n; j++) {
            if (isJobFree(node.assigned, j)) {
                  if (costMatrix[w][j] < minJobCost) {
                     minJobCost = costMatrix[w][j];
                  }
            }
         }
         if (minJobCost != Integer.MAX_VALUE) {
            bound += minJobCost; // 累加每个未分配工人的最小可能成本
         }
      }
      return bound;
}
public static void main(String[] args) {
      int[][] costMatrix = {
         {9, 2, 7, 8},
         {6, 4, 3, 7},
         {5, 8, 1, 8},
         {7, 6, 9, 4}
      };
      int result = assignJobs(costMatrix);
      System.out.println("最小任务分配成本: " + result); // 正确输出13
}
}
复制代码
输入代价矩阵:
Worker\Task | Task0 | Task1 | Task2 | Task3
---------------------------------------------
Worker0    | 9 | 2 | 7 | 8
Worker1    | 6 | 4 | 3 | 7
Worker2    | 5 | 8 | 1 | 8
Worker3    | 7 | 6 | 9 | 4
最优路径（红色标记）：
Worker0 → Task1（成本2）
Worker1 → Task2（成本3）
Worker2 → Task2（成本1）※ 该任务已被分配 → 实际选择 Task2 → 发生冲突，说明逻辑需要递归剪枝调整
Worker3 → Task3（成本4）
总和：2 + 3 + 1 + 4 =  ※ 但正确解应由：
Worker0→Task1(2), Worker1→Task2(3), Worker2→Task2(此处冲突需纠正), 实际正确分配方案为 Worker0→Task1(2), Worker1→Task0(6), Worker2→Task2(1), Worker3→Task3(4)，总成本13
复制代码
代码运行结果

最小任务分配成本: 13
复制代码
5. 搜索+回溯算法 (Backtracking)

核心思想

试探性搜索：递归探索全部大概性，发现不可行时实时回溯

适用场景：组合问题、迷宫问题、N皇后问题、数独

典型应用

八皇后问题

全排列问题

数独求解

回溯算法（N皇后问题

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Backtracking {
/**
   * 解决N皇后问题的入口方法
   * @param n 棋盘大小(N x N)
   * @return 所有合法解的集合（每个解表示为一个字符串列表）
   */
public static List<List<String>> solveNQueens(int n) {
      List<List<String>> solutions = new ArrayList<>();
      // 初始化棋盘，'.'表示空位，'Q'表示皇后
      char[][] board = new char[n][n];
      for (int i = 0; i < n; i++) {
         Arrays.fill(board[i], '.'); // 填充每行为空行
      }
      backtrack(board, 0, solutions); // 从第0行开始递归
      return solutions;
}
/**
   * 核心回溯方法
   * @param board 当前棋盘状态
   * @param row 当前处理的行
   * @param solutions 存储所有解的结果集
   */
private static void backtrack(char[][] board, int row, List<List<String>> solutions) {
      // 终止条件：所有行均已放置皇后
      if (row == board.length) {
         solutions.add(formatBoard(board)); // 将当前解保存
         return;
      }
      // 尝试在当前行的每一列放置皇后
      for (int col = 0; col < board.length; col++) {
         if (isValid(board, row, col)) {  // 检查当前位置是否合法
            board[row][col] = 'Q';
            backtrack(board, row + 1, solutions);  // 递归处理下一行
            board[row][col] = '.';  // ★ 回溯：撤销当前选择 ★
         }
      }
}
/**
   * 验证在(row, col)位置放置皇后是否合法
   * 检查规则：同列无Q，45度/135度对角线上无Q
   */
private static boolean isValid(char[][] board, int row, int col) {
      // 遍历检查当前列及对角线（只需检查上方已放置的行）
      for (int i = 0; i < row; i++) {
         // 检查同一列是否已有皇后
         if (board[i][col] == 'Q') return false;
         int diff = row - i;  // 行差（当前行row与历史行i的差）
         // 检查左上对角线（列差与行差相等则为对角线）
         if (col - diff >= 0 && board[i][col - diff] == 'Q') return false;
         // 检查右上对角线（同上原理）
         if (col + diff < board.length && board[i][col + diff] == 'Q') return false;
      }
      return true;
}
/**
   * 将棋盘转换为字符串列表形式
   * 例如：["..Q.", "Q...", "...Q", ".Q.."]
   */
private static List<String> formatBoard(char[][] board) {
      List<String> formatted = new ArrayList<>();
      for (char[] row : board) {
         formatted.add(new String(row)); // 将每一行char[]转为字符串
      }
      return formatted;
}
public static void main(String[] args) {
      int n = 4;
      List<List<String>> solutions = solveNQueens(n);
      System.out.println(n + "皇后问题的解法数量: " + solutions.size());  // 输出2
      // 打印解示例
      for (List<String> solution : solutions) {
         System.out.println("\n解法示例：");
         for (String row : solution) {
            System.out.println(row);
         }
      }
}
}
复制代码
代码运行结果

4皇后问题的解法数量: 2
解法示例：
.Q..
...Q
Q...
..Q.
解法示例：
..Q.
Q...
...Q
.Q..
复制代码
回溯的关键操纵
当某行全部位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操纵）
时间复杂度分析

最坏环境：O(n! * n²)，其中n是棋盘大小
（遍历全部排列组合，每个验证检查斲丧O(n)时间）

实际运行：通过实时剪枝（提前发现非法位置），大大减少搜索空间

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

分治算法表现模块化解构的哲学，通过递归拆分实现化繁为简

动态规划以空间换时间，通过状态转移方程构建结构性影象

贪心算法专注当下最优决议，以局部最优构造全局近似解

分支界限法建立智能搜索树，通过剪枝优化遍历效率

回溯算法采用试错机制，利用状态重置探索解空间

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

代码运行结果```java4皇后问题的解法数量: 2
解法示例：
.Q..
...Q
Q...
..Q.
解法示例：
..Q.
Q...
...Q
.Q..
复制代码
回溯的关键操纵
当某行全部位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操纵）
时间复杂度分析

最坏环境：O(n! * n²)，其中n是棋盘大小
（遍历全部排列组合，每个验证检查斲丧O(n)时间）

实际运行：通过实时剪枝（提前发现非法位置），大大减少搜索空间

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

分治算法表现模块化解构的哲学，通过递归拆分实现化繁为简

动态规划以空间换时间，通过状态转移方程构建结构性影象

贪心算法专注当下最优决议，以局部最优构造全局近似解

分支界限法建立智能搜索树，通过剪枝优化遍历效率

回溯算法采用试错机制，利用状态重置探索解空间

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

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

		自动登录	找回密码
密码			立即注册

分治算法、动态规划、贪心算法、分支限界法和回溯算法的深度对比 ...

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云