一. 回溯算法（Back-tracking algorithm）

1.定义

遍历搜索空间并遇阻回溯的算法 -> 暴力求解+遇阻回溯。

遇阻回溯

解空间有结构：

  • 一个解由多个顺序子阶段决策构成。
  • 分阶段构造一个解。
  • 一旦某个阶段的解不可行，后面可以不再继续构造，回溯上一阶段尝试其他构造方式。

二. N皇后问题

1.题目描述



2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
package swu.xl.algorithm.code_06_02.experiment_1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class NQueen {
    /**
     * 递归的方式求解N皇后问题
     * @param n 皇后的数目
     */
    public static LinkedList<List<Integer>> getByRecursion(int n){
        //存储所有放置N皇后方式的集合
        LinkedList<List<Integer>> NQueens = new LinkedList<>();
        //存储一种放置N皇后方式的集合
        List<Integer> queens = new ArrayList<>();

        //初始化数据
        for (int i = 0; i < n; i++) {
            queens.add(-1);
        }

        //递归求解
        solveNQueue(queens,0,NQueens);

        return NQueens;
    }

    /**
     * 递归求解
     * @param queens
     * @param currentQueue
     * @param NQueens
     */
    private static void solveNQueue(List<Integer> queens, int currentQueue, LinkedList<List<Integer>> NQueens) {
        //获取每一行放置皇后的的列数
        int column = queens.size();

        //依次放置在每一列
        for (int i = 0; i < column; i++) {
            //设置当前皇后放置的位置
            queens.set(currentQueue,i);

            //判断是否可以放置
            if (check(queens,currentQueue)) {
                //判断是否都放置完毕
                if (currentQueue != column - 1){
                    //接着放置
                    solveNQueue(queens,currentQueue+1,NQueens);
                }else {
                    //放置完毕，产生了一种放置方法
                    List<Integer> temp_queues = new ArrayList<>(queens);
                    NQueens.add(temp_queues);
                }
            }
        }
    }

    /**
     * 迭代的方式求解N皇后的问题
     * @param n
     * @return
     */
    public static LinkedList<List<Integer>> getByIterate(int n){
        //存储所有放置N皇后方式的集合
        LinkedList<List<Integer>> NQueens = new LinkedList<>();
        //存储一种放置N皇后方式的集合
        List<Integer> queens = new ArrayList<>();

        //初始化数据
        for (int i = 0; i < n; i++) {
            queens.add(-1);
        }

        int currentQueue = 0;
        while (currentQueue >= 0){
            //放置当前皇后的位置
            queens.set(currentQueue,queens.get(currentQueue)+1);

            //如果发现位置不可以，往后移动直到找到一个适合的位置
            while (!check(queens,currentQueue) && queens.get(currentQueue) < n) {
                //找到合适的位置放置皇后
                queens.set(currentQueue,queens.get(currentQueue)+1);
            }

            if (queens.get(currentQueue) == n){
                //如果超出了位置，说明无法放置，回到上一层
                currentQueue--;
            }else {
                //判断是否都放置完毕
                if (currentQueue != n-1){
                    //接着放置
                    currentQueue++;
                    queens.set(currentQueue,-1);
                }else {
                    //放置完毕，产生了一种放置方法
                    List<Integer> temp_queues = new ArrayList<>(queens);
                    NQueens.add(temp_queues);
                }
            }
        }

        return NQueens;
    }


    /**
     * 检查位置是否合理
     * @param queues
     * @param currentQueue
     * @return
     */
    private static boolean check(List<Integer> queues, int currentQueue){
        for (int i = 0; i < currentQueue; i++) {
            if (Math.abs(queues.get(i) - queues.get(currentQueue)) == Math.abs(i - currentQueue)
                    || queues.get(i) == queues.get(currentQueue)){
                return false;
            }
        }

        return true;
    }

    /**
     * 测试程序
     * @param args
     */
    public static void main(String[] args) {
        //递归的方式
        LinkedList<List<Integer>> NQueues = getByRecursion(4);
        System.out.println("递归的方式：");
        for (List<Integer> queues : NQueues) {
            for (int i = 0; i < queues.size(); i++) {
                System.out.print(queues.get(i)+" ");
            }
            System.out.println();
        }

        //迭代的方式
        NQueues = getByIterate(4);
        System.out.println("迭代的方式：");
        for (List<Integer> queues : NQueues) {
            for (int i = 0; i < queues.size(); i++) {
                System.out.print(queues.get(i)+" ");
            }
            System.out.println();
        }
    }
}

//运行结果
递归的方式：
1 3 0 2 
2 0 3 1 
迭代的方式：
1 3 0 2 
2 0 3 1

三. 背包问题

1.题目描述

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/**
 * 背包问题
 */
