aalgorithm.cpp

AI作业合集

// 8_num.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include <time.h>
#include <stdio.h>
#include <dos.h>
#include <conio.h>

static int target[9]={1,2,3,4,5,6,7,8,0};
//定义一个类
class eightNum
{
private:
	int num[9];
	int notInNum;
	int deapth;
	int evaFunction;

public:
	eightNum* parent;
	eightNum* leaf_next;
	eightNum* leaf_pre;

	eightNum(int init_num[9]);
	eightNum(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)
	{
		num[0]=num1;
		num[1]=num2;
		num[2]=num3;
		num[3]=num4;
		num[4]=num5;
		num[5]=num6;
		num[6]=num7;
		num[7]=num8;
		num[8]=num9;
	}
	eightNum(void)
	{
		for (int i=0;i<9;i++)
			num[i]=i;
	}

	void cul_para(void);

	void get_numbers_to(int other_num[9]);
	int get_nipn(void)
	{return notInNum;}
	int get_deapth(void)
	{return deapth;}
	int get_evafun(void)
	{return evaFunction;}
	void set_num(int other_num[9]);

	void show(void);
	
	eightNum& operator=(eightNum&);
	eightNum& operator=(int other_num[9]);
	int operator==(eightNum&);
	int operator==(int other_num[9]);
};

void eightNum::cul_para(void)
{
	int i;
	int temp_nipn=0;
	for (i=0;i<9;i++)
		if (num[i]!=target[i])
			temp_nipn++;
	notInNum=temp_nipn;
	if (this->parent==NULL)
		deapth=0;
	else
		deapth=this->parent->deapth+1;
	evaFunction=notInNum+deapth;
}

eightNum::eightNum(int init_num[9])
{
	for (int i=0;i<9;i++)
		num[i]=init_num[i];
}

void eightNum::show()
{
	cout<<num[0];
	cout<<" ";
	cout<<num[1];
	cout<<" ";
	cout<<num[2];
	cout<<"\n";
	cout<<num[3];
	cout<<" ";
	cout<<num[4];
	cout<<" ";
	cout<<num[5];
	cout<<"\n";
	cout<<num[6];
	cout<<" ";
	cout<<num[7];
	cout<<" ";
	cout<<num[8];
	cout<<"\n";
}

void eightNum::get_numbers_to(int other_num[9])
{
	for (int i=0;i<9;i++)
		other_num[i]=num[i];
}

void eightNum::set_num(int other_num[9])
{
	for (int i=0;i<9;i++)
		num[i]=other_num[i];
}

eightNum& eightNum::operator=(eightNum& another_8num)
{
	for (int i=0;i<9;i++)
		num[i]=another_8num.num[i];
	notInNum=another_8num.notInNum;
	deapth=another_8num.deapth+1;
	evaFunction=notInNum+deapth;
	return *this;
}

eightNum& eightNum::operator=(int other_num[9])
{
	for (int i=0;i<9;i++)
		num[i]=other_num[i];
	return *this;
}

int eightNum::operator==(eightNum& another_8num)
{
	int match=1;
	for (int i=0;i<9;i++)
		if(num[i]!=another_8num.num[i])
		{
			match=0;
			break;
		}
	if (match==0)
		return 0;
	else 
		return 1;
}

int eightNum::operator==(int other_num[9])
{
	int match=1;
	for (int i=0;i<9;i++)
		if(num[i]!=other_num[i])
		{
			match=0;
			break;
		}
	if (match==0)
		return 0;
	else 
		return 1;
}

//class definition over
//*************************


//空格向上移
int move_up(int num[9])
{
	for (int i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i<3)
		return 0;
	else
	{
		num[i]=num[i-3];
		num[i-3]=0;
		return 1;
	}
}

//空格向下移
int move_down(int num[9])
{
	for (int i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i>5)
		return 0;
	else
	{
		num[i]=num[i+3];
		num[i+3]=0;
		return 1;
	}
}
//空格向左移
int move_left(int num[9])
{
	for (int i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i==0||i==3||i==6)
		return 0;
	else
	{
		num[i]=num[i-1];
		num[i-1]=0;
		return 1;
	}
}
//空格向右移
int move_right(int num[9])
{
	for (int i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i==2||i==5||i==8)
		return 0;
	else
	{
		num[i]=num[i+1];
		num[i+1]=0;
		return 1;
	}
}

