 |
|
|
 首页 |
名片设计 CorelDRAW Illustrator AuotoCAD Painter 其他软件 Photoshop Fireworks Flash |
|
//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类可以胜任这项工作，不过作业都交了，我也懒得改了！ 返回类别: 教程 上一教程: java版的SHA-1 下一教程: 100行Java代码构建一个线程池 您可以阅读与"用java实现人工智能中的A*算法求8数码问题"相关的教程: · Javamail中的常见中文乱码问题与解决办法(综合) · 漫谈Java中的中文问题 · Java 关于中文乱码问题的解决方案与经验 （2） · Java中的Big/Little问题 · 漫谈Java中的中文问题 |
  |
| 快精灵印艺坊 版权所有 |
首页 会员中心在线印刷在线编辑付款方式索取样品设计指南连锁门店
|
||
