eightdigits.java

八数码

import java.util.Vector;
import java.lang.Math;


public class EightDigits {
	private Vector vecClose = new Vector();//记录下已经扩展的节点
	private Vector vecOpen = new Vector();//记录下未扩展的节点
	
	private int[] startS = new int[]{2,8,3,1,0,4,7,6,5};
	private int[] endS = new int[]{1,2,3,8,0,4,7,6,5};//有解
	
	//private int[] startS = new int[]{7,2,4,5,0,6,8,3,1};
	//private int[] endS = new int[]{0,1,2,3,4,5,6,7,8};//无解
	
	private State nowState = null;
	private State endState = new State(endS);
	
	private State startState = new State(startS);
	
	private int HeuristicF1(State st){
		//曼哈顿距离
		
		int[] s = st.getState();
		int[][] s2 = new int[3][3];
		int[][] e2 = new int[3][3];
		int steps = 0;
		
		for(int i=0;i<3;i++){
			for(int j =0;j<3;j++){
				e2[i][j] = endS[3*i+j];
			}
		}//将一维储存的数组转换成二维，结束状态
		for(int i=0;i<3;i++){
			for(int j =0;j<3;j++){
				s2[i][j] = s[3*i+j];
			}
		}//将一维储存的数组转换成二维
		
		for(int i=0;i<3;i++){
			for(int j =0;j<3;j++){
			   if(s2[i][j]==0)continue;//如果是空格就跳过
			   for(int k=0;k<3;k++){
			       for(int h=0;h<3;h++){
			    	   if(s2[i][j]==e2[k][h]){
			    		   steps = steps+Math.abs(i-k)+Math.abs(j-h);
			    	   }//if
			       }//h
			   }//k
		    }//j
		}//计算所有数值i
		return steps;
		
	}
	private int HeuristicF2(State st){
	//不在位棋子数
		int steps = 0;
		
		int[] s = st.getState();
		for(int i=0;i<9;i++){
			if(s[i]==0)continue;
			if(s[i]!=endS[i])steps++;
		}
		return steps;
	}
	
	private boolean haveContained(State st){
	    int size = vecClose.size();
	    State temp;
	    
	    for(int i=0;i<size;i++){
	    	temp = (State)vecClose.elementAt(i);
	    	if(temp.equals(st))return true;
	    }
	    return false;
	}//判断是否已经扩展过
	
	private int expandNowState(){
		//扩展当前节点,1表示扩展成功,0表示找到目标节点，-1表示当前节点不可扩展
		
		int[] value = new int[]{255,255,255,255};//用于根据启发函数排序
		int size = nowState.expandSize();
		State[] states = nowState.expandState();
		
		for(int i=0;i<size;i++){
			if(!haveContained(states[i])){
				value[i] = HeuristicF1(states[i]);
				if(value[i]==0){
					nowState = states[i];
					return 0;
				}//如果找到目标节点
			    else {
					for(int k=0;k<size;k++){
						for(int j=k;j<size;j++){
							if(value[j]>value[k]){
								int temp = value[j];
								State tempState = states[j];
								value[j] = value[k];
								states[j] = states[k];
								value[k] = temp;
								states[k] = tempState;
							}
						}
					}//排序降序（越来越小）
					
					for(int m=0;m<size;m++){
						if(value[m]!=255){
							vecOpen.add(states[m]);
						}
					}//将扩展结果加入vecOpen
					return 1;
				}//扩展成功，则将扩展结果排序,将扩展结果加入标示未扩展的集合else
			}//if未扩展过
		}//for
		return -1;
	}
	private boolean searchPath(){
		//寻找路径
			
		while(!vecOpen.isEmpty()){
			int openSize = vecOpen.size();
			State st = (State)vecOpen.elementAt(openSize-1);
			if(nowState!=null){
			   nowState.moveTo(st);
			}
			
			nowState = st;
			vecOpen.remove(openSize-1);
			vecClose.add(nowState);
			
			if(expandNowState()==0){
				return true;
			}//如果已达到最终节点
		}//while
		return false;
	}
	
	private int climbExpandNowState(){
    //爬山算法的扩展当前节点,1表示扩展成功,0表示找到目标节点，-1表示当前节点不可扩展
		
		int[] value = new int[]{255,255,255,255};//用于根据启发函数排序
		int size = nowState.expandSize();
		State[] states = nowState.expandState();
		
		int min = 255;
		
		for(int i=0;i<size;i++){
			if(!haveContained(states[i])){
				value[i] = HeuristicF1(states[i]);
				if(value[i]==0){
					nowState = states[i];
					return 0;
				}//如果找到目标节点
				else {
					for(int k=0;k<size;k++){
						for(int j=k;j<size;j++){
							if(value[j]>value[k]){
								int temp = value[j];
								State tempState = states[j];
								value[j] = value[k];
								states[j] = states[k];
								value[k] = temp;
								states[k] = tempState;
							}
						}
					}//排序降序（越来越小）

					for(int m=0;m<size;m++){
						if(value[m]!=255){
							vecOpen.add(states[m]);
							return 1;
						}
					}//将扩展的最小的节点加入vecOpen
					
				}//扩展成功，找到扩展结果中最小的节点,将其加入标示未扩展的集合else
			}//if未扩展过
		}//for
		return -1;
	}
	
	private boolean climbSearchPath(){
		while(!vecOpen.isEmpty()){
			int openSize = vecOpen.size();
			State st = (State)vecOpen.elementAt(openSize-1);
			if(nowState!=null){
			     nowState.moveTo(st);
			}
			
			nowState = st;
			vecOpen.remove(openSize-1);
			vecClose.add(nowState);
			
			if(climbExpandNowState()==0){
				return true;
			}//如果已达到最终节点
		}
		return false;
	}

	public static void main(String[] args) {
		// *********************************使用启发式函数的A*算法解决八数码问题
		EightDigits ed = new EightDigits();
		ed.vecOpen.add(ed.startState);
		
		System.out.println("使用曼哈顿距离A*算法解决八数码问题：");
		if(ed.searchPath()){
		    for(int i=0;i<ed.vecClose.size();i++){
			    State s = (State)ed.vecClose.elementAt(i);
			    s.printState();
			    System.out.println("步骤"+(i+1));
		    }
		    ed.endState.printState();
		}//if
		else System.out.println("无解");
		//***********************************生成大量八数码问题用爬山法解决
		for(int i=0;i<1000;i++){
			EightDigitsRandomGenerator edr = new EightDigitsRandomGenerator();
			EightDigits eds = new EightDigits();
			State st = edr.EDRandom();
			eds.vecOpen.add(st);
			
			System.out.println("使用爬山算法解决八数码问题："+i);
			if(eds.climbSearchPath()){
		    	for(int j=0;j<eds.vecClose.size();j++){
			        State s = (State)eds.vecClose.elementAt(j);
			    	s.printState();
			    	System.out.println("步骤"+(j+1));
			    }
			}
			else System.out.println("无解");
		}
	}//main
}