//判断可否解出
int icansolve(int num[9],int target[9])
{
	int i,j;
	int count_num,count_target;
	for (i=0;i<9;i++)
		for (j=0;j<i;j++)
		{
			if(num[j]<num[i]&&num[j]!=0)
				count_num++;
			if(target[j]<target[i]&&target[j]!=0)
				count_target++;
		}
	count_num=count_num-2*(count_num/2);
	count_target=count_target-2*(count_target/2);
	if ((count_num==1&&count_target==1)||(count_num==0&&count_target==0))
		return 1;
	else
		return 0;
}

//判断有无重复
int existed(int num[9],eightNum *where)
{
	eightNum *p;
	for(p=where;p!=NULL;p=p->parent)
		if(*p==num)
			return 1;
	return 0;
}

//寻找估价函数最小的叶子节点
eightNum* find_OK_leaf(eightNum* start)
{
	eightNum *p,*OK;
	p=OK=start;
	int min=start->get_evafun();
	for(p=start;p!=NULL;p=p->leaf_next)
		if(min>p->get_evafun())
		{
			OK=p;
			min=p->get_evafun();
		}
	return OK;
}

//主函数开始
int main(void)
{
	double  time;   
	clock_t Start,Finish;
	int memeryUsed=0,step=0;
	int num[9];
	int flag=0;//是否输入错误标志，1表示输入错误
	int bingo=0;//是否查找成功标志，1表示成功
	int i,j;
	cout<<"Please Input The Number(0 For The Blank):\n";
	for (i=0;i<9;i++)
	{
		flag=0;
		cin>>num[i];
		for(j=0;j<i;j++)
			if(num[i]==num[j])
				flag=1;
		if (num[i]<0||num[i]>8||flag==1)
		{
			i--;
			cout<<"Illegle number!\tReinput!\n";
		}
	}
	cout<<"Do you want to modify the target(Y/N)?";
	char input;
	cin>>input;
	if (input=='y'||input=='Y')
	{
		cout<<"\nPlease input the new target:\n";
		for (i=0;i<9;i++)
		{
			flag=0;
			cin>>target[i];
			for(j=0;j<i;j++)
				if(target[i]==target[j])
					flag=1;
			if (target[i]<0||target[i]>8||flag==1)
			{
				i--;
				cout<<"Illegle number!\tReinput!\n";
			}
		}
	}

	eightNum S(num),Target(target);
	S.parent=S.leaf_next=S.leaf_pre=NULL;
	S.cul_para();
	memeryUsed++;
	cout<<"Now the initial numbers are:\n";
	S.show();
	cout<<"And the Target is:\n";
	Target.show();
	
	if(!icansolve(num,target))
	{
		cout<<"No one can solve it!\n";
		cin>>i;
		return 1;
	}

	Start=clock( );//获取时间

	eightNum *OK_leaf=&S,*leaf_start=&S,*new_8num,*p;
	while(OK_leaf!=NULL&&bingo!=1)
	{
		OK_leaf=find_OK_leaf(leaf_start);
		if(*OK_leaf==Target)
		{
			bingo=1;
			break;
		}
		
		p=OK_leaf->leaf_pre;
		OK_leaf->get_numbers_to(num);
		if(move_up(num)&&!existed(num,OK_leaf))
		{
			new_8num=new eightNum;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			memeryUsed++;
		}
		OK_leaf->get_numbers_to(num);
		if(move_down(num)&&!existed(num,OK_leaf))
		{
			new_8num=new eightNum;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			memeryUsed++;
		}
		OK_leaf->get_numbers_to(num);
		if(move_left(num)&&!existed(num,OK_leaf))
		{
			new_8num=new eightNum;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			memeryUsed++;
		}
		OK_leaf->get_numbers_to(num);
		if(move_right(num)&&!existed(num,OK_leaf))
		{
			new_8num=new eightNum;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			memeryUsed++;
		}
		p->leaf_next=OK_leaf->leaf_next;
		if(OK_leaf->leaf_next!=NULL)
			OK_leaf->leaf_next->leaf_pre=p;
		OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL;
	}

	Finish=clock( ); 

	if(bingo==1)
	{
		time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC;
		eightNum *p;
		for (p=OK_leaf->parent;p!=NULL;p=p->parent)
		{
			cout<<"  ^\n";
			p->show();
			step++;
		}

		cout<<"Time cost:";
		cout<<time;
		cout<<"ms\n";
		cout<<"Memery cost:";
		cout<<memeryUsed;
		cout<<"Blocks\n";
		cout<<"Totaly covered steps:";
		cout<<step;
		cout<<"\n";
	}
	else
		cout<<"Fail to find!";

	cin>>i;
	return 0;
}