回溯法及举例分析

回溯法，按照百度百科的介绍，是指一种选优的搜索法，按照选优条件向前搜索，以达到目标，但当搜索到某一步时发现原先的选择并不优或者不能达到目标，则退回上一步重新选择，这种走不通就退回重新选择再走的方法就是回溯法。

可用回溯法求解的问题P一般可以被如下描述：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<=i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i≥j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

使用回溯法的一般步骤：

（1）针对特定问题，确定问题的解空间

（2）确定易于搜索的解空间结构

（3）以深度优先方式搜索解空间，并在搜索过程中用减枝函数避免无效搜索。

下面我们讲述几个使用回溯法的例子。

首先我们先看一个关于象棋的问题，假设我们在一个4*4的棋盘上有一个马，马的位置为（1,1）点，当然也可以是其它点，我们要求列出所有的从（1,1）出发，最终能够回到起点的所有走法。

下面我们给出实现

package com.application.sample;
//使用回溯思想
public class backtrackingSample1 {
    static int[][] direction = {
   {-1, -1, -2, -2, 2, 2, 1, 1},{-2, 2, 1, -1, 1, -1, 2, -2}};
    private int[][] chess;
    private int x,y;
    private int total=0;
    public backtrackingSample1(int x,int y)
    {
        this.x=x;
        this.y=y;
        this.chess=new int[4][4];
        chess[x][y]=1;
    }
    private void output()
    {
//        if(isOneStep())
//        {
//            System.out.println("Total:"+this.total);
//            for(int i=0;i<4;i++)
//            {
//                for(int j=0;j<4;j++)
//                {
//                    System.out.print(chess[i][j]+" ");
//                }
//                System.out.println();
//            }
//            System.out.println();
//        }
        System.out.println("Total:"+this.total);
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                System.out.print(chess[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }
    public void findway(int posx,int posy,int step)
    {
        int px,py;
        for(int i=0;i<8;i++)
        {
            px=posx+direction[0][i];
            py=posy+direction[1][i];
            if(px>=0&&px<=3&&py>=0&&py<=3)
            {
                if(px==this.x&&py==this.y)
                {
                    this.total++;
                    this.output();
                }else if(chess[px][py]==0)
                {
                    chess[px][py]=step;
                    findway(px,py,step+1);
                    chess[px][py]=0;
                }
            }
        }
    }
    public boolean isOneStep()
    {
        boolean result=true;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(chess[i][j]>2)
                {
                    return false;
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        backtrackingSample1 sample=new backtrackingSample1(1,1);
        long start=System.currentTimeMillis();
        sample.findway(1, 1, 2);
        long end=System.currentTimeMillis();
        System.out.println("用时："+(end-start)+"毫秒");
    }
}

运行结果如下所示：

Total:1 0 0 5 2 4 1 0 0 0 0 3 6 0 0 0 0 Total:2 9 12 5 2 4 1 8 11 13 10 3 6 0 7 14 0 ........
Total:369
0 6 0 0 
4 1 10 7 
11 8 5 2 
0 3 12 9 
Total:370
0 0 0 0 
4 1 0 0 
0 0 5 2 
6 3 0 0 
用时：78毫秒

接下来我们看另外一个经典的问题九宫格。九宫格就是一个9*9的网格，而这个网格又可以被分成9个3*3的子网格，向网格中填入1~9的数字，要求每行，每列以及每个子网格中1-9都只出现一次，即不能有重复数字出现。如下所示，0表示待填入数据的格子

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

我们将9个子网格的编排如下所示：

对于用于标识元素在大的9*9网格中位置的变量i和j，有0<=i,j<=8，为了获取(i,j)元素在哪个小子网格中，我们做如下处理

假设k为小的3*3子网格的序号，则我们根据下面的关系可以得到(i,j)与k的关系

我们可以容易得到k=(i/3)*3+(j/3)；

下面给出java的实现：

package com.application.sample;
//使用回溯法求解九宫格问题
import java.util.Scanner;
public class BackTrackingSample2 {
    private int[][] table;
    private boolean[][] rstate;//rstate[i][value]=true表示value在第i行出现过
    private boolean[][] cstate;//cstate[j][value]=true表示value在第j行出现过
    private boolean[][] gstate;//gstate[k][value]=true表示value在第k个小网格中出现过
    private int[] pos;//存放需要填数字的方格位置
    private int posnum=0;//需要填的格子总数
    private boolean flag=false;//搜索结束标志
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BackTrackingSample2 sample=new BackTrackingSample2();
        sample.searchSolution(1);
    }
    public BackTrackingSample2()
    {
        table=new int[9][9];
        rstate=new boolean[9][10];
        cstate=new boolean[9][10];
        gstate=new boolean[9][10];
        pos=new int[81];
        System.out.println("输入九宫格的数据（使用0表示待填入数据的格子）：");
        Scanner in=new Scanner(System.in);
        String array=null;
        for(int i=0;i<9;i++)
        {
            array=in.nextLine();
            for(int j=0;j<9;j++)
            {
                table[i][j]=array.charAt(j)-'0';
                if(table[i][j]!=0)
                {
                    rstate[i][table[i][j]]=true;
                    cstate[j][table[i][j]]=true;
                    int k=(i/3)*3+(j/3);
                    gstate[k][table[i][j]]=true;
                }else
                {
                    pos[posnum++]=i*9+j;
                }
            }
        }
        pos[posnum]=-1;
    }
    private void output()//输出结果
    {
        System.out.println();
        System.out.println("结果：");
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                System.out.printf("%2d", table[i][j]);
            }
            System.out.println();
        }
    }
    public void searchSolution(int n)//搜索处理第n个待填入数据的格子
    {
        if(n>this.posnum)//如果所有的格子都处理完了则输出
        {
            output();
            return;
        }
        int row=pos[n-1]/9;//获取第n个待处理格子的坐标位置和子网格位置
        int column=pos[n-1]%9;
        int k=(row/3)*3+(column/3);
        for(int i=1;i<=9&&!flag;i++)//遍历，分别用1-9中的数进行试探
        {
            if(rstate[row][i]) //判断数组i在格所在的行和列以及子网格中是否出现过
                continue;
            if(cstate[column][i])
                continue;
            if(gstate[k][i])
                continue;
            table[row][column]=i;//填入该数，并设置标志
            rstate[row][i]=true;
            cstate[column][i]=true;
            gstate[k][i]=true;
            searchSolution(n+1);//回溯
            table[row][column]=0;//清除标志
            rstate[row][i]=false;
            cstate[column][i]=false;
            gstate[k][i]=false;
        }
    }
}

