【数据结构与算法之回溯法】案例

àì夳堔傛蜴生んèń 2024-03-25 20:19 81阅读 0赞

#### 【数据结构与算法之回溯法】案例 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之回溯法】案例
         *   *   *  1 四皇后问题
                 *  2 0-1背包问题

###### 1 四皇后问题 ######

先给出我们之前讨论的四皇后问题的解法Java 描述：

import java.util.SortedMap;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: FourQueensProblem
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 10:21
     */
    
    public class FourQueensProblem {
        
    
        public static void QueenByBacktracking(int size) {
        
            int[][] Q = new int[size][size];
    
            // 初始化整个棋盘
            for (int i = 0; i < size; i++) {
        
                for (int j = 0; j < size; j++) {
        
                    Q[i][j] = 0;
                }
            }
            
            /*
            	0 0 0 0
            	0 0 0 0
            	0 0 0 0
            	0 0 0 0
            */
            // 四皇后棋盘初始化完成后就是这样的
    
            Queen(0, Q, size);
        }
    
        private static void Queen(int col, int[][] Q, final int size) {
         // 核心 
            // 找到一个四皇后问题的解
            if (col == size) {
         // 这里是问题的终止条件，不等于4证明还没有搜索到底
                for (int i = 0; i < size; i++) {
        
                    for (int j = 0; j < size; j++) {
        
                        System.out.print(Q[i][j] + " ");
                    }
                    System.out.println(" ");
                }
    
                System.out.println("==========================");
                return;
            }
    
            for (int i = 0; i < size; i++) {
        
                if (isCorrectPosition(i, col, Q, size)) {
         // 如果(i, col) 的位置可摆放一个皇后
                    // 那就摆一个皇后
                    Q[i][col] = 1;
                    Queen(col + 1, Q, size); // 深度优先搜索解空间树【列 + 1】
                    // 回溯[还原现场]
                    Q[i][col] = 0;
                }
            }
        }
    
        private static boolean isCorrectPosition(int i, int j, int[][] Q, int size) {
        
            // 判断行
            for (int s = i, t = 0; t < size; t++) {
        
                if (Q[s][t] == 1 && t != j) {
        
                    return false;
                }
            }
    
            // 判断列
            for (int t = j, s = 0; s < size; s++) {
        
                if (Q[s][t] == 1 && s != i) {
        
                    return false;
                }
            }
    
            // 判断左上方
            for (int s = i - 1, t = j - 1; s >= 0 && t >= 0; s--, t--) {
        
                if (Q[s][t] == 1) {
        
                    return false;
                }
            }
    
            // 判断右下方
            for (int s = i + 1, t = j + 1; s < size && t < size; s++, t++) {
        
                if (Q[s][t] == 1) {
        
                    return false;
                }
            }
    
            // 判断右上方
            for (int s = i - 1, t = j + 1; s >= 0 && t < size; s--, t++) {
        
                if (Q[s][t] == 1) {
        
                    return false;
                }
            }
    
            // 判断左下方
            for (int s = i + 1, t = j - 1; s < size && t >= 0; s++, t--) {
        
                if (Q[s][t] == 1) {
        
                    return false;
                }
            }
    
            return true;
        }
    
        public static void main(String[] args) {
        
    
            QueenByBacktracking(4);
    
        }
    
    }

运行结果

![在这里插入图片描述][2942b33efa3a402e9785fe29149a2f84.png_pic_center]

答案就是这个，4皇后问题只有2种摆法是符合要求的。

如果是8皇后问题，

![在这里插入图片描述][d69a532cbcc4481fa5e7685ed2912298.png_pic_center]

一共是92 种摆法符合要求

###### 2 0-1背包问题 ######

【经典】

有n 个物品和一个背包，已知物品i 的重量为  w i w\_i wi，价值为  v i v\_i vi，背包的最大载量为c。

编写一个算法，使得装入背包中的物品总价值最大。

这是一个非常经典的问题，常用的解法包括穷举、动态规划、分支限界、回溯等。我们这次用回溯法来解决这个问题。

