基于禁忌搜索算法求解随机约束满足问题

李飞龙　赵春艳　范如梦

摘 要：为了求解具有增长取值域的随机约束满足问题（CSP），提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先，利用禁忌搜索得到一组启发式的初始赋值，即由一个随机初始化的可行解通过邻域构造一组候选解，再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解，就把它作为启发式的初始赋值，再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明，所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解，与其他局部搜索算法相比，表现出了显著的优越性，可用于随机CSP的算法设计。

关键词：随机约束满足问题;RB模型;相变现象;禁忌搜索;模拟退火;算法效率

中图分类号： TP301.6文献标志码：A

Solving random constraint satisfaction problems based on

tabu search algorithm

LI Feilong， ZHAO Chunyan*， FAN Rumeng

（College of Science， University of Shanghai for Science and Technology， Shanghai 200093， China）

Abstract： A novel algorithm based on tabu search and combined with simulated annealing was proposed to solve random Constraint Satisfaction Problem （CSP） with growing domain. Firstly， tabu search was used to obtain a set of initial heuristic assignments， which  meant a set of candidate solutions were constructed based on a randomly initialized feasible solution through neighborhood， and then the tabu table was used to move the candidate solutions to the direction of minimizing the objective function value. If the obtained optimal assignment was not the solution of the problem， the assignment would be used as the initial heuristic assignment and then simulated annealing was performed to correct the set of assignments until the global optimal solution was obtained. The numerical experiments demonstrate that， the proposed algorithm can effectively find the solution of problem when approaching the theoretical phase transition threshold of problem， and it shows obvious superiority compared with other local search algorithms. The proposed algorithm can be applied to the algorithm design of random CSP.

Key words： random Constraint Satisfaction Problem （CSP）;Revised B （RB） model; phase transition phenomenon; tabu search; simulated annealing; algorithm efficiency

0 引言

約束满足问题（Constraint Satisfaction Problem， CSP）是人工智能领域的一个重要分支[1-2]，它在物流规划、生产调度、产品配置器、生物信息等领域都有非常广泛的应用。

CSP模型是探索非确定性多项式（Non-deterministic Polynomial， NP）-完全问题难解性的重要基础。为了克服标准CSP模型中B模型的平凡渐进不可满足性[3-5]，Xu等[6]提出了RB（Revised B）模型并证明了该模型具有精确的可满足性相变现象。随后，Xu等[7-8]又从理论和实验上证明了RB（Revised B）模型在相变区域能产生大量的难解实例。近年来，RB模型受到了国内外研究学者的广泛研究[9-12]。理论上，沈静等[13-16]提出了基于RB模型的推广模型;Zhou等[17]改进了发生相变的条件。实验上，Zhao等[18-20]设计了基于置信传播的算法来求解RB模型;原志强等[21]提出了改进的模拟退火（Simulated Annealing， SA）和遗传算法;吴拨荣等[22]将置信传播和模拟退火相结合来求解RB模型。此外，基于RB模型的难解算例被用于各种算法竞赛[23]。

本文提出了一种基于禁忌搜索（Tabu Search， TS）并与模拟退火（SA）相结合的高效算法来求解RB模型这类具有可变取值域的随机CSP， 命名为TS-SA。首先，利用TS得到一个启发式的初始赋值，即由一个初始可行解通过邻域生成一组候选解，利用禁忌表使得候选解向目标函数值减小的方向移动。如果得到的赋值不是问题的解，再利用SA对该赋值进行优化直至得到最优解。实验结果表明，TS-SA算法的求解性能显著优于TS、SA以及其他局部搜索算法。在难解区域即使找不到解，得到的最优解仅使得极少数的约束是不可满足的。

1 RB模型

RB模型由一个变量集合X={x1，x2，…，xN}和一个约束集合C={C1，C2，…，CM}构成[6]。每个变量xi都从定义域D={1，2，…，dN}中取值，这里dN=Nα，α>0为常数。不难看出，RB模型中变量的取值域规模随着变量数的增加呈多项式级增长，因此RB模型可以看作是一类具有可变取值域的随机CSP。每个约束Ca都由一个变量的子集Xa和其相应的不相容赋值集合Qa所构成。从N个变量中随机选取k（k≥2）个不同的变量构成Xa，从Xa可能的dk个赋值中随机不重复地选取pdk个k元赋值作为不相容赋值集合Qa，这里00是常数）个就构成了RB模型的一个随机实例RB（k，N，r，α，p） 。

