回溯算法解决n后问题和0-1背包问题

回溯算法运用练习
一、实验目的
本次实验是针对回溯算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

三、 实验项目

1．请用回溯法对下列问题进行求解。
题目（4选2）：（1）数读问题（标准数读）；（2）n后问题；（3）0-1背包问题；（3）四城市旅行商问题。

四、实验过程

（一）题目一：0-1背包问题

1. 题目分析:
   0-1背包问题是典型的回溯问题，所谓回溯就是按照深度优先的策略遍历解空间树，对于每一个节点都先判断该节点是否包含问题的解，如果不包含对该节点进行剪枝，跳过以该节点为根的子树的搜索，逐层向其父节点进行回溯，否则进入该子树进行深度优先遍历。
   本题就是利用了回溯的思想，下面拿可选物品数量为3的背包问题进行举例分析
   n=3时的解空间树：

   现在已知每个物品的权值，要对每个物品进行舍取（拿或者不拿，也就是上图中的0或者1的分支），现在要选择一种最优的选取方式。
   一共有2¬ 3=8种请况（A到叶子节点），先根据题目规定一个合理的剪枝函数，然后从根节点进行深度优先遍历，当不满足函数时，放弃以该节点为根节点的子树进行回溯，直至找到最优解。

2. 算法构造
   首先先定义了几个全局的静态变量：
   private static int[] price;//物品的价值数组
   private static int[] weight;//物品的重量数组
   private static int current;//最大可以拿的重量
   private static int count;//物品的个数
   private static int bestp;//目前最优装载的价值
   private static int residueprice;//剩余物品的价值
   private static int cw;//当前的重量
   private static int cp;//当前的价值
   private static int[] c_answer;//存放当前解
   private static int[] best_answer;//存放最终解

然后有回溯函数
根据以下三种不同条件进行不同的操作：
if(t>count) //遍历到叶子结点

if(cw+weight[t]<=current) //如果在该节点下存在可能解，则遍历当前子树（左子树）

if(cp+residueprice>bestp) {//当前子树下不存在可能解，进行剪枝操作

3. 算法实现
   package com.cn;
   import java.util.Scanner;

public class Package {
private static int[] price;//物品的价值数组
private static int[] weight;//物品的重量数组
private static int current;//最大可以拿的重量
private static int count;//物品的个数
static int bestp;//目前最优装载的价值
private static int residueprice;//剩余物品的价值
private static int cw;//当前的重量
private static int cp;//当前的价值
private static int[] c_answer;//存放当前解
private static int[] best_answer;//存放最终解
public static int Loading(int[] ww,int[] pp, int cc) {

//初始化数据成员，数组下标从1开始
count=ww.length-1;
weight=ww;
price=pp;
current=cc;//给三个数组赋予初值
cw=0;
bestp=0;
c_answer=new int[count+1];
best_answer=new int[count+1];
//初始化r，即剩余最大价格
for(int i=1;i<=count;i++) {
residueprice+= price[i];
}
//调用回溯法计算
BackTrack(1);//从第一个节点开始检查
return bestp;//返回最优价值
}
public static void BackTrack(int t) {//回溯
if(t>count) {//遍历到叶子结点
if(cp>bestp) {//如果当前价值大于最优价值
for(int i=1;i<=count;i++) {
best_answer[i] =c_answer[i];//把当前解放入最优解中
}
bestp=cp;//当前价格置位最优价格
}
return;
}
residueprice-=price[t];
if(cw+weight[t]<=current) {//如果在该节点下存在可能解，则遍历当前子树（左子树）
c_answer[t]=1;
cp+=price[t];
cw+=weight[t];
BackTrack(t+1);
cp-=price[t];//恢复现场
cw-=weight[t];//恢复现场
}
if(cp+residueprice>bestp) {//当前子树下不存在可能解，进行剪枝操作
c_answer[t]=0;//搜索右子树
BackTrack(t+1);
}
residueprice+=price[t];//恢复现场
}
public static void main(String[] args) {
int c1;
int n;
System.out.println("请输入您要比较的数字串长度");
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();//规定数组长度
int w1[]=new int[n];
for(int i=0;i<n;i++){
System.out.println("请输入第"+i+"个数字，还需输入"+(n-i)+"个");
Scanner scanner1=new Scanner(System.in);
w1[i]=scanner1.nextInt();
}
System.out.println("------------------------------------------------------------------------------------------------");
int p1[]=new int[n];
for(int i=0;i<n;i++){
System.out.println("请输入第"+i+"个权值，还需输入"+(n-i)+"个");
Scanner scanner1=new Scanner(System.in);
p1[i]=scanner1.nextInt();
}
System.out.println("请输入最大的装载值");
Scanner scanner1=new Scanner(System.in);
c1=scanner1.nextInt();
//System.out.println("最大的装载值"+c1);
Loading(w1,p1,c1);
System.out.println("最优装载为："+bestp);
for(int i=1;i<=count;i++) {
System.out.print(best_answer[i]+" ");
}
}

}
4. 运行结果

5. 经验归纳
   回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索到才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题的算法称为回溯法，适合解组合数较大的问题。

（二）题目二：N皇后问题

1. 题目分析:
   N皇后问题也是经典的回溯问题，所谓回溯就是按照深度优先的策略遍历解空间树，对于每一个节点都先判断该节点是否包含问题的解，如果不包含对该节点进行剪枝，跳过以该节点为根的子树的搜索，逐层向其父节点进行回溯，否则进入该子树进行深度优先遍历。
   这个问题的诞生背景是源于国际象棋，名为Queen的棋子可以“吃掉”和自己位于一条横线，纵线，和斜线的每一颗棋子，现将八个Queen放置在一个88的棋盘之上，问有几种放置方法让它们都能够存活下来。这就是所谓的8皇后问题了，N皇后问题就是在8皇后问题上的改良。
   现在拿四皇后问题来进行分析寻找解题规律：
   44的棋盘上，安置4个皇后：

将第一个Queen放在（1,1）后，下图中黑色的区域不能放棋子：

再从第二行中可放位置选择一个进行安置，选择（2,3）：

全部锁死不能，这种情况作废，进行回溯再寻出路
返回上一步，将Queen的位置放在（2，4）：

可行将这种情况放入解集之中。
再找寻下一种情况，返回第一行将Queen安置在（1,2）位置：

重复上面动作即可求出问题最优解
2. 算法构造
在此论证算法设计中的一些必要的设计依据。
判断每行每列只放置一个皇后：if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))
3. 算法实现
package com.cn;

