IDC资讯中心
//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类可以胜任这项工作，不过作业都交了，我也懒得改了！