其实我们可以把n 个物品的取舍状态用一个向量进行表示  X = \{ x 0 , x 1 , . . . , x i , . . . , x n \} X = \\\{x\_0,x\_1,...,x\_i,...,x\_n\\\} X=\{ x0,x1,...,xi,...,xn\}

x i x\_i xi 只有0和1两种取值， x i x\_i xi = 1 代表将第i个物品装入背包， x i x\_i xi = 0代表不将第i 个物品放入背包。

所以0-1背包的实质就是找到这样一个向量  X = \{ x 0 , x 1 , . . . , x i , . . . , x n \} X = \\\{x\_0,x\_1,...,x\_i,...,x\_n\\\} X=\{ x0,x1,...,xi,...,xn\} ，x ∈ \{0,1\}，使得

∑ i = 1 n v i x i \\sum\_\{i=1\}^n v\_ix\_i ∑i=1nvixi 的值最大，并且要满足  ∑ i = 1 n w i x i ≤ c \\sum\_\{i=1\}^n w\_ix\_i ≤ c ∑i=1nwixi≤c 这个约束条件。

还有要注意的地方是，0-1背包问题的答案可能不唯一，所以在比较本次方案可装物品的总价值和记录中保存的总价值时，要考虑到相等的情况，如果相等，则需要将本次的装包方案连同可装物品的价值也记录下来，这样才能确保通过一遍深度优先搜索解空间树就可以得到 0-1 背包问题的全部解。

回溯法求解01背包问题的Java 描述：

import org.w3c.dom.ls.LSException;
    
    import java.util.ArrayList;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ZeroOneBackpackProblem
     * @Author: Ding Jiaxiong
     * @Data:2023/3/15 11:00
     */
    
    public class ZeroOneBackpackProblem {
        
    
        public static ArrayList<Integer> knapSackByBackTrack(int c, int[] x, int[] w, int v[]) {
        
            ArrayList<Integer> record = new ArrayList<Integer>();
    
            backTrack(c, 0, x, w, v, record);
            return record;
        }
    
        private static void backTrack(int c, int index, int[] x, int[] w, int v[], ArrayList<Integer> record) {
        
    
            if (index == x.length) {
        
                // 得到一个装包方案
                int value = 0;
                for (int i = 0; i < x.length; i++) {
        
                    if (x[i] == 1) {
        
                        value += v[i];
                    }
                }
    
                int lastPos = record.size() - 1;
                if (record.size() == 0 || record.get(lastPos) < value) {
        
                    record.clear();
                    for (int i = 0; i < x.length; i++) {
        
                        record.add(x[i]); // 更新为最新的装包方案
                    }
    
                    record.add(x.length, value);
                } else if (record.get(lastPos) == value) {
        
                    for (int i = 0; i < x.length; i++) {
        
                        record.add(lastPos + 1 + i, x[i]);
                    }
    
                    // 将value值置于装包方案后
                    record.add(lastPos + x.length + 1, value);
                }
    
                return;
            }
    
            if (c - w[index] >= 0) {
        
                x[index] = 1;
                backTrack(c - w[index], index + 1, x, w, v, record);
            }
    
            x[index] = 0;
            backTrack(c, index + 1, x, w, v, record);
        }
    
        public static void main(String[] args) {
        
    
            int[] x = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
            int[] w = {
        2, 7, 3, 4, 8, 5, 8, 6, 4, 16};
            int[] v = {
        15, 25, 8, 9, 15, 9, 13, 9, 6, 14};
    
            System.out.println(knapSackByBackTrack(34, x, w, v));
    
        }
    
    }

运行结果

![在这里插入图片描述][fecad787abba46fc9dc56b1f1647c63a.png_pic_center]

结果是有两种方案，最大价值都是 87 。

[2942b33efa3a402e9785fe29149a2f84.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5376982594d14164a2f0b94ee6e202f8.png
[d69a532cbcc4481fa5e7685ed2912298.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/50e8ccb475fa4fff8f2fd94e61fd5d83.png
[fecad787abba46fc9dc56b1f1647c63a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/48d77a6ebb874dbb8e066a9fb44c665a.png