转载请注明出处：
最近梳理，翻出了当年高级算法课程做的题目，禁忌搜索算法解决3SAT问题。吐槽：数学符号如何在编辑器里打出来啊，为了保留符号，我直接截图了。1 SAT问题描述
定理4.4.1：
赋值v为使CNF可满足的充要条件是f(x1,x2,…,xm)达到最小值0。
2 禁忌搜索算法
禁忌搜索算法是在局部搜索的过程中引进了贪心选择机制，并利用禁忌表修改邻域，通过构造的候选邻域来控制解得选择和接受过程。在搜索的过程中，禁忌搜索算法从上一步计算解的候选邻域里选择一个最好的解，即使这个解比上一步得到的解还差，也接受它，同时修改禁忌表，以避免该解在禁忌期限内再次被选择。
思路分析如下：
1 初始赋值
随机初始化变元值
2 候选邻域的构造：
对于当前的赋值X,从每一个非零子句中选出一个变元，所有选出的变元构成一个子变元集SVS。从SVS里选择一个变元，改变它的值，其他的变元值保持不变，得到的解为X的一个邻解。所有邻解的集合，就构成了候选邻域。减少搜索空间，，提高了搜索效率。
3 禁忌表：
禁忌表记录着在最近L次迭代内扰动过得变元，这些变元在当前迭代范围内禁忌扰动。
禁忌表用数组iteration_age[i],i=1,2,…m来表示，iteration_age[i]的值为变元xi被扰动时的迭代序数
变元xi是不是被禁忌：
iteration_age[i]+L>=iteration
禁忌搜索算法解决3SAT问题的伪代码：
算法伪代码： initcnf();initialiteration_age[] //初始化CNF，禁忌表 iteration = 1;flips =1//迭代次数和扰动次数初始化 while(v_cnf(variable)!=0&&iteration< itera_max) //停止准则 SVS[] //从每一个非零子句中选出一个变元 flag = 1;i =0 while(i<|SVS|&&flag==1)dofor j i+1 to |SVS| doif((candidate(j)-v_cnf(variable))<(candidate(s)-v_cnf(variable))) //从SVS选择f'最小的变元 选择策略 then swap SVS[i] andSVS[j]if(iteration_age[SVS[i]]+L>=iteration) //如果变元禁忌if(candidate(i)-v_cnf(variable)<0) //吸引准则 candidate(i) isflipped //接受该变元的扰动 modify iteration_age[] //修改禁忌表 flag=0 flips++else i++elsecandidate(i) isflipped //接受该变元的扰动 modify iteration_age[] //修改禁忌表 flag=0 flips++ iteration++;
C++实现代码：
// TS3SAT.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "stdafx.h"#include <string>#include <time.h>#include <fstream>#include <iostream>#include <iterator>using namespace std;const int n=129; //子句个数const int l=3;const int m=30; //变元个数const int L=20;//禁忌表长度const int N=1000;int clause[n+5][l+5];//下标数组 int sign[l*n+1];//CNF变元符号int variable[m+1];//变元数组//int neighbour[n];//邻域int SVS[N];//子变元集int vclause[n+5];//子句的值int itera_max = 500000;int iteration_age[m];//禁忌表int t;//int v;//f(x)目标函数void initcnf()//CNF初始赋值{printf("\n");ifstream in("1.txt");for(int i =0;i<n+5;i++) {for(int j=0;j<=3;j++){clause[i][j]=1;} }for (int i = 1; i <= n; i++){in >> clause[i][1] >> clause[i][2] >> clause[i][3] >> t;}//下标变元随机赋值/*for(int i=0;i<n;i++){for(int j=0;j<l;j++){clause[i][j]=rand()%m+1;//1到m}}*///各变元符号 0为反 1为正for(int i=1; i<=n; i++)for(int j=1; j <= l; j++){//sign[i] == clause[i][j]/abs(clause[i][j]);if(clause[i][j]/abs(clause[i][j]) == 1)sign[i]=1;elsesign[i]=0;}for(int i=1;i<=m;i++){iteration_age[i]=0;}for(int i=0;i<=N;i++){SVS[i]=0;}}int v_cnf(int var[])//f(x)的值{int v=0;for(int i=1;i<=n;i++){vclause[i]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=l;j++){vclause[i] *= (sign[3*(i-1)+j]^var[abs(clause[i][j])]);//各个子句的值}v+=vclause[i];}return v;}int candidate(int a)//邻解{int var1[m+1];//memcpy(var1,variable,m+1);for (int t = 0; t < m+1; t++)var1[t] = variable[t];int v=0;//v=v_cnf();var1[SVS[a]]=1-var1[SVS[a]];v=v_cnf(var1);return v;}void tssat()//禁忌搜索{srand(double(time(NULL)));for(int i=1;i<=m;i++)//变元赋值{variable[i]=rand()%2;//0到1}printf("变元初始赋值为：");for(int i=1;i<=m;i++){printf("%d ",variable[i]);}initcnf();int iteration=1;int flips=1;int c=v_cnf(variable);printf("初始f(X)=%d ",c);printf("\n");while(v_cnf(variable)!=0&&iteration < itera_max){int a=0;for(int i=0;i<n;i++)//从每一个非零子句中选出一个变元{if(vclause[i]==1){int svs=abs(clause[i][rand()%l]);SVS[a]=svs;//选出变元的下标int pos = 1;for(int i=0;i<a;i++){if(SVS[a]==SVS[i]){pos = 0;break;}}if (pos == 1){a++;}}int flag=1;int s=0;while(s<a&&flag==1){for(int j=s+1;j<a;j++){if((candidate(j)-v_cnf(variable))<(candidate(s)-v_cnf(variable)))//选择f'最小的变元{/*int temp=candidate(i);candidate(i)=candidate(j);candidate(j)=temp;*/int temp=SVS[s];SVS[s]=SVS[j];SVS[j]=temp;}}if(iteration_age[SVS[s]]+L>=iteration)//变元是否禁忌{if(candidate(s)-v_cnf(variable)<0)//吸引准则{variable[SVS[s]]=1-variable[SVS[s]];iteration_age[SVS[s]]=iteration;flag=0;flips++;}else{//flag=0;s++;}}else{variable[SVS[s]]=1-variable[SVS[s]];iteration_age[SVS[s]]=iteration;flips++;flag=0;}}iteration++;}printf("扰动次数为：%d ",flips);printf("\n");printf("变元最终取值为：");for(int i=0;i<m;i++){printf("%d ",variable[i]);}printf("\n");int v=v_cnf(variable);printf("最终f(X)=%d\n ",v);}}int _tmain(int argc, _TCHAR* argv[]){time_t start,end;start = clock();tssat();end = clock();printf("\n");printf("运行时间为：%f\n",double(end – start)/(CLOCKS_PER_SEC));system("pause");return 0;return 0;}
测试所有给出的样例，运行20次可得结果如下：
CNF(l=3)
平均时间
成功/失败次数
N m
TS
TS
30 129
0.8200
20/0
40 172
0.9500
20/0
50 215
0.1500
20/0
100 430
0.2600
20/0
测试用例(1.txt)：
参考文献
[1] 张德富.算法设计与分析（高级教程）[M].国防工业出版社，2007.
因为在路上你就已经收获了自由自在的好心情。