public class Knapsack {
    /**
     * 回溯-迭代
     * @param items
     * @param capacity
     * @return
     */
    public static LinkedList<Integer> getByBacktrackIteration(int[][] items, int capacity){
        //物品的个数
        int n = items.length;
        //存储当前各个物品放置结果
        int[] current_park = new int[n+1];
        //初始化结果
        for (int i = 0; i <= n; i++) {
            current_park[i] = -1;
        }
        //存储最佳各个物品放置结果
        int[] best_pack = new int[n+1];
        //存储放置的最大价值
        int best_value = 0;
        //存储对应操作次数背包中存放的重量
        int[] packed_weight = new int[n+1];
        //存储对应操作次数背包中存放的价值
        int[] packed_value = new int[n+1];

        //从第一个物品开始操作
        int current_item = 1;
        while (current_item >= 1) {
            //设置当前物品的选择状态
            current_park[current_item] += 1;

            //不放入 第current_item个物品
            //放入 第current_item个物品，且不超过放入的容量
            if (current_park[current_item] == 0 ||
                    (current_park[current_item] == 1 &&
                            packed_weight[current_item-1] + items[current_item-1][0] <= capacity)) {

                //设置放置第current_item个物品的时候，此时背包中已经存放的重量
                packed_weight[current_item] = packed_weight[current_item-1] + items[current_item-1][0] * current_park[current_item];
                //设置放置第current_item个物品的时候，此时背包中存放物品的总价值
                packed_value[current_item] = packed_value[current_item-1] + items[current_item-1][1] * current_park[current_item];

                //如果 操作的物品次数 == 物品数
                if (current_item == n){
                    if (packed_value[current_item] > best_value){
                        best_value = packed_value[current_item];

                        best_pack = current_park.clone();
                    }
                }else {
                    //继续下一次操作
                    current_item = current_item + 1;
                }

            }else {
                //当前物品的选择状态（0，1）不对了，在回到上一位之前将当前次数的操作还原
                current_park[current_item] = -1;

                //回到上一位
                current_item = current_item - 1;
            }
        }

        //整理结果
        LinkedList<Integer> packedItems = new LinkedList<>();
        for (int i = 0; i <= n; i++) {
            if (best_pack[i] == 1) packedItems.add(i);
        }

        return packedItems;
    }

    /**
     * 回溯-递归
     * @param items
     * @param capacity
     * @return
     */
    public static LinkedList<Integer> getByBacktrackRecursion(int[][] items, int capacity) {
        //物品的个数
        int n = items.length;
        //存储当前各个物品放置结果
        int[] current_park = new int[n+1];
        //存储最佳各个物品放置结果
        int[] best_pack = new int[n+1];
        //存储放置的最大价值
        int[] best_value = {0};
        //存储对应操作次数背包中存放的重量
        int[] packed_weight = new int[n+1];
        //存储对应操作次数背包中存放的价值
        int[] packed_value = new int[n+1];

        //从第一个物品开始操作
        int current_item = 1;
        getByBacktrackRecursion(
                items,
                capacity,
                current_item,
                best_pack,
                best_value,
                current_park,
                packed_weight,
                packed_value
        );

        //整理结果
        LinkedList<Integer> packedItems = new LinkedList<>();
        for (int i = 0; i <= n; i++) {
            if (best_pack[i] == 1) packedItems.add(i);
        }

        return packedItems;
    }

    private static void getByBacktrackRecursion(int[][] items, int capacity, int current_item, int[] best_pack, int[] best_value, int[] current_park, int[] packed_weight, int[] packed_value) {
        //获取物品的个数
        int n = items.length;

        //操作的物品次数不能超过物品的个数
        if (current_item > n){
            return;
        }

        //循环控制
        for (int c = 0; c <= 1; c++){
            //设置当前物品的选择状态
            current_park[current_item] = c;

            //判断放置的物品总重量是否已经超过背包的容量
            if (packed_weight[current_item-1] + items[current_item-1][0] * c <= capacity){

                //设置放置第current_item个物品的时候，此时背包中已经存放的重量
                packed_weight[current_item] = packed_weight[current_item-1] + items[current_item-1][0] * c;
                //设置放置第current_item个物品的时候，此时背包中存放物品的总价值
                packed_value[current_item] = packed_value[current_item-1] + items[current_item-1][1] * c;

            }

            //如果 操作的物品次数 == 物品数
            if (current_item == n){

                //如果当前的放置结果得到的价值更大，更新
                if (packed_value[current_item] > best_value[0]){

                    best_value[0] = packed_value[current_item];

                    for (int i = 0; i <= n; i++) {
                        best_pack[i] = current_park[i];
                    }
                }
            }

            //下一个物品
            getByBacktrackRecursion(
                    items,
                    capacity,
                    current_item+1,
                    best_pack,
                    best_value,
                    current_park,
                    packed_weight,
                    packed_value
            );
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class KnapsackTest {
    public static void main(String[] args) {
        int[][] items = {{2,12},{1,10},{3,20},{2,15}};
        int capacity = 5;

        LinkedList<Integer> packedItemsByIteration = Knapsack.getByBacktrackIteration(items, capacity);
        int packedValueByIteration = 0;
        for(int i : packedItemsByIteration) {
            packedValueByIteration += items[i-1][1];
        }

        LinkedList<Integer> packedItemsByRecursion = Knapsack.getByBacktrackRecursion(items, capacity);
        int packedValueByRecursion = 0;
        for(int i : packedItemsByRecursion) {
            packedValueByRecursion += items[i-1][1];
        }

        System.out.println("Iteration: packed items " + packedItemsByIteration + " packed value " + packedValueByIteration);
        System.out.println("Recursion: packed items " + packedItemsByRecursion + " packed value " + packedValueByRecursion);
    }

}
//运行结果
Iteration: packed items [1, 2, 4] packed value 37
Recursion: packed items [1, 2, 4] packed value 37