若能找到这N个变量的一组完全赋值，使得所有约束同时被满足，这组赋值就是RB（k，N，r，α，p）的一个解。文献[6]中已经严格证明了RB模型存在精确的可满足性相变现象，即用Pr（SAT）表示随机实例有解的概率，则有以下结论成立：

定理 设ps=1-e-α/r，若α>1/k，r>0是两个常数，且满足ke-α/r≥1 ，则：

limN→∞ Pr（SAT）=1， p

0，p>ps （1）

该定理表明，当N→∞时，约束紧度存在一个阈值ps，若p>ps，RB模型随机实例有解的概率趋近于0;若p

由于二元RB模型（即k=2）是NP-完全问题，故下面的算法均用于求解二元RB模型的随机实例。而k>2的情形可以通过多项式时间归约为二元的情形。

2 TS算法

TS算法是对局部邻域搜索算法的推广，是对人类智力过程的一种模拟，是人工智能的一种体现。它区别于其他现代启发式算法的显著特点是利用记忆来引导算法的搜索过程。TS算法涉及邻域、候选解、禁忌表、禁忌长度、藐视准则等概念。在邻域搜索的基础上，通过禁忌表来避免重复搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证搜索空间的多样化，最终实现对全局的优化。

为将TS算法应用于求解RB模型，先给出目标函数的定义。对RB模型的一个随机实例，设N个变量的一组完全赋值为X0=（σ1，σ2，…，σN） ，相应的约束Ca中变量的赋值为X0a=（σ1a，σ2a，…，σNa）。定义目标函数为不可满足约束的数目，即：

E（X0）=∑Ma=1[1-S（X0a）]（2）

其中：

S（X0a）=1， σ1a，σ2a，…，σkaQa

0，σ1a，σ2a，…，σka∈Qa（3）

由此可见，若一组赋值使得目标函数值为0，则这组赋值就是实例的解;否则就不是解。

给定RB模型变量的一组赋值，先随机且不重复地从这N个变量中选取NCa个变量对Xij=（xi，xj）构成邻域变量集合。采用两种不同的策略改变这组赋值中每对所对应的赋值构成NCa组候选解。这两种策略分别是：将Xij中xi和xj的赋值相互交换;重新对xi和xj进行随机赋值。将这组候选解中使得目标函数取得最小值的那组赋值作为最优候选解，它所对应的Xij作为禁忌对象置入禁忌表中。禁忌表可以看作是一个N×N的矩阵，矩阵中的元素是禁忌对象Xij。禁忌表的主要目的是禁止这些禁忌对象在近期内参与最优候选解的选择，从而避免搜索过程中出现循环和陷入局部最优的现象。在最优候选解更新过程中，要设定禁忌对象不允许被选取的最大次数即禁忌长度。禁忌长度的选取与问题特征有关，它在很大程度上决定了算法的计算复杂性。在TS算法中，设禁忌长度LTabu=N（N-1）/2，这样能保证更新禁忌表时，至少有一个变量对Xij被选择。当禁忌长度为0时，禁忌表会释放相应的禁忌对象，重新参与候选解的选择。在赋值更新过程中，可以设置藐视准则，也就是最优候选解优于当前最优解时，即使这组賦值中所对应的Xij在禁忌表中，也可以忽视其禁忌属性，用它代替当前解和最优解。若不存在上述最优候选解，则在候选解中选择非禁忌的次优候选解为新的当前解，将对应的Xij加入禁忌表，同时修改禁忌表中各禁忌对象的禁忌长度。重复上述迭代搜索过程，直到最优解对应的目标函数值为零，则停止迭代;否则，直至达到最大迭代次数。

TS算法的具体步骤如下：

输入 二元RB模型的一个随机实例以及TS算法中候选解的数目NCa，最大迭代次数tmax;

输出 找到的最优解以及对应的目标函数值。

步骤1 初始化禁忌表为N×N的零矩阵，由公式计算禁忌长度，随机初始化一组赋值X0。

步骤2 t=0。

步骤3 计算目标函数值E（X0），如果E（X0）=0，则输出最优解及对应的目标函数值。

