八数码难题（启发式搜索）_、应用启发式搜索算法求解课本八数码问题: 设评价函数 f(n) = d(n) + p(n)(错位棋

八数码难题---启发式搜素

 

1.启发式搜索：

特点：重排OPEN表，选择最有希望的节点加以扩展

种类：有序搜索(A算法)、A*算法等

 

2.估价函数

用来估算节点处于最佳求解路径上的希望程度的函数

f(n) = g(n) + h(n)

 n——搜索图中的某个当前被扩展的节点；

f(n) ——从初始状态节点s, 经由节点n到达目标节点ng，估计的最小路径代价；

g(n) ——从s到n 的实际路径代价；

h(n)——从n到ng,估计的最小路径代价。

 八数码难题估价函数：f(n)=d(n)+w(n)                     

其中：d(n)为n的深度           w(n)为不在位的棋子数

 

3.有序搜索：

选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。

八数码难题使用全局择优搜索：

   选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。

在八数码难题中, 令估价函数

       f(n)=d(n)+p(n)

启发函数h(n)=p(n),p(n)为不在位的棋子与其目标位置的距离之和，则有p(n)≤h^*(n),满足A^*算法的限制条件。

w(n)——不在位的棋子数，不够贴切，错误选用节点加以扩展。

p(n)——更接近于h^*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋子在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。

p(n)比w(n)更接近于h^*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数）

数据结构的建立：由于open，close表常设计删除增加节点的操作，故使用单链表最好

open表存储生成的节点且未被处理的节点，处理过的节点取出放入close表

close表存储处理过的节点

status表存储所有生成的节点

采用全局择优的思想

 

java代码如下：

package 八数码难题;
 
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
 
 
 
 
 
public class Main {
	static int f[][]=new int[3][3];
	static int e[][]=new int[3][3];
	static int p=0;
	static int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
	static List<node>openlist=new LinkedList<node>();
	static List<node>closelist=new LinkedList<node>();
	static int d=0;
	static List<node>status=new LinkedList<node>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1;//初始状态
		String str2;//目标状态
		str1="2831647.5";//空格用.表示
		str2="1238.4765";
		for(int i=0;i<str1.length();i++){
			f[i/3][i-i/3*3]=str1.charAt(i)=='.'?0:str1.charAt(i)-'0';
			e[i/3][i-i/3*3]=str2.charAt(i)=='.'?0:str2.charAt(i)-'0';
		}
		node f1=new node(f,d,e);
		openlist.add(f1);
		status.add(f1);
		Search();//寻找最短路径
		toPrint();//输出状态空间
	}
	public static boolean check(int x,int y){
		if(x<0||x>=3||y<0||y>=3){
			return false;
		}
		return true;
	}
	public static boolean contains(List<node> list,int a[][]){
		int flag=0;
		int a1[][] = new int[3][3];
		
		for(int i=0;i<list.size();i++){
			flag=0;
			for(int j=0;j<3;j++){
				a1[j]=list.get(i).a[j].clone();
				for(int k=0;k<3;k++){
					if(a1[j][k]==a[j][k]){
						flag++;
					}
				}
			}
			if(flag==9) return false;
		}
		return true;
	}
	//输出状态空间
	public static void toPrint(){
		int a[][];
		System.out.println();
		System.out.println("========状态空间大小为："+status.size()+"-----");
		int k1=0,i=0;
		while(i<status.size()){
			a=status.get(i).a;
			System.out.println("---------------");
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					System.out.print(a[j][k]+" ");
				}
				System.out.println();
			}
			i++;
		}
	}
	public static void Search(){
		hnode ehn=new hnode(e);
		while(!openlist.isEmpty()){
			int at[][]=new int[3][3];
			int min=0;
			for(int i=0;i<openlist.size();i++){
				if(openlist.get(i).f<openlist.get(min).f){
					min=i;
				}
			}
			node n=null;
			n=openlist.remove(min);
			closelist.add(n);
			
			
			for(int i=0;i<3;i++){
				at[i]=n.a[i].clone();
			}
			
			int x = 0,y = 0;
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(at[i][j]==p){
						x=i;y=j;//记录空格在棋盘中的位置(原）
						break;
					}
				}
			}
			for(int i=0;i<4;i++){
				int nx,ny,t;
				nx=x+dir[i][0];//空格移动的位置（现）
				ny=y+dir[i][1];
				if(check(nx,ny)){
					t=at[nx][ny];
					at[nx][ny]=at[x][y];
					at[x][y]=t;
					d=n.h+1;
					hnode thn=new hnode(at);
					node tn=new node(at,d,e);
					if(thn.equals(ehn)){
						//找到最短路径
						status.add(tn);
						closelist.add(tn);
						toOutput();
						return;
					}
					
					if(contains(openlist,at)&&contains(closelist,at)){
						openlist.add(tn);
						status.add(tn);
					}
					t=at[nx][ny];
					at[nx][ny]=at[x][y];
					at[x][y]=t;
				}
			}
		}
		return;
	}
	public static void toOutput(){
		System.out.println("====移动路径如下====");
		System.out.println("所需步数为:"+d);
		for(int i=0;i<closelist.size();i++){
			int a[][]=closelist.get(i).a;
			System.out.println("----------------------");
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					System.out.print(a[j][k]+" ");
				}
				System.out.println();
			}
		}
	}
 
}
 
 
 
class hnode{
	//hash用于hashSet
	int hash;
	public hnode(){
		
	}
	public hnode(int a[][]){
		int hc=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				hc*=10;
				hc+=a[i][j];
			}
		}
		this.hash=hc;
	}
	public boolean equals(Object object){
		hnode thn=(hnode)object;
		return thn.hash==hash;
	}
	@Override
	public int hashCode(){
		return hash;
	}
	
	
}
class node{
	int a[][];//九宫格的状态
	int h;//深度
	int f;//从初始状态节点s, 经由节点n到达目标节点ng，估计的最小路径代价
	int p;//不在位的棋子与其目标位置的距离之和
	public node(int [][]a,int h,int [][]e){
		this.a=new int[3][];
		for(int i=0;i<3;i++){
			this.a[i]=a[i].clone();
		}
		this.h=h;
		this.p=work(e);
		this.f=this.h+this.p;
	}
	public int work(int e[][]){
		int ants=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(a[i][j]!=e[i][j]&&a[i][j]!=0){
					int r=0,c = 0,flag=0;
					for(int k=0;k<3;k++){
						for(int k1=0;k1<3;k1++){
							if(a[i][j]==e[k][k1]){
								r=k;
								c=k1;
								ants+=Math.abs(r-i);
								ants+=Math.abs(c-j);
								flag=1;
								break;
							}
						}
						if(flag==1) break;
					}
					
				}
			}
		}
		return ants;
	}
}