Java教程

回溯算法及其案例用途

本文主要是介绍回溯算法及其案例用途,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

回溯算法是一种递归模式,它是一种暴力求解方法(brute force method),用于求出所有可能的解,回溯算法通常会构建一个状态空间树(state space tree),

将可能的组和从根到叶节点进行展开,然后以深度优先的方式搜索遍历状态树,遍历过程中遇到不符合解的节点立马返回进行新的遍历,而不是继续遍历,

状态空间树的结构可用下图进行描述:

 

 

 回溯算法不是用来求解最优解,而是用来求解可行解的方法,回溯算法的代码结构:

Backtrack(x)
    if x is not a solution
        return false  // return directly
    if x is a new solution
        add to list of solutions
    backtrack(expand x)

根据以上结构,用具体的示例进行分析,例如:

1、排队问题,假设有2个男孩和1个女孩,女孩不能站在男孩的中间,则可以用一个树的结构进行描述:

 树是构建好了,根据构建树构建代码:

arrange-boy-girl(p,index,result,mem)://index 用于记录孩子的位置,result是最终的排列结果,mem用于记录孩子是否已经排在队中了

  if index == p.length:

    print(result);//输出结果

  // expand p

  for i =0 to p.length:

    if(index == 2 && p[i]=='girl' || mem[i] ==1)://位置2不能是女孩,且该小孩没有在队列中,继续进行循环

      continue;    

    result[index]=p[i];//将小孩排到队中

    mem[i]=1;//记录一下,下次这个小孩不能再排了,因为已经在队伍中了

    index++;//排下一个位置

    arrange-boy-girl(p,index,result,mem);//递归调用,排下一个位置

    index--;//注意这里,index恢复原值,表示原来的index位置还可以安排下一个小孩,比如,位置0可以是boy1,也可以是boy2

    mem[i]=0;//这里也是,index恢复原值后,mem也要恢复原值

以上是一个全排列问题,但是它有一些限制,就是女孩不能排到男孩儿中间。

2、数的组合排列问题,给定一个数组 1 2 3,可以拼成多少种不同的两位数,每个数都可以重复利用,先构建组合树:

 

 

以上构建的是两位数,根据同样的方式还可以继续构建,可以是3位数,4位数,根据构建树编写程序:

combine-num(arr,depth,result):

  //递归的结束条件

  if depth == 2:

    print(result);

  // expand array  

  for int i =0 to arr.length:    

    result.add(arr[i]);//添加元素

    depth++;//走到下一个位置

    combine-num(arr,depth,result);

    depth--;//回溯到上一个位置

    result.removeLastNum();//将当前位置元素删除,相当于回溯到上一个位置以存放for循环中的第i+1个元素

本示例中,递归的结束条件是depth=2,如果需要是3位数,则depth=3,注意这里的“回溯”是在哪里体现的,就是“depth--”那个位置,表示返回

到上一个位置,将该位置放置第(i+1)个元素。

3、子集和的问题,给定一个集合{1,2,3,4,5,6,7,8,9,10}和一个值val=15,判断该集合中是否存在元素和为val的子集,如果有则输出该子集;

这个和上面的是一样的,也是一个组合问题,但是为了避免重复解的出现,比如 7+8=15,8+7=15;可以让每个元素只和它后面的元素进行组合;构造程序

如下:

def subset-sum(arr,fromIndex,sum,val,result):

  if sum==val:

    print(result);

  for i=fromIndex to arr.length:

    sum+=arr[i];//加上当前元素

    result.add(arr[i]);//将当前元素放到子集中

    subset-sum(arr,i+1,sum,val,result);// 注意这里,fromIndex变为了i+1,也就是当前元素只能和它后面的元素进行组合

    sum-=arr[i];//减去当前元素,回溯到上一个子集和的状态

    result.removeLast();//删除当前元素,回溯到上一个子集状态

4、八皇后问题,在8*8的空格列表中,每个空格可以放一个皇后,皇后可以攻击与它同行或同列的其他皇后,在该列表中摆放8个皇后,使其不能

互相攻击,求一共有多少种摆放方法;首先构造树结构,这里有一个4*4的列表结构:

 

 

从这棵树的构造过程,可以大体得出代码的构造过程,根节点到叶子节点的距离就是该叶子节点的深度,其实也就是行数rows;每行中空格的个数也就是

表格的列数cols,可以创建一个arr[rows][cols]的二维数组,然后构建代码:

N-Queens(arr,rows,cols,row):

  if row == rows://当前树的深度为表格的行数,也就是所有行都遍历了,则打印出结果

    print(arr);

  else:

    for col=0 to cols://遍历第depth行中的每个空格

      if isValid(arr,row,col,rows,cols):

        arr[row][col]=1;

        row+=1;//移动到下一行

        N-Queen(arr,rows,cols,row);//遍历下一行

        row-=1;//回溯到上一行,对上一行的下一个元素继续递归运算

        arr[row][col]=0;//将原来位置重新恢复原值0,注意这里代码是有先后顺序的,row-=1在前,恢复原值在后

      else:

        continue;//继续遍历该行的下一个元素

这里有一个isValid方法,用于判断row行和col列中没有皇后存在:

isValid(arr,row,col,rows,cols):

  for i=0 to rows and i!=row

    if arr[i][col]==1       return false; //存在皇后,该列非法

  for i=0 to cols and i!=col

    if arr[row][i]==1    return false; //存在皇后,该行非法     

  return true;//该空格所在的行和列都不存在皇后,是合法位置

总结:

回溯算法是和递归相关的,首先需要构建一个状态空间树,在代码层面是通过遍历和递归的形式构建一颗逻辑性的状态空间树,而非真的创建一个

树型的数据结构,在遍历和递归的过程中,这些执行路线构成了一个状态空间树,回溯算法的代码接口可如下表示:

backtrace(arr,result,xx):

  if xx满足条件:

    print(result)

  else

    for el in arr: //expand arr

      result.add(el);//做选择

      update xx;//更新条件

      backtrace(arr,result,xx);

      cancel xx;//撤销条件

      result.delete(el);//撤销选择  

回溯的难点就是构造树的过程,这是一个逻辑形式上的构建,通过遍历和递归加以实现,同时需要对执行过程对状态更新和撤销。 

 

 

 

 

   

这篇关于回溯算法及其案例用途的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!