步骤4 随机生成邻域变量集合，对邻域变量集合采用两种策略构造NCa组候选解。计算候选解目标函数值，按照从小到大保留较优的NCa/2组候选解并记录对应的变量对Xij。将使得目标函数值最小的候选解设为最优候选解，并记录对应的目标函数值。

步骤5 如果最优候选解优于当前迭代的最优解或满足藐视准则，则将最优候选解作为当前解和最优解，并将其他禁忌对象的禁忌长度减1;否则将候选解中次优且在禁忌表中对应的禁忌长度为0的候选解作为当前解，并将其他禁忌对象的禁忌长度减1。

步骤6 t=t+1。

步骤7 如果t>tmax，则输出最优解及对应的目标函数值;否则返回步骤3。

可以看出，TS算法先通过邻域构造了一组候选解，增强了全局搜索能力;再利用禁忌表使得目标函数值向减少的方向移动，使算法具备较好的局部搜索能力。虽然该算法受初始赋值和邻域结构的影响较大，很难得到全局最优解，但是搜索过程分布性好，搜索得到的最优解仅使得较少的约束是不可满足的。

SA算法是启发式算法的一种。该算法从高温出发，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优时能概率性地跳出并最终趋于全局最优。可见，SA算法的局部搜索能力很强，可以很好地避免陷入局部最优;但是其对初始解的依赖性较大。考虑到TS算法较强的全局搜索能力以及SA算法较强的局部搜索能力，本文将两种算法结合提出了TS-SA算法来求解RB模型这类具有可变取值域的随机CSP。

3 TS-SA算法

TS-SA算法可以概括为两步：第一步，利用TS算法得到最优解;第二步，若利用TS算法得到的最优解不是RB模型随机实例的解，就将此解作为SA算法的启发式初始赋值，再执行SA算法对该赋值进行修正，直至得到最优解。

TS-SA算法具体步骤如下：

输入 二元RB模型的一个随机实例，以及TS算法中候选解的个数NCa，最大迭代次数tmax;SA算法中初始温度T0，终止温度Tf，温度控制参数a，同一温度下最大迭代次数L。

输出 找到的最优解以及对应的目标函数值。

步骤1 运行上述TS算法，将返回的最优赋值作为当前解X0。

步骤2 T=T0。

步骤3 i=0。

步骤4 计算目标函数值E（X0），如果E（X0）=0，则输出最优解及对应的目标函数值。

步骤5 随机生成一个0到1之间的实数rand1。程序前

if （rand1<3/T） {令X0=Xbest，随机选取一个不可满足的约束，从其所关联变量的协调赋值集合中随机选取一组赋值，从而得到一组新的赋值记作Xnew}

else {对于X0，随机选取一个不可满足的约束，从其所关联变量的协调赋值集合中随机选取一组赋值，从而得到一组新的赋值记作Xnew}。程序后

步骤6 计算ΔE=E（X0）-E（Xnew） ;程序前

if （ΔE<0）{随机取一个0到1之间的实数rand2

if （rand2

else {go to 步骤7}}

else {令X0=Xnew}。

程序后步骤7 计算当前解的目标函数值E（X0），如果优于最优解，则将当前解赋予最优解。

步骤8 i=i+1。

步骤9 如果i>L，则T=a·T;否则返回步骤4。

步骤10 如果T

由此可以看出，TS-SA算法先通过TS算法得到启发式的初始赋值，再执行SA算法对该赋值进行修正直至得到最优解。其中，TS算法通过邻域构造候选解，是多个体进行迭代搜索，有效地避免了陷入局部最优解。SA算法是单个体迭代搜索，由以TS算法得到的启发式初始赋值避免了SA算法对初始赋值的依赖问题。TS-SA算法有效地利用了TS和SA这两个算法的优点，因此可以表现出良好的求解性能。

4 实验与结果分析

4.1 TS-SA算法结果

在RB模型中，取k=2，α=0.8，r=3，N∈{20，40，60，80，100}，由第1章中的定理可以求出理论的可满足性相变点为ps=0.234。在不同的问题规模N下，RB模型的定义域规模d、约束数目M等参数值如表1所示。

