一、什么是回溯算法

回溯算法实际上是一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

回溯算法实际上是一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径。

八皇后问题:

N皇后问题要求求解在N*N的棋盘上放置N个皇后,并使各皇后彼此不受攻击的所有可能的棋盘布局。皇后彼此不受攻击的约束条件是:任何两个皇后均不能在棋盘上同一行、同一列或者同一对角线上出现。

由于N皇后问题不允许两个皇后在同一行,所以,可用一维数组X表示N皇后问题的解,X[i]表示第i行的皇后所在的列号。关键是代码中把待处理行中不可用的点找出来。

由上述X数组求解N皇后问题,保障了任意两个皇后不在同一行上,而判定皇后彼此不受攻击的其他条件,可以描述如下:

1. X[i] = X[s],则第i行与第s行皇后在同一列上。

2. 如果第i行的皇后在第j列,第s行皇后在第t列,即X[i] = j和X[s] = t,则只要 i-j = s-t 或者 i+j = s+t,说明两个皇后在同一对角线上。

对两个等式进行变换后,得到结论:只要|i-s| = |j-t|(即i-s = X[i]-X[s]),则皇后在同一对角线上。

解N皇后问题需要遍历解空间树,遍历中要随时判定当前结点棋盘布局是否符合要求,符合要求则继续向下遍历,直至判断得到一个满足约束条件的叶子结点,从而获得一个满足要求的棋盘布局;不符合要求的结点将被舍弃(称之为剪枝),并回溯到上一层的结点继续遍历。当整棵树遍历结束时,已获得所有满足要求的棋盘布局。

