用java实现人工智能中的A*算法求8数码问题
//8数码类
class Eight{
int e[][] = {{2,8,3},{1,6,4},{7,0,5}}; //默认的起始状态
int faX ,faY; //保存父状态中0的位置
int f; //估价函数值
Eight former ;
public Eight(){
faX = -1;
faY=-1;
f=-1;
former = null;
}
public Eight(Eight other){
for(int i = 0; i<3; i++)
for(int j=0 ;j<3; j++){
e[i][j] = other.e[i][j];
}
faX = other.faX;
faY = other.faY;
f = other.f;
former = other.former;
}
public void print()
{
for(int i1 = 0;i1<3;i1++)
for(int j1=0;j1<3;j1++){
System.out.print(e[i1][j1]);
if(j1==2)
System.out.println();
}
System.out.println();
}
public void listAll( Eight e ){
while( e.former != null ){
e.former.print();
e = new Eight(e.former);
}
return ;
}
}
class Queue extends Object{ //队列类
private int size = 0;
Eight qe[] = new Eight[20];
public void print(){
for(int i=0;i<size;i++)
qe[i].print();
}
public void addElement(Eight e){
qe[size] = e;
size++;
}
public boolean contains(Eight e){
if( size == 0 )
return false;
else{
for(int i=0;i<size;i++){
if(qe[i].equals(e))
return true;
}
}
return false;
}
public boolean isEmpty(){
if (size == 0) {
return true;
}
else return false;
}
public Eight elementAt(int index){
return qe[index];
}
public void setElementAt( Eight e,int index ){
qe[index] = e;
}
public int size(){
return size;
}
public int indexOf (Eight e) {
for (int i = 0; i < size; i++){
if (qe[i].equals( e ))
return i;
}
return -1;
}
public void removeFirst( ){
for(int i=0;i<size;i++){
qe[i] = qe[i+1];
}
size--;
}
public void remove( Eight e ){
for( int i = 0; i < size; i++ ){
if( qe[i].equals( e ))
qe[i] = null;
}
size--;
}
public void removeAllElements(){
for (int i = 0; i < size; i++){
qe[i] = null;
}
size = 0;
}
}
//算法实现类
public class Asearch{
static int dest[][] = {{1,2,3},{8,0,4},{7,6,5}};
static void Swap(Eight ee,int i,int j,int m,int n){
int temp;
temp = ee.e[i][j];
ee.e[i][j] = ee.e[m][n];
ee.e[m][n] = temp;
}
static int compare(Eight a){
int h =0,i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++){
if(a.e[i][j]!=dest[i][j])
h++;
}
return h;
}
//生成子状态
static Queue born(Eight e){
int m=1,n=1,i=0,j=0;
boolean flag = true;
Queue sons = new Queue();
for(i=0;i<3&&flag;i++)
for(j=0;j<3&&flag;j++){
if(e.e[i][j]==0){
flag=false;
break;
}
}
i--;
if(i-1>=0){
m=i-1;
if(m!=e.faX){
Swap(e,m,j,i,j);
//e.print();
Eight son1 = new Eight(e);
son1.faX = i;
son1.faY = j;
son1.former = e;
sons.addElement(son1);
Swap(e,i,j,m,j);
}
}
if(i+1<3){
m=i+1;
if(m!=e.faX){
Swap(e,m,j,i,j);
//e.print();
Eight son2 = new Eight(e);
son2.faX = i;
son2.faY = j;
son2.former = e;
sons.addElement(son2);
Swap(e,i,j,m,j);
}
}
if(j-1>=0){
n=j-1;
if(n!=e.faY){
Swap(e,i,n,i,j);
//e.print();
Eight son3 = new Eight(e);
son3.faX = i;
son3.faY = j;
son3.former = e;
sons.addElement(son3);
Swap(e,i,j,i,n);
}
}
if(j+1<3){
n=j+1;
if(n!=e.faY){
Swap(e,i,n,i,j);
//e.print();
Eight son4 = new Eight(e);
son4.faX = i;
son4.faY = j;
son4.former = e;
sons.addElement(son4);
Swap(e,i,j,i,n);
}
}
return sons;
}
public static void main(String[] args){
int depth=0; //深度
Eight n = new Eight() ;
Eight temp1 = new Eight() , temp2 = new Eight() ;
//open表
Queue open = new Queue();
//closed表
Queue closed = new Queue();
//保存子状态的表
Queue son = new Queue();
open.addElement(n);
while(!open.isEmpty()){
n= open.elementAt(0);
open.removeFirst( );
if(compare(n)==0){
n.listAll(n);
System.out.println("Success!");
return;
}
son = born(n);
depth++;
int count = son.size();
if(count==0)
continue;
else for(int t=0;t<count;t++){
temp1 = son.elementAt(t);
if(!open.contains(temp1)&&!closed.contains(temp1)){
temp1.f = depth + compare(temp1);
open.addElement(temp1);
}
else if(open.contains(temp1)){
temp1.f = depth + compare(temp1);
int pos = open.indexOf(son.elementAt(t));
temp2 = open.elementAt(pos);
if(temp1.f<temp2.f){
open.setElementAt(temp1,pos);
}
}
else if(closed.contains(temp1)){
temp1.f = depth + compare(temp1);
int pos = closed.indexOf(temp1);
temp2 = closed.elementAt(pos);
if( temp1.f<temp2.f ){
closed.remove(son.elementAt(t));
open.addElement(temp1);
}
}
}//end for
closed.addElement(n);
for(int i=open.size()-1;i>0;i--)
for(int j=0;j<i;j++){
temp1 = (Eight)open.elementAt(j);
temp2 = (Eight)open.elementAt(j+1);
if(temp1.f>temp2.f){
Eight tq=new Eight();
tq = open.elementAt(j);
open.setElementAt(open.elementAt(j+1),j);
open.setElementAt(tq,j+1);
}
}
}//end while
System.out.println("Fail!");
return;
}//end main
}
这个程序是实现人工智能中的A*算法，照着书上的算法做的。Queue类是自己写的一个队列类，用来实现open表和closed表。原来用Vector做的，但后来发现Vector中保存的只是引用，生成子状态后表中的状态也跟着变了，只好自己实现一个队列类。现在知道还有个LinkedList类可以胜任这项工作，不过作业都交了，我也懒得改了！