在TS算法中，取候选解个数NCa=120，最大迭代次数tmax=103，LTabu由禁忌长度公式计算。在随机生成的50个实例RB（2，N，3，0.8，p）上测试TS算法的求解性能，求解概率如图1所示。从图1可以看出，当N=20时，TS算法在约束紧度p≤0.15的范围内以概率1找到解，而在p≥0.23时算法失效;在N=100时，TS算法在约束紧度p≤0.09的范围内以概率1找到解，而在p≥0.12时算法失效。若取最大迭代次数tmax=2000，求解概率如圖2所示，取N=60。从图2可以看出，增加迭代次数并没有从本质上改变算法意义上RB模型发生相变的区域，仅在个别点处提高了求解概率。因此，本文中算法的最大迭代次数取tmax=1000。

取N=40，TS算法求解随机实例的平均迭代次数和平均运行时间如表2所示，其中：t表示平均迭代次数， time表示平均运行时间。从表2中可以看出，随着p的不断增加，TS算法的运行时间呈指数级增长。当p≤0.14时，TS算法可以在较短的时间内通过较少的迭代次数以概率1收敛到实例的解;当0.14

在 TS-SA算法中，取候选解个数NCa=120，最大迭代次数tmax=103，LTabu由禁忌长度公式计算。取初始温度T0=97，终止温度Tf=3，温度控制参数a=0.95，同一温度下最大迭代次数L=103。对于不同的问题规模N，分别在随机生成的50个实例RB（2，N，3，0.8，p）上测试TS-SA算法的求解性能，求解概率如图3所示。从图3中可以看出：当N=20时，TS-SA算法在约束紧度p≤0.16的范围内以概率1找到解，而在p≥0.23时算法失效;当N=100时，TS-SA算法在约束紧度p≤0.12的范围内以概率1找到解，而在p≥0.17时算法失效。

TS算法和TS-SA算法在求解二元RB模型随机实例过程中，在p=0.10和p=0.13时算法的平均运行时间分别如图4和图5所示。从图4（a）和图5（a）可以看出，两种算法在N≤100时平均运行时间基本一样。这是由于在p≤0.10时TS算法起主要作用，它能比较有效地找到实例的解，此时并不需要运行SA算法对TS算法得到的最优赋值进行优化或者仅在少数情况下需要再执行SA算法。从图4（b）和图5（b）可以看出，这两种算法在N≤80时平均运行时间基本一样;而当N=100时，TS-SA算法的运行时间明显比TS算法多。这说明在p=0.13时随着变量数目N的增加，需要再运行SA算法对TS算法得到的赋值进行修正才能得到实例的解或者最优解。

当p≥0.16时，TS算法和TS-SA开始失效，即不能有效地找到二元RB模型随机的解，也就是得到的最优解不能使得所有约束都是可满足的。对于不同的问题规模N，由TS算法和TS-SA算法得到的最优解使得约束不可满足的平均数目如表3～4所示。从表3和表4可以看出，在邻近相变点时TS-SA算法虽然找不到实例解，但是得到的最优解仅使得极少数的约束是不可满足的;并且TS-SA算法求解RB模型时得到的平均不可满足约束数目明显少于TS算法所得到的。

TS-SA算法总能收敛到一组赋值，该赋值是此算法得到的最优解。事实上，当p较小时，只执行TS算法就能找到实例的解。随着p的不断增大，TS得到的赋值逐渐不能使得目标函数为0，需要执行SA算法对由TS算法得到的启发式初始赋值进行修正，直到得到全局最优解。如图6所示，可以看到，取N=40，p从0.15增大到0.19时，在TS-SA算法找到解的实例中，仅执行TS算法就能找到解的实例数目比例在逐渐降低，需要执行SA算法才能找到解的实例数目占比逐渐增大。这表明在TS算法失效的情况下，SA算法的局部搜索能力开始占主导地位。直到非常接近理论相变点时，TS-SA算法失效，不能收敛到实例的解。

4.2 算法对比

将本文提出的TS-SA算法与TS算法，文献[21]中提出的GSA（Genetic Simulated Annealing）算法、RSA（Revised Simulated Annealing）算法，文献[22]中提出的BP-RSA-1（Belief Propagation-Revised Simulated Annealing-1）、BP-RSA-2（Belief Propagation-Revised Simulated Annealing-2）算法进行对比。特别地，取N=100，对于不同的约束紧度p，分别在随机生成的50个实例RB（2，N，3，0.8，p）上运行算法，得到的求解概率如图7所示。由图7可以看出，本文提出的TS-SA算法求解效率明显优于TS算法、RSA算法;与BP-RSA-1算法、BP-RSA-2算法、GSA算法相比，TS-SA算法也在一定程度上提高了求解概率。

