houxuan.cpp

VC语言实现的候选消除算法

#include "iostream"
#include "list"

using namespace std;

const int n=4;
const int m=6;

class Example
{
public:
	bool type;
	char Att[m];
};

class G_border
{
public:
	char rule[m];
};



typedef list<G_border> G_LIST; //存放一般边界的链表
G_LIST glis;

//判断某一正样例和一般边界不一致
int UnConsitent_P_G(Example a,char *b)
{
    for(int i=0;i<m;i++)
	{
		if(b[i]!='?')
		{
			if(a.Att[i]!=b[i])
			{
				return 1;
				break;
			}
		}
	}
	return 0;
		
}

//判断某一反样例与一般边界一致
int UnConsitent_N_G(Example a,char *b)
{
	int num=0;
    for(int i=0;i<m;i++)
	{
		if(b[i]!='?')
		{
			if(a.Att[i]==b[i])
				num+=1;
		}
	}
	if(num==0||num==m)
		return 1;
	else 
		return 0;
	
}
//判断某一正样例和特殊边界不一致
int UnConsitent_S(Example a,char *b)
{
    for(int i=0;i<m;i++)
	{
		if(a.Att[i]!=b[i]||b[i]=='#')
		{
			return 1;
			break;
		}
		
	}
	return 0;
}

//对某一正样例，特殊边界进行修改
void replace(Example a,char *b)
{
     for(int i=0;i<m;i++)
	 {
		 if(b[i]=='#')
			 b[i]=a.Att[i];
		 else
		 {
			 if(a.Att[i]!=b[i])
				 b[i]='?';
		 }
	 }
}

//对某一反样例，根据特殊边界，产生更特殊的一般边界
G_LIST deal_with_n(Example a,char *b)
{
	G_border c;
	G_LIST s;
    for(int t=0;t<m;t++)
	{
		for(int k=0;k<m;k++)
			c.rule[k]='?';
		
		if(b[t]!='?')
		{
			if(a.Att[t]!=b[t])
			{
				c.rule[t]=b[t];
				s.push_back(c);
			}
		}
	}
	
	return s;
}

void main()
{

//初始化训练样例
	Example ex[n];
	G_border G0;
    char S_border[m];
    G_LIST S_Last;
	
	for(int i=0;i<n;i++)
	{
		cout<<"请依次输入第"<<i<<"个样例的属性值和类型值:";
		for(int j=0;j<m;j++)
			cin>>ex[i].Att[j];
		cin>>ex[i].type;
	}

//检测数据是否正确输入进去
	/*for(i=0;i<n;i++)
	{
		cout<<"第"<<i<<"个样例为：";
			for(int j=0;j<m;j++)
				cout<<ex[i].Att[j]<<" ";
			cout<<endl;
	}*/
	
	for(int t=0;t<m;t++)
	{
		G0.rule[t]='?';//一般边界初始化为<?,?,?,?,?,?>
		S_border[t]='#';//特殊边界初始化<#,#,#,#,#,#>，其中#表示空集
	}
    glis.push_back(G0);
	for(i=0;i<n;i++)
	{
		if(ex[i].type==1)
		{
			for(G_LIST::iterator iter=glis.begin();iter!=glis.end();++iter)
			{
				if(UnConsitent_P_G(ex[i],iter->rule))
				{
					glis.erase(iter);
					break;
				}
			}
			
			if(UnConsitent_S(ex[i],S_border))
			{
				replace(ex[i],S_border);
			}
//显示正样例与一般边界比较后的一般边界
			cout<<"正样例"<<i<<"与一般边界比较后的一般边界为："<<endl;
			for(G_LIST::iterator it=glis.begin();it!=glis.end();++it)
			{
				cout<<"<";
				for(int p=0;p<m;p++)
					cout<<it->rule[p]<<" ";
				cout<<">"<<endl;
			}
//显示正样例与特殊边界比较后的特殊边界
			cout<<"正样例"<<i<<"与特殊边界比较后的特殊边界为："<<endl;
			cout<<"<";
			for(int s=0;s<m;s++)
				cout<<S_border[s]<<" ";
			cout<<">"<<endl;
		}

		else
			if(ex[i].type==0)
			{
				G_LIST temp;
				if(i==0)
				{
                     for(int e=0;e<m;e++)
					 {
						 for(int v=1;v<n;v++)
						 {
							 if(ex[i+v].type==1)
							 {
								 S_border[e]=ex[i+v].Att[e];
								 break;
							 }
						 }
					 }
					 for(G_LIST::iterator iter=glis.begin();iter!=glis.end();++iter)
					 {
						 if(UnConsitent_N_G(ex[i],iter->rule))
						 {
							 glis.erase(iter);
							 break;
						 }
					 }
					 
					 temp=deal_with_n(ex[i],S_border);
					 glis.insert(glis.begin(),temp.begin(),temp.end());
					 
					 //显示反样例与一般边界比较后的一般边界
					 cout<<"反样例"<<i<<"与一般边界比较后的一般边界为："<<endl;
					 for(G_LIST::iterator it=glis.begin();it!=glis.end();++it)
					 {
						 cout<<"<";
						 for(int p=0;p<m;p++)
							 cout<<it->rule[p]<<" ";
						 cout<<">"<<endl;
					 }
				}
				
				else
				{
					for(G_LIST::iterator iter=glis.begin();iter!=glis.end();++iter)
					{
						if(UnConsitent_N_G(ex[i],iter->rule))
						{
							glis.erase(iter);
							break;
						}
					}
					
					temp=deal_with_n(ex[i],S_border);
					glis.insert(glis.begin(),temp.begin(),temp.end());
					
					//显示反样例与一般边界比较后的一般边界
					cout<<"反样例"<<i<<"与一般边界比较后的一般边界为："<<endl;
					for(G_LIST::iterator it=glis.begin();it!=glis.end();++it)
					{
						cout<<"<";
						for(int p=0;p<m;p++)
							cout<<it->rule[p]<<" ";
						cout<<">"<<endl;
					}
				}
			}
	}//end for(i=0;i<n;i++)

//显示最终的变型空间
	
	cout<<"最终的变型空间如下所示："<<endl;
	cout<<"特殊边界为："<<"<";
	
    for(int r=0;r<m;r++)
		cout<<S_border[r]<<" ";
	cout<<">"<<endl;

	
    for(int d=0;d<m;d++)
	{
		G_border tem;
		for(int h=0;h<m;h++)
			tem.rule[h]=S_border[h];
		
		if(S_border[d]!='?')
		{
			tem.rule[d]='?';
			S_Last.push_back(tem);
		}
		else
			continue;
	}

	for(G_LIST::iterator last=S_Last.begin();last!=S_Last.end();++last)
	{
		cout<<"<";
		for(int b=0;b<m;b++)
			cout<<last->rule[b]<<" ";
		cout<<">";
	}
	cout<<endl;

	cout<<"一般边界为：";
    for(G_LIST::iterator it=glis.begin();it!=glis.end();++it)
	{
		cout<<"<";
		for(int q=0;q<m;q++)
			cout<<it->rule[q]<<" ";
		cout<<">";
	}
	cout<<endl;
}//end main()