searchwidth.c

人工智能里的图搜索技术

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<fstream>
#define Column  3
#define Line    3
#define MAX     50
using namespace std;
typedef   struct no
{
	   int Number[Line][Column];
           struct no *father;
	   struct no  * next;
	   int Operator;
}Node;
Node *HeadOpen,*HeadClose,sg;
void WidthSearch(void);
void main()
  {   
	WidthSearch();
  }   
void WidthSearch(void)
{   Node* GetSource_Dest(void);
    Node* MoveToClose(void);
    int JudgeSameNode(Node,Node*);
    void  DisplayAnswer(void);
    void CreateSubNode(void);
	Node *father;
	int n,i=0;
	HeadOpen=new Node;
	HeadClose=new Node;
   	HeadClose->father=HeadClose;
       	HeadClose->next=NULL;
    HeadOpen->father=HeadOpen;
	HeadOpen->next=GetSource_Dest();
	if(HeadOpen->next==NULL)
		return;
	HeadOpen->Operator=1;
	HeadClose->Operator=0;
    while(1)
	{
	     n=HeadClose->Operator;
		 if(n>2000)
		 {
			 cout<<"问题无解";
            
			 return;
                 }
         father=MoveToClose();
	  if(JudgeSameNode(sg,father))
		 {
			 cout<<endl;
			 DisplayAnswer();
			 return;
		 }
		 CreateSubNode();
         }
}
Node* GetSource_Dest(void)
{  
  int ReadNumber(Node*);
  Node *data;
  data=new Node;
  data->father=NULL;
  data->next=NULL;
  ReadNumber(data);
   return  data;
}
int ReadNumber(Node* source)
{ char file_name[MAX];
  int i,j;
  cout<<"input the file name\n";
  cin>>file_name;
  ifstream fp(file_name);
  for(i=0;i<Line;i++)
	for(j=0;j<Column;j++)
	  fp>>source->Number[i][j];
  for(i=0;i<Line;i++)
	for(j=0;j<Column;j++)
      fp>>sg.Number[i][j];
	return 1;
}
void CreateSubNode(void)
{
int AddNode(Node ,Node *,Node **,int );
 int i,row,col,n=0;
 Node *father,*x,q;
 father=HeadClose->father;
 x=HeadOpen->father;
  for(i=0;i<Line;i++)
   for(int j=0;j<Column;j++)
		 if(father->Number[i][j]==0)
		 {
			 row=i;col=j;
		 }
	if(col>0)
	 {
		 q=*father;
		 q.Number[row][col]=q.Number[row][col-1];
		 q.Number[row][col-1]=0;
	         n+=AddNode(q,father,&x,1);
	 }
	 if(col<Column-1)
	 {
                 q=*father;
		 q.Number[row][col]=q.Number[row][col+1];
		 q.Number[row][col+1]=0;
	         n+=AddNode(q,father,&x,1);
	 }
	if(row>0)
	 {
		 q=*father;
		 q.Number[row][col]=q.Number[row-1][col];
		 q.Number[row-1][col]=0;
	         n+=AddNode(q,father,&x,1);
	 }
	if(row<Line-1)
	 {
		 q=*father;
		 q.Number[row][col]=q.Number[row+1][col];
		 q.Number[row+1][col]=0;
	         n+=AddNode(q,father,&x,1);
	 } 
	HeadOpen->father=x;
	HeadOpen->Operator+=n;
}
Node* MoveToClose(void)
{
  Node* Temp;
  Temp=HeadOpen->next;
  HeadOpen->next=Temp->next;
  Temp->next=NULL;
  HeadOpen->Operator--;
  HeadClose->father->next=Temp;
  HeadClose->Operator++;
  HeadClose->father=Temp;
  if(HeadClose->Operator==1)
	  HeadClose->next->father=NULL;
   return Temp;
}
int JudgeSameNode(Node in_f,Node* out_s)
{
     int i;
     for(i=0;i<Line;i++)
	  for(int j=0;j<Column;j++)
		  if(in_f.Number[i][j]!=out_s->Number[i][j])
                return 0;
        return 1;
}
void  DisplayAnswer(void)
{
  ofstream fp("c:\\file_out.txt");
  typedef struct nodelink
 {
		Node *head;
		struct nodelink *next;
  }nodDelete;	
Node *temper,*Prev_nod;
nodDelete *headNode,*nextnode;
headNode=new nodDelete;
temper=HeadClose->father;
Prev_nod=temper->father;    
headNode->head=temper;    
headNode->next=NULL;   
  while(Prev_nod)
  {
  nextnode=new nodDelete;  
  nextnode->head=Prev_nod;
  nextnode->next=headNode;
  headNode=nextnode;
  Prev_nod=Prev_nod->father;
  }
  while(headNode)
  {
   temper=headNode->head;
   for(int i=0;i<Line;i++)
   {  for(int j=0;j<Column;j++)
           {
          fp<<temper->Number[i][j]<<" ";
            //cout<<temp->Number[i][j];
            }
          fp<<"\n";
   }
   fp<<"\n";
   nextnode=headNode;
   headNode=headNode->next;
   delete nextnode;
  }
  
}
int CopyData(Node *q,Node *p)
{
        int i,j;
	for(i=0;i<Line;i++)
		for(j=0;j<Column;j++)
			p->Number[i][j]=q->Number[i][j];
         return 1;
}
int CheckDataExist(Node* q)
{
    Node *Check;
	Check=HeadOpen->next;
	while(Check)
	{
	if(JudgeSameNode(*q,Check))
			return 0;
		Check=Check->next;
	}
        Check=HeadClose->next;
	while(Check)
	{ if(JudgeSameNode(*q,Check))
			return 0;
		Check=Check->next;
	}
	return 1;
}
int AddNode(Node q,Node *father,Node **x,int OPt)
{
    Node *Add;
	int n=0;
	if(CheckDataExist(&q))
	{
	   Add=new Node;
	   CopyData(&q,Add);
	   (*x)->next=Add;
	   *x=Add;
	   Add->father=father;
	   Add->next=NULL;
	   Add->Operator=OPt;
	   n=1;
	}
	return n;
}