取N=60，p=0.13时，TS-SA算法、BP-RSA-1算法、GSA算法和RSA算法的平均运行时间如图8所示。由图8可以看出，当N较大时，与其他算法相比，本文提出的TS-SA算法花费了较多的运行时间。而由图4可知，当N较小时，只运行TS算法就可以花费较少的时间有效地找到实例的解。这是因为大多数的实例都需要花费时间来执行SA算法对由TS得到的启发式初始赋值进行修正。

取N=60，p≥0.17，五种算法求解RB模型随机实例找不到解时，得到的平均不可满足约束数目如表5所示。由表5可以看出，由TS算法得到的不可满足约束的数目要小于RSA算法所得到的，可见TS算法的全局搜索能力是优于RSA算法的。从求解概率来看，RSA算法的局部搜索能力优于TS算法。而将TS和SA结合得到的TS-SA算法所得到的平均不可满足约束数目是最少的。当p=0.17时，TS-SA算法的平均最少不可满足约束的数目占约束总数的比例约为0.3%;当p=0.20时，TS-SA算法的平均最少不可满足约束的数目占约束总数的比例约为1.1%。这充分表明了本文提出的TS-SA算法虽然在非常接近理论相变点时找不到实例的解，但得到的最优解仅使得近1%的约束是不可满足的。

5 结语

本文提出了一种基于TS并与SA相结合的高效算法TS-SA来求解RB模型这类具有可变取值域的随机约束满足问题（CSP）。TS-SA算法是利用TS算法得到最优初始赋值，在不是问题解的情况下再执行SA算法对这个启发式的初始赋值进行优化。实验结果表明，在接近理论相变点时，TS-SA算法能有效地找到隨机实例的解;在理论相变点附近，即使算法失效，得到的最优解仅使得极少数的约束是不可满足的。这表明TS-SA算法充分利用了TS和SA算法的优势，既在全局搜索，又对局部优化，表现出了良好的求解性能，可用于对随机CSP的算法设计。接下来的工作中我们会尝试研究将禁忌搜索算法与其他局部搜索算法相结合来进一步优化算法的求解性能，从而探索CSP解空间的演化规律，以及问题难解性的根源。

参考文献 （References）

[1]TSANG E. A glimpse of constraint satisfaction [J]. Artificial Intelligence Review， 1999， 13（3）： 215-227.

[2]MOLLOY M. Models for random constraint satisfaction problems [J]. SIAM Journal of Computing， 2003， 32（4）： 935-949.

[3]SMITH B M， DYER M E. Locating the phase transition in binary constraint satisfaction problems [J]. Artificial Intelligence， 1996， 81（1/2）： 155-181

[4]ACHLIOPTAS D， MOLLOY M S O， KIROUSIS L M， et al. Random constraint satisfaction： a more accurate picture [J]. Constraints， 2001， 6（4）： 329-344.

[5]GENT I P， MACINTYRE E， PROSSER P， et al. Random constraint satisfaction： flaws and structure [J]. Constraints， 2001， 6（4）： 345-372.

[6]XU K， LI W. Exact phase transitions in random constraint satisfaction problems [J]. Journal of Artificial Intelligence Research， 2000， 12（1）： 93-103.

[7]XU K， LI W. Many hard examples in exact phase transitions [J]. Theoretical Computer Science， 2006， 355（3）： 291-302.

[8]XU K， BOUSSEMART F， HEMERY F， et al. Random constraint satisfaction： Easy generation of hard （satisfiable） instances [J]. Artificial Intelligence， 2007， 171（8/9）： 514-534.

[9]LIU T， LIN X， WANG C， et al. Large hinge width on sparse random hypergraphas [C]// Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Reston： AAAI， 2011： 611-616.

[10]ZHAO C， ZHENG Z. Threshold behaviors of a random constraint satisfaction problem with exact phase transitions [J]. Information Processing Letters， 2011， 111（20）： 985-988.

[11]徐偉，巩馥洲.值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析[J].计算机科学，2014，41（4）：205-210.（XU W， GONG F Z. Computational complexity analysis of backtrack-free and random-walk strategies on constraint satisfaction problems with growing domains [J]. Computer Science， 2014， 41（4）： 205-210.）