运行结果如下所示：

输入九宫格的数据（使用0表示待填入数据的格子）：
103000509
002109400 
000704000
300502006 
060000050
700803004 
000401000
009205800
804000107
结果：
 1 4 3 6 2 8 5 7 9
 5 7 2 1 3 9 4 6 8
 9 8 6 7 5 4 2 3 1
 3 9 1 5 4 2 7 8 6
 4 6 8 9 1 7 3 5 2
 7 2 5 8 6 3 9 1 4
 2 3 7 4 8 1 6 9 5
 6 1 9 2 7 5 8 4 3
 8 5 4 3 9 6 1 2 7

我们再讲一个比较经典的问题，那就是八皇后问题。什么是八皇后问题呢？八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

Java代码实现如下所示：

package com.application.sample;
//使用回溯法解决八皇后问题
public class BackTracingSample4 {
    private boolean[][] table=new boolean[8][8];
    private int queencount=0;
    private int total=0;
    public boolean lineHasQueen(int line)//line列全为false则返回true，否则返回false
    {
        for(int i=0;i<8;i++)
        {
            if(table[i][line]==true)
                return true;
        }
        return false;
    }
    public boolean catercornerHasQueen(int x,int y)//判断对角线方向是否含有皇后，如果有则返回true,否则返回false
    {
        int i,j;
        for(i=x,j=y;i<8&&j<8;i++,j++)
        {
            if(table[i][j]==true)
                return true;
        }
        for(i=x,j=y;i>=0&&j>=0;i--,j--)
        {
            if(table[i][j]==true)
                return true;
        }
        for(i=x,j=y;i>=0&&j<8;i--,j++)
        {
            if(table[i][j]==true)
                return true;
        }
        for(i=x,j=y;i<8&&j>=0;i++,j--)
        {
            if(table[i][j]==true)
                return true;
        }
        return false;
    }
    public void searchSolution(int line)
    {
        if(line==8)
            return;
        for(int i=0;i<8;i++)
        {
            if((!lineHasQueen(i))&&(!catercornerHasQueen(line,i)))
            {
                table[line][i]=true;
                queencount++;
                if(queencount==8)
                {
                    System.out.println();
                    output();
                    table[line][i]=false;
                    queencount--;
                    continue;
                }
                searchSolution(line+1);
                table[line][i]=false;
                queencount--;
            }
        }
    }
    public void output()
    {
        total++;
        System.out.println("Total:"+total);
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<8;j++)
            {
                if(table[i][j]==true)
                {
                    System.out.print("1");
                }else
                {
                    System.out.print("0");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BackTracingSample4 sample=new BackTracingSample4();
        sample.searchSolution(0);
    }
}

运行结果如下所示：

Total:1
10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000

Total:2
10000000
00000100
00000001
00100000
00000010
00010000
01000000

………….

Total:91
00000001
00100000
10000000
00000100
01000000
00001000
00000010
00010000

Total:92
00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000

最后我们来看一个大家基本都见过的题目，那就是上楼梯。对于一个含有n阶的楼梯，如果我们每次只能上一阶或者两阶，问我们总共可以有多少种走法，每种走法怎么走？

对于这个问题，我们很明显也可以使用回溯法进行求解。求解过程如下所示：

package com.application.sample;
public class BackTracingSample5 {
    private int[] step;    
    public BackTracingSample5(int n)
    {
        step=new int[n+1];
        step[0]=n;
    }
    public void goUp(int level,int n)
    {
        if(n>step[0])
            return;
        if(n==step[0])
        {
            output(level);
            return;
        }
        for(int i=1;i<=2;i++)
        {
            step[level+1]=i;
            goUp(level+1,n+i);
            step[level+1]=0;
        }
    }
    private void output(int level)
    {
        System.out.println("步数："+level);
        for(int i=1;i<=level;i++)
        {
            System.out.print(step[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BackTracingSample5 sample=new BackTracingSample5(5);
        sample.goUp(0, 0);
    }
}

运行结果如下所示：

步数：5
1 1 1 1 1
步数：4
1 1 1 2
步数：4
1 1 2 1
步数：4
1 2 1 1
步数：3
1 2 2
步数：4
2 1 1 1
步数：3
2 1 2
步数：3
2 2 1