文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>贪心算法解SAT

贪心算法解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;
}

相关阅读 更多 +
排行榜 更多 +
超级冒险王安卓版

超级冒险王安卓版

休闲益智 下载
玩具小镇手机版

玩具小镇手机版

休闲益智 下载
这一关特上头手机版

这一关特上头手机版

休闲益智 下载