贪心算法解SAT
时间:2010-11-21 来源:刘润佳
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define ARRAYLENGTH 20
#define SENTENCES 91
#define VARIABLE 3
#define SenLength 128
//定义数组存储变元个数
int array[ARRAYLENGTH];
//定义存储子句的数值的数组
int sent[SENTENCES][VARIABLE];
//定义数组表示子句是否验证过,false为未验证,true为验证
int check[SENTENCES];
//定义最大的翻转次数
int Max_Flips;
//初始化数组
void initialArray(int temp[],int length)
{
int i=0;
for(;i<length;i++)
{
temp[i]=0;
}
}
void initialCheck(int temp[],int length)
{
int i;
for(i=0;i<length;i++)
{
temp[i]=0;
}
}
/*本函数用来是初始化子句数组,其功能是把子句里面的数字从string类型转换为int类型,并存储在数据空间里面
@ptr字符指针,保存文件名
@temp[][VARIABLE] 保存子句里的数值
@ firLen 表示数组第一个下标
@ secLen 表示数组第二个下标
*/
void initalSentArray(char *ptr,int temp[][VARIABLE],int firLen,int secLen)
{
FILE *fptr;
int i,j,k,m,n;
char str[SenLength];
char strTemp[SenLength];
if(fptr=fopen(ptr,"r"))
{
for(i=0,j=0;(fgets(str,SenLength,fptr))!=NULL;i++)
{
//printf("%d%s%s\n",i," ",str);
k=0;
if(str[0]!='c'&&str[0]!='0'&&str[0]!='%'&&str[0]!='p')
{
//printf("%d%s%s",j," ",str);
for(m=0,n=0;m<strlen(str);m++)
{
if(str[m]==' '&&m!=0)
{
if(strlen(strTemp)>0)
{
temp[j][k]=atoi(strTemp);
k++;
for(;n>=0;n--)
{
strTemp[n]=' ';
}
n=0;
}
}
else
{
strTemp[n]=str[m];
n++;
}
}
j++;
}
}
fclose(fptr);
}
else
{
printf("%s\n","打开文件失败");
}
}
//检查满足子句的个数(取true时的个数-取false时的个数)
int satisfyCount(int index)
{
int count=0,i,j,sum;
for(i=0;i<SENTENCES;i++)
{
sum=0;
if(check[i]==0)
{
for(j=0;j<VARIABLE;j++)
{
if(sent[i][j]-1==index)
sum+=1;
else if(-1-sent[i][j]==index)
sum+=0;
else if(sent[i][j]>0)
sum+=array[sent[i][j]-1];
else
sum+=(array[0-sent[i][j]-1]?0:1);
//if(sent[i][j]-1==index)
//{
// count++;
//}
}
if(sum>0)
count++;
}
}
for(i=0;i<SENTENCES;i++)
{
sum=0;
if(check[i]==0)
{
for(j=0;j<VARIABLE;j++)
{
if(sent[i][j]-1==index)
sum+=0;
else if(-1-sent[i][j]==index)
sum+=1;
else if(sent[i][j]>0)
sum+=array[sent[i][j]-1];
else
sum+=(array[0-sent[i][j]-1]?0:1);
//if(sent[i][j]-1==index)
//{
// count++;
//}
}
if(sum>0)
count--;
}
}
return count;
}
//设置满足的子句
void setSatisfy(int index)
{
int i,j;
for(i=0;i<SENTENCES;i++)
{
if(check[i]==0)
{
for(j=0;j<VARIABLE;j++)
{
if(sent[i][j]-1==index)
{
check[i]=1;
}
}
}
}
}
//计算现在以满足的字句数
int totalSatisfyCount()
{
int count=0,i;
for(i=0;i<SENTENCES;i++)
{
if(check[i])
count++;
}
return count;
}
//输出解
void printfAnswer()
{
int j;
for(j=0;j<ARRAYLENGTH;j++)
{
printf("%d ",array[j]);
if(j%50==0&&j!=0)
{
printf("\n");
}
}
}
/*检查是否满足,满足则返回true,不满足则返回false*/
int isSat()
{
int sum,i,j;
for(i=0;i<SENTENCES;i++)
{
sum=0;
for(j=0;j<VARIABLE;j++)
{
if(sent[i][j]>0)
sum+=array[sent[i][j]-1];
else
sum+=array[0-sent[i][j]-1]?0:1;
}
if(sum==0)
{
return 0;
}
}
return 1;
}
int greedy()
{
int sententsOfSat,flag=0;
int index=ARRAYLENGTH;
int i,temp;
//每次调用一次递减
Max_Flips--;
for(i=0;i<ARRAYLENGTH;i++)
{
if(array[i]!=1)
{
temp = satisfyCount(i);
if(flag==0)
{
sententsOfSat=temp;
index=i;
flag=1;
}
if(temp>sententsOfSat)
{
sententsOfSat=temp;
index=i;
}
}
}
if(index!=ARRAYLENGTH&&Max_Flips>=0)
{
array[index]=1;
setSatisfy(index);
if(totalSatisfyCount()==SENTENCES||isSat())
{
return 1;
}
else
{
return greedy();
}
}
else
{
return 0;
}
}
void run(char *str)
{
//当前时间
clock_t startTime,endTime;
//设定最大翻转次数==变元个数
Max_Flips=ARRAYLENGTH;
FILE *fp;
int j;
if((fp=fopen("刘润佳10212764\\10212764--greedy.txt","a+"))==NULL)
{ /*以文本只写方式打开文件*/
printf("cannot open file");
exit(0);
}
startTime=clock();
//初始化Array
initialArray(array,ARRAYLENGTH);
initialCheck(check,SENTENCES);
initalSentArray(str,sent,SENTENCES,VARIABLE);
//输出格式设定
fprintf(fp,"%s\n","#刘润佳 10212764");
str+=5;
//printf("%s%s%s%d%d%d","#",str," ",-VARIABLE,-ARRAYLENGTH,-SENTENCES);
fprintf(fp,"%s%s%s%d%d%d","#",str," ",-VARIABLE,-ARRAYLENGTH,-SENTENCES);
if(greedy())
{
//结束时间
endTime=clock();
//printf("%s%f\n","运行时间是:",((float)(endTime-startTime))/1000);
double timeOff = ((double)(endTime-startTime))/1000;
//printf("%f\n",-timeOff);
fprintf(fp,"%s%f\n","-",timeOff);
for(j=0;j<ARRAYLENGTH;j++)
{
fprintf(fp,"%d ",array[j]);
if(j%50==0&&j!=0)
{
//printf("\n");
fprintf(fp,"\n");
}
}
//printf("%s%f\n","运行时间是:",((double)(endTime-startTime))/1000);
//printfAnswer();
}
else
{
//结束时间
endTime=clock();
//printf("%s%f\n","运行时间是:",((float)(endTime-startTime))/1000);
double timeOff = ((double)(endTime-startTime))/1000;
//printf("%f\n",-timeOff);
fprintf(fp,"%s%f\n","-",timeOff);
fprintf(fp,"%s\n","无解");
}
fprintf(fp,"\n");
fclose(fp);
}
int main()
{
char *str="test\\t1.txt";
run(str);
str="test\\t2.txt";
run(str);
str="test\\t3.txt";
run(str);
str="test\\t4.txt";
run(str);
str="test\\t5.txt";
run(str);
str="test\\t6.txt";
run(str);
str="test\\t7.txt";
run(str);
str="test\\t8.txt";
run(str);
str="test\\t9.txt";
run(str);
str="test\\t10.txt";
run(str);
system("pause");
return 0;
}