转载请注明出处：http://blog.csdn.net/zhoubin1992/article/details/46440389
近期梳理，翻出了当年高级算法课程做的题目。禁忌搜索算法解决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)do
for j i+1 to |SVS| do
if((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++
else
candidate(i) isflipped //接受该变元的扰动
modify iteration_age[] //改动禁忌表
flag=0 flips++
iteration++;
C++实现代码：
// TS3SAT.cpp : 定义控制台应用程序的入口点。 //
/*********************************
-----------------------------------
禁忌搜索算法解决3SAT问题(C++代码实现)
-----------------------------------
Author:牧之丶 Date：2014年
Email:[email protected]
**********************************/
#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;
else
sign[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)：http://download.csdn.net/detail/zhoubin1992/8794893
參考文献
[1] 张德富.算法设计与分析（高级教程）[M].国防工业出版社。2007.