import java.util.Scanner;

public class Queen {
int[] x;//将当前解，存入数组之中
int N;//皇后个数
int sum = 0;//当前已找到的可行方案数
public int totalNQueens(int n) {
N=n;
x=new int[N+1];
backTrace(1);
return sum;
}
//col行这个点，x[col]列这个点，与已经存在的几个皇后，是否符合要求，放到这个位置上，

private boolean place(int col){//检测该点是否可以放置皇后
for(int i = 1; i < col; i++){
if(Math.abs(col - i)==Math.abs(x[col]-x[i])||x[col]==x[i]){//函数名: abs 功 能: 求整数的绝对值
//防止出现负数影响程序运行
return false;
}
}
return true;
}
private void backTrace(int t) {//回溯
if(t>N){
sum++;
}else {
//第t行，遍历所有的节点
for(int j = 1; j <= N; j++) {
x[t] = j ;
//如果第j个节点可以放下皇后
if(place(t)){
//接着放下一个
backTrace(t+1);
}
}
}
}
public static void main(String[] args) {
Queen queen = new Queen();
System.out.println("请输入皇后的个数N，本程序会计算N*N的棋盘中，N个皇后有少种安置方式");
Scanner scanner=new Scanner(System.in);
int N=scanner.nextInt();
System.out.println(N+"个皇后有"+queen.totalNQueens(N)+"种安置方式");
}

}
4. 运行结果

5. 经验归纳
   n后问题采用递归回溯的方法解决，从第一个皇后开始依次往下找满足条件（任何2个皇后不放在同一行或同一列或同一斜线上）的皇后，直到进行完为止。
   五、实验总结
   以上两个问题都是需要递归遍历，采用回溯法。0-1背包问题是用动态规划方法做的这个算法是动态规划的典型应用；n后问题关键是判断任意两个皇后不在同一行，同一列或同一斜线上的限制条件。

最后

以上就是端庄小白菜为你收集整理的回溯算法解决n后问题和0-1背包问题的全部内容，希望文章能够帮你解决回溯算法解决n后问题和0-1背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。