回溯法

  大三上学习算法时都没怎么真正去体会算法的精髓，更没想过如何将它用到应用程序中？
想到找工作时算法数据结构作为基础，会经常被考到，于是最近有开始复习算法了。

        回溯递归，可以解决很多问题，比如迷宫问题，n皇后问题等
于是我通过看书学习，先实现了一个通用的回溯算法，与具体应用程序无关，回溯法核心是进行递归地找到目标位置，每次处于的位置，先判断是它是否符合要求，若符合，继续递归到下个位置，否则，回到上一个可选择的位置，BackTrack.java如下：

package 数据结构及算法.回溯法;

import java.util.Iterator;

public class BackTrack {
    Application app;
    
    public BackTrack(Application app){
    	this.app=app;
    }
    @SuppressWarnings("rawtypes")
	public boolean tryToSolve(Position pos){
    	boolean success=false;
    	Iterator itr=app.iterator(pos);

    	while(!success&&itr.hasNext()){
    		pos=(Position) itr.next();
    		if(app.valid(pos)){
    			app.record(pos);
    			//System.out.println(pos.getRow()+" "+pos.getColumn());
    			if(app.done(pos)){
        			success=true;
        			//System.out.println(app+"\n");
        		}
        		else{
        			success=tryToSolve(pos);
        			if(!success){
        				app.undo(pos);
        			}
        		}
    		}
    		
    	}
    	return success;
    }
}

每次处于的位置，用Position 类表示：

package 数据结构及算法.回溯法;

public class Position {
    private int column;
    private int row;
    public Position(){
    	this.row=0;
    	this.column=0;
    }
    public Position(int row,int column){
    	this.row=row;
    	this.column=column;
    }
    
    public int getRow(){
    	return this.row;
    }
    public int getColumn(){
    	return this.column;
    }
}

为实现具体应用程序给出接口 Application.java

package 数据结构及算法.回溯法;

import java.util.Iterator;


public interface Application {
    boolean valid(Position pos);//判断是否有效，符合要求
    void record(Position pos);//符合要求，就记录下来
    boolean done(Position pos);//表示找到目标
    void undo(Position pos);//从该位置下去无法找到目标，必须撤销，但可以留下撤销的痕迹，表示曾经走过
    String toString();//重写，方便输出
    Iterator iterator(Position pos);//可通过写个实现Iterator接口的内部类，用来存储该位置可以扩展的下面一系列的位置
}