【算法设计与分析】——搜索算法
🎃个人专栏：
🐬 算法设计与分析：算法设计与分析_IT闫的博客-CSDN博客
🐳Java基础：Java基础_IT闫的博客-CSDN博客
🐋c语言：c语言_IT闫的博客-CSDN博客
🐟MySQL：数据结构_IT闫的博客-CSDN博客
🐠数据结构：??????数据结构_IT闫的博客-CSDN博客
💎C++：C++_IT闫的博客-CSDN博客
🥽C51单片机：C51单片机（STC89C516）_IT闫的博客-CSDN博客
💻基于HTML5的网页设计及应用：基于HTML5的网页设计及应用_IT闫的博客-CSDN博客??????
🥏python：python_IT闫的博客-CSDN博客
🐠离散数学：离散数学_IT闫的博客-CSDN博客
欢迎收看，希望对大家有用！
目录
🎯目的：
1）了解回溯算法思想；
2）掌握回溯法的算法框架；
3）能够针对实际问题，按照回溯法算法框架，分析问题的解空间、解空间的组织结构、搜索的约束条件、限界条件；
4）能够正确的编码；
5）能够正确分析算法的时间复杂度和空间复杂度。
🎯内容概括：
- 使用回溯法解决n皇后问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
0-1背包问题的回溯算法与分支限界算法的实现：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为W。一个物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大？
例如：物品数目n=4，限重W=7，物品重量分别为w=(3,5,2,1)，价值为v=(9,10,7,4)，最优解为：（1，0，1，1）。
🎯基本步骤：
1）明确题目的已知条件和求解的目标；
2）问题建模；
3）算法设计；
4）编码实现；
5）测试数据；
6）程序运行结果；
7）分析实验结果是否符合预期，如果不符合，分析可能的原因；
8）算法分析。
🎯内容：
🐟one：
🎐问题：
????????使用回溯法解决n皇后问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
🎐解题思路：
- 创建一个大小为n×n的棋盘。
- 从第一行开始，在每一行选择一个位置放置皇后，保证不受攻击。
- 在放置皇后的过程中，需要检查当前位置是否满足放置条件，即不与之前放置的皇后冲突。
- 如果找到一个满足条件的位置，继续递归地在下一行放置皇后。
- 如果在某一行无法找到合适的位置，回溯到上一行，尝试放置皇后的其他位置。
- 当所有行都放置了皇后，得到一个解。
- 继续回溯，寻找其他解。
🎐代码分析：
package test20210110;
public class Test01 {
public static void main(String[] args) {
NQueens nQueens = new NQueens();
nQueens.solveNQueens(4);
}
}????????这段代码定义了一个
Test01类，包含了程序入口main方法。在main方法中创建了一个NQueens的实例，并调用solveNQueens方法，传入参数4，表示要解决4皇后问题。?
class NQueens {
private int[] queens; // 皇后在每一行的列索引
private int n; // 棋盘大小
public void solveNQueens(int n) {
this.n = n;
queens = new int[n];
backtrack(0);
}
private void backtrack(int row) {
if (row == n) {
// 打印解决方案
printQueens();
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col)) {
queens[row] = col;
backtrack(row + 1);
}
}
}
private boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
return false;
}
}
return true;
}
private void printQueens() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (queens[i] == j) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
System.out.println();
}
}
????????这段代码定义了一个
NQueens类，用于解决N皇后问题。类中包含了solveNQueens方法、backtrack方法、isValid方法和printQueens方法。
solveNQueens方法用于解决N皇后问题，接受一个整数参数n，表示要解决的棋盘大小。在方法中，首先初始化queens数组和n变量，然后调用backtrack方法，传入参数0，表示从第0行开始搜索。
??backtrack方法用于使用回溯算法来解决N皇后问题。接受一个整数参数row，表示当前处理的行数。???????如果
row等于n，即已经处理完所有行，就打印出解决方案，即调用printQueens方法，并返回。???????否则，对于当前行的每一列，判断是否能够放置皇后，即调用
isValid方法。???????如果可以放置皇后，就将列索引记录在
queens数组中，并递归调用backtrack方法处理下一行。
??isValid方法用于判断当前位置是否可以放置皇后。遍历之前的行，检查是否与之前的皇后冲突。如果与之前的皇后冲突，返回false；否则，返回true。
printQueens方法用于打印解决方案。遍历每一行和每一列，根据queens数组中的列索引来输出相应的字符（"Q"代表皇后，"."代表空格）。每打印完一行，就换行，并在最后打印一个空行。
🎐总代码：
package test20210110;
public class Test01 {
public static void main(String[] args) {
NQueens nQueens = new NQueens();
nQueens.solveNQueens(4);
}
}
class NQueens {
private int[] queens; // 皇后在每一行的列索引
private int n; // 棋盘大小
public void solveNQueens(int n) {
this.n = n;
queens = new int[n];
backtrack(0);
}
private void backtrack(int row) {
if (row == n) {
// 打印解决方案
printQueens();
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col)) {
queens[row] = col;
backtrack(row + 1);
}
}
}
private boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
return false;
}
}
return true;
}
private void printQueens() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (queens[i] == j) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
System.out.println();
}
}🐟two：
🎐 问题：
????????0-1背包问题的回溯算法与分支限界算法的实现：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为W。一个物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大？
例如：物品数目n=4，限重W=7，物品重量分别为w=(3,5,2,1)，价值为v=(9,10,7,4)，最优解为：（1，0，1，1）。
🎐解题思路：
回溯算法：
- 使用回溯算法可以尝试所有可能的解决方案，找到总价值最大的解。
- 从第一个物品开始，逐个考虑将其放入背包或不放入背包的情况。
- 对于每个物品，如果放入背包不超重，则递归地考虑下一个物品，并更新当前总价值。
- 当考虑完所有物品或背包已满时，比较当前总价值与历史最大总价值，更新最大总价值和最优解。
- 通过递归回溯，可以尝试所有可能的组合，最终找到最优解。
分支限界算法：
- 使用分支限界算法可以更高效地找到最优解。
- 使用优先队列来维护待扩展的节点，节点的优先级根据上界来确定，上界越大表示该节点可能包含更优解。
- 从根节点开始，依次扩展节点，生成子节点。
- 对于每个子节点，计算其上界，如果上界大于当前的最优解，将子节点加入优先队列。
- 通过不断扩展和剪枝，优先队列中的节点会按照优先级被处理，直到队列为空或无法生成更优的节点。
- 当队列为空时，得到的最优解即为问题的解。
🎐代码分析：
第一部分：导入相关包
package one;
import java.util.*;
这部分代码用于导入所需的包，包括
java.util包，以便使用ArrayList、LinkedList和Collections等类。??
第二部分：定义物品类
Item和节点类Node?
private static class Item implements Comparable<Item> {
int weight;
int value;
double density;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
this.density = (double) value / weight;
}
@Override
public int compareTo(Item other) {
return Double.compare(other.density, this.density);
}
}
private static class Node {
int level;
int weight;
int value;
double bound;
public Node(int level, int weight, int value, double bound) {
this.level = level;
this.weight = weight;
this.value = value;
this.bound = bound;
}
}
?这部分代码定义了两个内部类
Item和Node。Item类表示背包中的物品，有重量(weight)、价值(value)和价值密度(density)属性。Node类表示搜索树上的节点，具有层级(level)、总重量(weight)、总价值(value)和价值上界(bound)属性。
第三部分：解决背包问题的方法
solveKnapsack?
public static int solveKnapsack(int maxWeight, int[] weights, int[] values) {
// ... 省略部分代码 ...
}
这部分代码定义了一个静态方法
solveKnapsack，用于解决背包问题。它接受最大承重(maxWeight)、物品重量数组(weights)和物品价值数组(values)作为输入参数，并返回最优解的最大价值。?
第四部分：计算价值上界的方法
bound?
private static double bound(int level, int weight, int value, List<Item> items, int maxWeight) {
// ... 省略部分代码 ...
}
这部分代码定义了一个私有静态方法
bound，用于计算给定节点的价值上界。它接受层级(level)、当前总重量(weight)、当前总价值(value)、物品列表(items)和最大承重(maxWeight)作为输入参数，并返回价值上界。?
第五部分：主函数
main?
public static void main(String[] args) {
// ... 省略部分代码 ...
}
?这部分代码定义了主函数
main，在其中创建了一个具体的背包问题实例，调用solveKnapsack方法求解最大价值，并输出结果。
🎐总代码：
package one;
import java.util.*;
public class Knapsack {
private static class Item implements Comparable<Item> {
int weight;
int value;
double density;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
this.density = (double) value / weight;
}
@Override
public int compareTo(Item other) {
return Double.compare(other.density, this.density);
}
}
private static class Node {
int level;
int weight;
int value;
double bound;
public Node(int level, int weight, int value, double bound) {
this.level = level;
this.weight = weight;
this.value = value;
this.bound = bound;
}
}
public static int solveKnapsack(int maxWeight, int[] weights, int[] values) {
int n = weights.length;
List<Item> items = new ArrayList<>();
for (int i = 0; i < n; i++) {
items.add(new Item(weights[i], values[i]));
}
Collections.sort(items);
Queue<Node> queue = new LinkedList<>();
Node root = new Node(-1, 0, 0, 0);
queue.offer(root);
int maxValue = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
int level = node.level + 1;
int weight = node.weight;
int value = node.value;
if (level == n) {
if (value > maxValue) {
maxValue = value;
}
continue;
}
if (weight + items.get(level).weight <= maxWeight) {
int newValue = value + items.get(level).value;
if (newValue > maxValue) {
maxValue = newValue;
}
queue.offer(new Node(level, weight + items.get(level).weight, newValue, node.bound));
}
if (bound(level + 1, weight, value, items, maxWeight) > maxValue) {
queue.offer(new Node(level, weight, value, bound(level + 1, weight, value, items, maxWeight)));
}
}
return maxValue;
}
private static double bound(int level, int weight, int value, List<Item> items, int maxWeight) {
double bound = value;
int n = items.size();
int totalWeight = weight;
while (level < n && totalWeight + items.get(level).weight <= maxWeight) {
bound += items.get(level).value;
totalWeight += items.get(level).weight;
level++;
}
if (level < n) {
bound += (maxWeight - totalWeight) * items.get(level).density;
}
return bound;
}
public static void main(String[] args) {
int[] weights = {3, 5, 2, 1};
int[] values = {9, 10, 7, 4};
int maxWeight = 7;
int maxValue = solveKnapsack(maxWeight, weights, values);
System.out.println("The maximum value that can be obtained: " + maxValue);
}
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！