[12]王晓峰，许道云.RB模型实例集上置信传播算法的收敛性[J].软件学报，2016，27（11）：2712-2724.（WANG X F， XU D Y. Convergence of the belief propagation algorithm for RB model instances [J]. Journal of Software， 2016， 27（11）： 2712-2724.）

[13]沈静.约束满足问题的模型构造和相变现象[D].武汉：华中师范大学，2011：13-30.（SHEN J. A model of random constraint satisfaction problems and phase transitions [D]. Wuhan： Central China Normal University， 2011： 13-30.）

[14]沈静，梅丹.可满足实例的归结复杂度[J].计算机工程与应用，2014，50（22）：69-72.（SHEN J， MEI D. Resolution complexity of satisfiability instances [J]. Computer Engineering and Applications， 2014， 50（22）： 69-72.）

[15]SHEN J， REN Y. Bounding the scaling window of random constraint satisfaction problems [J]. Journal of Combinatorial Optimization， 2016， 31（2）： 786-801.

[16]沈静，任耀峰，梅丹，等.一种产生可满足性难解实例的模型[J].海军工程大学学报，2016，28（3）：5-8.（SHEN J， REN Y F， MEI D， et al. A model to generate hard satisfiable instances [J]. Journal of Naval University of Engineering， 2016， 28（3）： 5-8.）

[17]ZHOU G， GAO Z， LIU J. On the constraint length of random-CSP [J]. Journal of Combinatorial Optimization， 2015， 30（1）： 188-200.

[18]ZHAO C， ZHOU H， ZHENG Z， et al. A message-passing approach to random constraint satisfaction problems with growing domains [J]. Journal of Statistical Mechanics： Theory and Experiment， 2011（2）： Article No. P02019.

[19]赵春艳，郑志明.一种基于变量熵求解约束满足问题的置信传播算法[J].中国科学：信息科学，2012，42（9）：1170-1180.（ZHAO C Y， ZHENG Z M. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems [J]. SCIENTIA SINICA Informationis， 2012， 42（9）： 1170-1180.）

[20]ZHAO C， ZHANG P， ZHENG Z， et al. Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2012， 85（1 Pt 2）： 016106.

[21]原志强，赵春艳.两种改进的模拟退火算法求解大值域约束足问题[J].计算机应用研究，2017，34（12）：3611-3616.（YUAN Z Q， ZHAO C Y. Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains [J]. Application Research of Computers， 2017， 34（12）： 3611-3616.）

[22]吳拨荣，赵春艳，原志强.置信传播和模拟退火相结合求解约束满足问题[J].计算机应用研究，2019，36（5）：1297-1301.（WU B R， ZHAO C Y， YUAN Z Q. Combining belief propagation and simulated annealing to solve random satisfaction problems [J]. Application Research of Computers， 2019， 36（5）： 1297-1301.）

[23]CAI S， SU K L， SATTAR A， et al. Local search with edge weighting and configuration checking heuristics for minimum vertex cover [J]. Artificial Intelligence， 2011， 175（9/10）： 1672-1696.

This work is partially supported by the National Natural Science Foundation of China （11301339）， the National Natural Science Foundation of China — International （Regional） Cooperation and Exchange Program （11491240108）.

LI Feilong， born in 1994， M. S. candidate， His research interests include computational theory and computational complexity.

ZHAO Chunyan， born in 1982， Ph. D.， lecturer. Her research interests include non-deterministic polynomial-complete problem， computational theory and computational complexity.

FAN Rumeng， born in 1995， M. S. candidate. Her research interests include computational theory and computational complexity.

收稿日期：2019-05-16;修回日期：2019-07-08;录用日期：2019-07-17。

基金项目：国家自然科学基金资助项目（11301339）;国家自然科学基金国际 （地区）合作与交流项目（11491240108）。

作者简介：李飞龙（1994—），男，安徽阜阳人，硕士研究生，主要研究方向：计算理论与计算复杂性; 赵春艳（1982—），女，河南焦作人，讲师，博士，主要研究方向：NP-完全问题、计算理论与计算复杂性; 范如梦（1995—），女，河南驻马店人，硕士研究生，主要研究方向：计算理论与计算复杂性。

文章编号：1001-9081（2019）12-3584-06 DOI：10.11772/j.issn.1001-9081.2019050834