3sat.c

用模拟退火方法解决3SAT问题

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define L 3         //定义每个子句变元数 k
#define M_P 100     //定义变元个数m_p
#define NUM_S  200     //定义子句个数num_S
#define ALPHA 0.95

double T;               //温度
double E;              //能量值
int ns[NUM_S][L][2];   //with value 0 or 1
int mp[M_P];        //with random [0,1]
int anti_ns[NUM_S][L][2];	

void random_M()    //随机给m_p个变元赋初值0 或1
{
	int i=0;
   time_t t;
   srand((unsigned) time(&t)*10000);
   for(i=0;i<M_P;i++)
   {
		mp[i]=rand()%2;
   }
}

void random_N_K()     //初始化
{
  int i=0;
  int j=0;
  int k=0;
  int member=0;
  time_t t;
  srand((unsigned) time(&t)*10000);
  for(i=0;i<NUM_S;i++)
	  for(j=0;j<L;j++)
	  {
		member=rand()%M_P +1;
		ns[i][j][0]=member;
		ns[i][j][1]=mp[member-1];
	  }
		  

}
double random()   //生成0，1之间的一个小数,开区间
{
	int a;
	double r;
	time_t t;
   srand((unsigned) time(&t)*10000);
   a=rand()%10000;
   while(a==0)
   {
	   a=rand()%1000000;
   }
   r=(double)(a/1000000);
   return r;
}

int random_Three()   //0  1  2
{
	int r;
    time_t t;
   srand((unsigned) time(&t)*10000);
   r=rand()%3;
   return r;
}

void transfer()
{
	int i;
	int j;
	for(i=0;i<NUM_S;i++)
		for(j=0;j<L;j++)
		{
			anti_ns[i][j][0]=ns[i][j][0];
			anti_ns[i][j][1]=1-ns[i][j][1];    //将每个变元求反
		}
}

int is_sat()		//if result==0 then is OK!  要与transfer()一起使用
{
	int result;
	int s;
	int i;
	int j;
	result=0;
	for(i=0;i<NUM_S;i++)
	{
		s=1;                            //注意这里S的初值是多少
		for(j=0;j<L;j++)
			s*=anti_ns[i][j][1];
		result+=s;
		//printf("%d\n",result);
	}
	return result;
}

void random_Change()   //选择每个子句选个随机元取反，但不能重复选择
{
	int i;
	int r;
	int k;
	int j;
	int flag[M_P];    //标记此变元是否已经在别的子句里被取反了
	for(i=0;i<M_P;i++)
		flag[i]=0;
    for(i=0;i<NUM_S;i++)
	{
		j=ns[i][0][1]+ns[i][1][1]+ns[i][2][1];   //这里可以不用计算j，直接执行if里的代码
		if(j<3)
		{
		   r=random_Three();
		   k=ns[i][r][0]-1;
		   if(flag[k]==0)
		   {
			   flag[k]=1;
			   ns[i][r][1]=1-ns[i][r][1];
		   }
		}
	}
}

int simulated_Annealing(int e)
{
	int EE;
	int d_e;
	int i,j;
	double prob;
	double r;
	int save_ns[NUM_S][L][2];
	for(i=0;i<NUM_S;i++)
	for(j=0;j<L;j++)
	{
		save_ns[i][j][0]=ns[i][j][0];
		save_ns[i][j][1]=ns[i][j][1];    
	}
	random_Change();
	transfer();
	EE=is_sat();
	d_e=EE-e;  
	if(d_e<0)  //EE优于e
	{
		e=EE;   //接受变异
	}
	else
	{
		prob=exp(-d_e/T);
		r=random();
		if(prob<=r)     //不接受
		{
			for(i=0;i<NUM_S;i++)   //撤消上次random_Change()的变异
			for(j=0;j<L;j++)
			{
				ns[i][j][0]=save_ns[i][j][0];
				ns[i][j][1]=save_ns[i][j][1];    
			}
		    return e;
		}
		else
		{
			e=EE;        //接受
		}
	}
	return e;
}
int main()
{
	int i=0;
	int j=0;
	int k=0;
	int  e;
	int count=0;
	time_t rawtime;
    struct tm * timeinfo;
    clock_t start; 
	clock_t end; 
	int T_stay;				//在每个温度的循环次数
	for(i=0;i<M_P;i++) mp[i]=0;
	for(i=0;i<NUM_S;i++)
		for(j=0;j<L;j++)
			for(k=0;k<2;k++)
			ns[i][j][k]=0;
	random_M();
	random_N_K();
	for(i=0;i<NUM_S;i++)
	{ printf("the %d-th subsentence:\n",i+1);
		for(j=0;j<L;j++)
			printf("the %d-th code and it's number is %d ,value is %d \n" ,j+1,ns[i][j][0],ns[i][j][1]);

	}
	T=(double)(NUM_S*L);
	transfer();
	e=is_sat();                      //计算初始的能量值
	time ( &rawtime );
    timeinfo = localtime ( &rawtime );
    printf ( "Current date and time are: %s\n", asctime (timeinfo) );
	start = clock();
	T_stay=100;
	while(e>0)                    //需要退火
	{ 	
	T_stay--;
	e=simulated_Annealing(e);	  //simulated annealing
	if(T_stay==0)
	{
		T=ALPHA*T;
		T_stay=100;
	}
	//printf("STEP\n");
	if(T<0.00001)
		{
			count++;
			random_Change();
			T=NUM_S;
		}
	if(count>5000)
		break;
	}
 
	for(i=0;i<NUM_S;i++)
	{ printf("the %d-th subsentence:\n",i+1);
		for(j=0;j<L;j++)
			printf("the %d-th code and it's number is %d ,value is %d \n" ,j+1,ns[i][j][0],ns[i][j][1]);

	}
	printf("e is %d\n, count is %d,T is %f\n",e,count,T);
	time ( &rawtime );
    timeinfo = localtime ( &rawtime );
    printf ( "Current date and time are: %s\n", asctime (timeinfo) );
	end = clock(); 
	printf("It has passed %ld seconds\n", (end - start)/CLK_TCK);
	return 0;
}