全局择优算法.cpp

ai 算法

#include<iostream.h>
class Item;
class StackDep{
public:
	Item*head;
	Item*top;
	StackDep();
	void push(Item*p);
	Item*pop();
	void printStackDep();
	int empt();
	Item*getTop();
};

class Item{
public:
	int state;
	int x;
	int y;

	int node[3][3];
	Item();
	Item(int k[3][3]);
	Item*next;
	Item*parent;
	int level;
	int compare(Item*p);
	void print();
	void input();
	void search(StackDep* k);
	Item*moveup();
	Item*movedown();
	Item*moveleft();
	Item*moveright();
	int already(StackDep*k);
	int parentAlready(StackDep*k);
	int h(Item owa);
};

int Item::h(Item owa){
	int num=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(owa.node[i][j]!=node[i][j]){
				num++;
			}
		}
	}
	return num;
}

int Item::already(StackDep*k){
	Item*p=k->head->next;
	while(p&&p->next){
		if(compare(p)){
			return 1;
		}
		p=p->next;
	}
	return 0;
}

int Item::parentAlready(StackDep*k){
	Item*p=parent;
	while(p&&p!=k->head){
		if(compare(p)){
			return 1;
		}
		p=p->parent;
	}
	return 0;
}

Item* Item::moveup(){
    int k=x-1;
	int m=y;
	if(!(k>=0&&k<=2&&m>=0&&m<=2)){
		return NULL;
	}else{
		Item*temp=new Item(node);
		temp->node[x][y]=temp->node[k][m];
		temp->node[k][m]=0;
		temp->x=k;
		temp->y=m;
		return temp;
	}
}

Item* Item::moveright(){
    int k=x;
	int m=y+1;
	if(!(k>=0&&k<=2&&m>=0&&m<=2)){
		return NULL;
	}else{
		Item*temp=new Item(node);
		temp->node[x][y]=temp->node[k][m];
		temp->node[k][m]=0;
		temp->x=k;
		temp->y=m;
		return temp;
	}
}

Item* Item::movedown(){
    int k=x+1;
	int m=y;
	if(!(k>=0&&k<=2&&m>=0&&m<=2)){
		return NULL;
	}else{
		Item*temp=new Item(node);
		temp->node[x][y]=temp->node[k][m];
		temp->node[k][m]=0;
		temp->x=k;
		temp->y=m;
		return temp;
	}
}

Item* Item::moveleft(){
    int k=x;
	int m=y-1;
	if(!(k>=0&&k<=2&&m>=0&&m<=2)){
		return NULL;
	}else{
		Item*temp=new Item(node);
		temp->node[x][y]=temp->node[k][m];
		temp->node[k][m]=0;
		temp->x=k;
		temp->y=m;
		return temp;
	}
}


Item::Item(){
	state=0;
}
Item::Item(int k[3][3]){
	state=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			node[i][j]=k[i][j];
			if(k[i][j]==0){
				x=i;
				y=j;
			}
		}
	}
}
int Item::compare(Item*p){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(node[i][j]!=p->node[i][j]){
				return 0;
			}
		}
	}
	return 1;
}

void Item::print(){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cout<<node[i][j]<<" ";
		}
		cout<<endl;
	}
//	int tt;
//	cin>>tt;
	cout<<endl;
}
void Item::input(){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cout<<"Input node["<<i<<"]["<<j<<"]:"<<endl;
			cin>>node[i][j];
			if(node[i][j]==0){
				x=i;
				y=j;
			}
		}
	}
}
/*
class StackDep{
public:
	Item*head;
	Item*top;
	StackDep();
	void push(Item*p);
	Item* pop();
	void printStackDep();
	int empt();
	Item*getTop();
};
*/
Item*StackDep::getTop(){
	return top;
}

StackDep::StackDep(){
	head=new Item();
	top=head;
}
void StackDep::push(Item*p){
	top->next=p;
	p->parent=top;
	top=p;
	p->next=NULL;
}
Item* StackDep::pop(){
	Item*temp=top;
	top=top->parent;
	top->next=NULL;
	return temp;
}
int StackDep::empt(){
	if(top==head){
		return 1;
	}
	else{
		return 0;
	}
}
void StackDep::printStackDep(){
	Item*p=head->next;
	int i=0;
	while(p){
		cout<<i++<<endl;
		p->print();
		cout<<endl;
		p=p->next;
	}
}

void main(){
     Item hajime;
     Item owari;
     cout<<"Please input the starting state:"<<endl;
     hajime.input();
     cout<<"then input the final state:"<<endl;
     owari.input();
     
     StackDep*father=new StackDep();
     father->push(&hajime);
     int flag=0;
     Item*temp;
	 Item*present;//
	 present=&hajime;
	 Item*made;//
	 made=&hajime;
	 int tag=0;
	 while(!father->empt()){
		 Item*p=father->head;
		 int min=9999;
		 Item*record;
		 while(p){
			 p=p->next;
			if(p->compare(&owari)){
				tag=1;
				break;
			}
			 if(min>p->h(owari)+p->level&&p->state==0){
				 min=p->h(owari)+p->level;
				 record=p;
			 }
			 p->state=1;

			temp=p->moveright();
			if(temp){
				father->push(temp);
				temp->parent=p;
				temp->level=p->level+1;
			}
			temp=p->movedown();
			if(temp){
				father->push(temp);
				temp->parent=p;
				temp->level=p->level+1;
			}
			temp=p->moveleft();
			if(temp){
				father->push(temp);
				temp->parent=p;
				temp->level=p->level+1;
			}
			temp=p->moveup();
			if(temp){
				father->push(temp);
				temp->parent=p;
				temp->level=p->level+1;
			}
		 }

		 if(tag){
			
			Item*kaka=p;
			Item*dada;
			while(kaka&&kaka!=father->head){
				dada=kaka;
				kaka=kaka->parent;
				kaka->next=dada;
			}
			p->next=NULL;
			father->printStackDep();
	       break;
		 }	 
	 
	 }
}