publicclassQueen{//方案数publicstaticintnum=0;//皇后数publicstaticfinalintMAXQUEEN=8;//定义数组,表示MAXQUEEN列棋子中皇后摆放位置publicstaticint[]cols=newint[MAXQUEEN];publicvoidgetCount(intn){boolean[]rows=newboolean[MAXQUEEN];for(intm=0;m<n;m++){//rows为true表名不可以放,垂直上面不可放rows[cols[m]]=true;intd=n-m;//y=x这条线往前判断if(cols[m]-d>=0){rows[cols[m]-d]=true;}//y=-x这条线往右边判断if(cols[m]+d<=(MAXQUEEN-1)){rows[cols[m]+d]=true;}}for(inti=0;i<MAXQUEEN;i++){if(rows[i]){//如果这一行中的某个列位置不可放置则继续看下个位置。continue;}cols[n]=i;//如果下面还没填充完毕则仍需合法位置if(n<MAXQUEEN-1){getCount(n+1);}else{//找到完整的一套方案num++;printQueen();}}}privatevoidprintQueen(){System.out.println("第">

背包问题:

问题:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
分析:问题是n个物品中选择部分物品,可知,问题的解空间是子集树。比如物品数目n=3时,其解空间树如下图,边为1代表选择该物品,边为0代表不选择该物品。使用x[i]表示物品i是否放入背包,x[i]=0表示不放,x[i]=1表示放入。回溯搜索过程,如果来到了叶子节点,表示一条搜索路径结束,如果该路径上存在更优的解,则保存下来。如果不是叶子节点,是中点的节点(如B),就遍历其子节点(D和E),如果子节点满足剪枝条件,就继续回溯搜索子节点。

【整体思路】

　　01背包属于找最优解问题,用回溯法需要构造解的子集树。对于每一个物品i,对于该物品只有选与不选2个决策,总共有n个物品,可以顺序依次考虑每个物品,这样就形成了一棵解空间树:基本思想就是遍历这棵树,以枚举所有情况,最后进行判断,如果重量不超过背包容量,且价值最大的话,该方案就是最后的答案。深度遍历的意思。

packagepractice;/***给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?**@authorfulisha**/publicclass_05{staticintBestValue=0;//最优值;当前的最大价值,初始化为0staticint[]BestX;//最优解;BestX[i]=1代表物品i放入背包,0代表不放入//staticintCurWeight=0;//当前放入背包的物品总重量staticintCurValue=0;//当前放入背包的物品总价值staticintN=3;//物品数量staticintC=16;//物品的总容量staticintW[]={10,8,5};//每个物品的重量staticintv[]={5,4,1};//每个物品的价值staticintx[]={0,0,0};//x[i]=1代表物品i放入背包,0代表不放入publicstaticintbacktrack(intt){//如果是子节点当前价值和**价值做判断保存**价值if(t>N-1){if(CurValue>BestValue){BestValue=CurValue;}returnBestValue;}//如果不是子节点对子节点进行遍历else{//就两种情况取或不取用0/1表示for(inti=0;i<=1;i++){x[t]=i;if(i==0){//如果是不取就不需要进行判断直接到下一个节点backtrack(t+1);}else//放入背包就进行约束条件判断放入背包的东西是否合法{if(CurWeight+W[t]<=C){CurWeight+=W[t];CurValue+=v[t];//当东西装进入背包后你可以进行对下个商品的判断了backtrack(t+1);//能执行以下两个语句就说明你回溯到了上一个节点//所以你就需要恢复现场把你刚刚拿的东西退出来//我们要冲上一个节点又要重新来遍历如果不减你就会多加一遍CurWeight-=W[t];CurValue-=v[t];}}}}returnBestValue;}publicstaticvoidmain(String[]args){backtrack(0);System.out.println(BestValue);for(inti=0;i<3;i++){//System.out.println(BestX[i]);}}}

也可以考虑剪枝的操作哦:剪枝操作

迷宫问题

首先我们定义一个 n * n 的二维数组,模拟迷宫,用2这个数字表示迷宫的墙壁 ,0表示迷宫的路线 ,那么我们主要的思路就是 在迷宫的入口判断入口的上下左右 哪一个方向不是墙壁 我们则进入进去,同时我们用1 这个数字表示走过的路线 0表示不通的路线 这就是我们大致的思路,关键是用完后记得把节点环境恢复下。

publicclassTestMaze{//定义一个二维数组做迷宫privateint[][]maze=null;//表示此迷宫一共有几种走法privateintcount=0;//迷宫的开始位置和结束位置的坐标privatestaticintstartI,startJ,endI,endJ;privatevoidsetStart(inti,intj){startI=i;startJ=j;}privatevoidsetEnd(inti,intj){endI=i;endJ=j;}privatevoidshow(){System.out.println("第">{2,2,2,2,2,2,2,2},{2,0,0,0,0,2,2,2},{2,0,2,0,0,0,2,2},{2,0,0,2,0,2,0,2},{2,0,0,2,0,2,2,0},{2,0,2,0,0,0,0,2},{2,0,0,0,0,2,0,2},{2,2,2,2,2,2,2,2}};myMaze.maze=maze;myMaze.setStart(1,1);myMaze.setEnd(6,6);myMaze.play(1,1);}}

生成有效的括号组合:

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。括号只有{}[]()这三种。

例如,给出 n = 3,生成结果为:

["((()))","(()())","(())()","()(())","()()()"]

解法:

/***list:用来存储符合要求的括号组合。*局部变量temp:表示当前函数的括号组成样式。*计数器x:判断递归次数,限制其底界。*总的形成括号对数n。**/publicList<String>generateParenthesis(intn){List<String>list=newArrayList<>();add_list(list,"(",1,n*2);returnlist;}//书写递归函数publicvoidadd_list(List<String>list,Stringtemp,intx,intn){x++;if(x<=n){//尽可能罗列括号的存在add_list(list,temp+"(",x,n);add_list(list,temp+")",x,n);}if(x>n){//在这里写判断条件是否负荷有效的括号组合char[]k=temp.toCharArray();//计数器inttimer=0;for(inti=0;i<k.length;i++){//无论何时(个数>=)个数if(timer<0||timer>n/2){return;}else{if(k[i]=='('){timer++;}else{timer--;}}}if(timer==0)list.add(temp);}}====importjava.util.ArrayList;importjava.util.List;publicclassgenerateParenthesis{//参数有n对的{}()[],publicstaticList<String>generater(intn){List<String>result=newArrayList<String>();generaterOneByOne("",result,n,n);returnresult;}/***left:左边的括号就n个*right:右边的括号有n个*思想:*必须先放左边的括号,以递归的方式,然后直到左边的括的数目小于0时,以及右边的括号为0时,截止并放到结果中*右边的括号要后放:也就是right>left,保证右括号大于左边括号的数目*@paramsubstring*@paramresult*@paramleft*@paramright*/privatestaticvoidgeneraterOneByOne(Stringsubstring,List<String>result,intleft,intright){if(left==0&&right==0){result.add(substring);return;}if(left>0){generaterOneByOne(substring+"(",result,left-1,right);}if(right>left){generaterOneByOne(substring+')',result,left,right-1);}}}

到此,相信大家对“回溯算法是什么”有了更深的了解,不妨来实际操作一番吧!这里是本站网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!