重置字的概念[1]指的是具有以下特征的字母表上的符号序列：不论自动机当前处于什么状态，只要执行该重置字都可以使自动机进入某个特定状态．显然，重置字相当于重启命令，执行重置字相当于进行了一次热重启．它不仅在软件测试、抗错的压缩编码、生物计算、机器人等领域有一定应用，还与控制论、本原矩阵(primitive matrices)等理论有关[2]．目前国内对自动机重置问题的关注较少，主要是何勇团队[3-5]及笔者的工作[6-8]．本研究在梳理文献的基础上，介绍有关自动机重置问题的经典算法的进展，分析自动机重置问题的理论结果和算法(实验)间的联系．针对文献中的算法和实验，讨论求解重置字的方法，涉及到计算复杂性、算法流程、复杂度和优化策略等知识．根据求解目标不同，将这些算法分成判定有限自动机是否可重置的算法、求解短重置字的算法和求解最短重置字的算法三类，其中后两类算法分别为计算最短重置字的近似算法和精确算法．对各个算法背后的思想、复杂度、生产的重置字的质量和存在的问题等进行分析，总结了这些算法的评估标准和优化策略，给出了理论上须要进一步探讨的问题．1 有限自动机重置问题1.1　有限自动机和重置字对于集合X，|X|为X的基数，即X的大小．对于有限字母表Σ，Σ*为由Σ中的字母构成的所有有限字(序列)的集合．有限自动机(finite automaton)定义为五元组A=(Q,Σ,δ,qinit,F)，其中：Q为有限状态集；δ为变迁函数Q×Σ→Q；qinit∈Q为初始状态；F⊆Q为终止状态集．如果δ是完全函数，即∀q∈Q和∀a∈Σ，δ(q,a)均有定义，那么称这个自动机是完全自动机；如果∀q∈Q和∀a∈Σ，|δ(q,a)|≤1，那么称这个自动机是确定的自动机．没有特别说明，下文的自动机和有限自动机均指完全的确定的有限自动机，即∀q∈Q和∀a∈Σ，|δ(q,a)|=1，用n表示自动机的状态数．记δ(S,a):=∪q∈Sδ(q,a)，其中S⊆Q，a∈Σ．将δ扩展为δ:Q×Σ*→Q，具体定义如下δ(q,w):=q    (w=ε);δ(δ(q,a),w')    (w=aw'),式中：a∈Σ；w,w'∈Σ*；ε为空字．相应地，δ(S,w):=∪q∈Sδ(q,w)．对于自动机A=(Q,Σ,δ,qinit,F)，如果存在w∈Σ*使得∀q,q'∈Q，δ(q,w)=δ(q',w)，即δ(Q,w)=qw，其中qw∈Q，那么称w是A的重置字(或同步字)，A是可重置的(或可同步的)．考虑自动机的重置时，由于不必考虑qinit和F，因此将自动机记为三元组A=(Q,Σ,δ)，它的最短重置字称为重置阈值．对于自动机A=(Q,Σ,δ)，如果存在状态q∈Q使得∀a∈Σ有δ(q,a)=q，那么称q是A的吸收状态．有限自动机和重置字的例子可参考文献[2]．讨论重置问题的算法会涉及幂集自动机和对自动机．对于自动机A=(Q,Σ,δ)，其幂集自动机(power-set automaton)定义为𝒫(A)=(2Q,Σ,Δ)，其中2Q为{P⊆Q}\{∅}，变迁函数Δ:2Q×Σ→2Q定义为Δ(q,l):=∪s∈q{δ(s,l):∀q∈2Q,l∈Σ}，其中s为状态集q中的状态．对于自动机A=(Q,Σ,δ)，其对自动机(pair automaton)定义为A2=(Q',Σ,δ')，其中Q'为{{p,q}:p,q∈Q,p≠q}⋃{q0}，不区分{p,q}和{q,p}．变迁函数δ':Q'×Σ→Q'定义为∀a∈Σ',δ'({p,q},a):={δ(p,a),δ(q,a)}和δ'(q0,a):=q0．类似δ，Δ和δ'可分别扩展到2Q×Σ*→2Q和Q'×Σ*→Q'．有限自动机的幂集自动机和对自动机的例子可分别参考文献[2]和[9]．1.2　重置问题的形式定义和复杂性讨论自动机的重置问题时以判定问题为主，实际应用中搜索(计算)问题居多．对于自动机A=(Q,Σ,δ)，定义以下四个判定问题，稍微修改可得到对应的搜索问题．基本问题：A是否是可重置的，即是否存在w∈Σ*是A的重置字．限界问题：对于自动机A和正整数l∈Z+，是否存在满足|w|≤l的w∈Σ*是A的重置字．最优问题：对于自动机A和正整数l∈Z+，是否存在满足|w|=l的w∈Σ*是A的最短重置字(最优问题可以看成是两个限界问题的组合)．近似问题：对于自动机A和近似比r，是否存在近似比不超过r的关于n的多项式时间算法．有关近似比、近似难度的知识参考文献[10]．表1给出了四个问题的计算复杂性结论和对应文献．须要说明的是，基本问题是NL-完全的，但未找到证明此结论的文献．有关它们的参数复杂性结论参考文献[11-12]，本研究不就复杂性方面的结论展开讨论，但这些结论对于更好地理解问题求解的难度(对资源的消耗)很重要．10.13245/j.hust.210202.T001表1关于有限自动机重置问题的计算复杂度问题复杂度基本问题[13]限界问题[14]最优问题[15]近似问题[16]有O(n2)上界NP-完全的DP-完全的在某个近似比之内计算，是NP-难的另外要指出，Černý猜想[1]宣称自动机的重置阈值不超过(n-1)2，虽然尚未得到证明，但许多自动机的子类已经证明了其正确性．目前已知的重置阈值的最小上界是114n3/685+O(n2)[17]．2 2008年前重置问题的算法概况对于判定自动机是否可重置的基本问题及求解重置字的计算问题，Natarajan算法[13]和Eppstein的GREEDY算法[14]都是多项式时间的．Natarajan算法解决了从方向器零件的设计问题抽象出的有限集上的函数组合问题(可看成是自动机重置问题的另一种表达)，得到的函数组合(即重置字)长度为O(|Σ|n3)的GREEDY算法实际上是Natarajan算法的改进，将时间复杂度从O(|Σ|n4)降至O(n3+|Σ|n2)，该算法得到的重置字长度为O(n3)．Trahtman改进了Eppstein的工作，给出的CLYCLE算法虽然时间复杂度与GREEDY算法相同，但是在处理Černý型自动机时能够得到更短的重置字[18]．GREEDY算法和CLYCLE算法是很重要的两个算法，许多基于融合字构造并结合启发式策略的算法都是二者的衍生．算法的第一阶段中判定是否为可重置的自动机基于以下结论：自动机A是可重置的，当且仅当对每对状态p,q∈Q存在融合字v使得δ(p,v)=δ(q,v)[13]．可以搜索和保存每对状态的最短融合序列，如果存在无法融合的状态对，那么自动机不可重置．算法可在对自动机A2上具体实现，以集合{(q,q)|q∈Q}中的状态为起点，执行后向广度优先搜索(breadth first search，BFS）加以验证即可．由于A2的有向边数为|Σ|n2，因此这一阶段需要的时间为O(|Σ|n2)．Trahtman给出另一个检测自动机的可重置性的条件：如果强连通的自动机A是可重置的，那么q0是其对自动机A2中唯一的吸收状态[18]．算法的第二阶段将第一阶段中每一轮循环迭代找到的融合字连接起来形成重置字，同时更新活跃状态集(指每轮迭代中尚未融合的状态集，其初值为Q，终值为单点集)．由于在每一轮的迭代中挑选融合字时可采取不同的策略，因此可形成不同算法，其中GREEDY算法的策略是每轮迭代选择最短的融合字对应的两个状态融合，CLYCLE算法的策略是要求前一轮迭代的两个状态融合后的状态必须是后一轮待融合的两个状态中的一个．表2总结了上述算法的复杂度，其中z为自动机的吸收状态个数．空间复杂度是在不考虑保存输出的重置字时得出的，如须保存重置字还要O(n3)的存储空间．相比Natarajan算法，GREEDY算法将存储空间压缩至O(n2)，在文献[14]和[19]中有更详细描述．10.13245/j.hust.210202.T002表22008年前的若干算法的复杂度算法时间复杂度空间复杂度基本问题的算法[14]Natarajan算法[13]GREEDY算法[14]CYCLE算法[18]O(|Σ|n2)O(|Σ|n4)O(n3+|Σ|n2)O(n3+|Σ|n2)O(|Σ|n)O(n3)O(n2)O(max(n,z2))对于搜索版的最优问题，即计算最短重置字，主要有两个算法：a. 在幂集自动机A上执行简单的BFS，从状态Q∈2Q出发到达任何单点集的最短路径的逆序即为最短重置字[2]．该算法最坏情况下的运行时间为Ω(2n)，所需空间为Ω(2nn)[20]，不是一个实用算法；b. Trahtman给出的SEMIGROUP算法[21]利用句法半群的概念，时间复杂度为O(|Σ|ns2)，空间复杂度为O(ns)，其中s为句法半群S的大小．该算法略好于幂集自动机上的BFS算法，已在著名的同步包TESTAS[22]中采用．3 求解基本问题的算法进展对于基本问题存在O(|Σ|n2)时间的算法，Berlinkov证明了含n个状态且字母表大小超过1的随机自动机以高概率可重置[23]．在此基础上证明了自动机重置的基本问题存在平均时间复杂度为O(|Σ|n)的算法[24]．Berlikovd的算法虽然在最坏情况下的时间复杂度仍为二次函数，但极大提高了原算法的性能．Ageev在实现Berlinkov算法过程中做了少量修改，通过实验验证了算法运行时间与n的线性关系，还指出当n31时算法的平均时间相比原二次多项式时间算法有极大改善[25]．可分析出Ageev的算法实现仍需O(|Σ|n)的存储空间．Berlinkov采用的概率模型虽是最简单的均匀分布模型，但是首次就自动机重置问题加入了对输入样本空间的概率分布的考虑，也是首次从理论上证明了存在更快的判定可重置性的算法．目前分析自动机这类复杂模型的概率性质较难，现有的分析工具主要是随机图(random graph)理论[26]．4 求解短重置字的算法进展4.1　基于构造短重置字的算法Natarajan算法、GREEDY算法和CLYCLE算法不一定得到最短重置字．但人们总希望在多项式时间内找到尽可能短的重置字．在这之后对基于构造重置字的算法改进主要是在第二阶段，即在选择和拼接融合字的过程中选择不同的启发式策略．这些算法的复杂度见表3，其中SYNCHROP(L)表示SYNCHROP和SYNCHROPL两个算法．10.13245/j.hust.210202.T003表3结合启发式策略的算法的复杂度算法时间复杂度空间复杂度SYNCHROP(L)[27]FASTSYNCHRO[20]优化SYNCHROP(L)[28]优化GREEDY/CYCLE[29]O(n5+|Σ|n2) O(|Σ|n4)O(n5+|Σ|n2)O(n3+|Σ|n2)O(n2)O(n2)O(n2)O(n3)Roman给出的SYNCHROP和SYNCHROPL算法不同于GREEY和CYCLE算法[27]，其启发式策略会前瞻一步，即每轮迭代都会去检查候选的某对状态p,q∈Q的融合字v对下一轮活跃状态集分布的潜在影响，评估所有可能的潜在活跃状态的分布是当前这一轮选择融合字的关键．SYNCHROP算法和SYNCHROPL算法都是五次多项式时间算法，但优势在于给出的重置字长度要比GREEDY算法和CLYCLE算法的短得多．分析得出：相比GREEDY算法，SYNCHROP(L)算法计算新的启发式策略还需大小为O(n2)的表格来保存中间结果，用于后续计算的查询，于是算法实现的存储空间需求为O(n2)．FASTSYNCHRO算法[20]改进了SYNCHROP算法，保持了解的质量，同时降低了时间复杂度．FASTSYNCHRO算法不再考虑状态对的融合字上的评估函数，而是对自动机A的所有可能的输入符号计算评估函数，选择函数值最小的字母作为下一轮的动作．此外，为确保最终找到一个重置字，同时降低平均运行时间，FASTSYNCHRO算法还做了一些适当的调整和限制．文献[20]虽未指出算法的空间复杂度，但分析可得所需的存储空间仍为O(n2)．文献[28]加速了SYNCHROP这种解的质量较高的算法，具体改进措施是：a. 预先计算采用融合字更新活跃状态集的所有可能代价，减少部分冗余计算；b. 引入“懒惰”思想，将预先计算推迟到需要时再进行；c. 在某些条件下优化SYNCHROP算法在第一轮迭代中的计算量．文献[24]指出：相比SYNCHROP算法，优化算法需要O(min(K,n2)的额外存储空间，其中K=∑l=1k|Σ|l，算法具体实现时得K=O(n2)即可得表3中的O(n2)的空间复杂度．通过对随机产生的自动机进行实验，发现这些优化措施对于比较大的自动机更加有效．文献[29]在不牺牲获得的重置字质量的前提下，重新构造算法并加入若干优化措施提高了GREEDY算法和CYCLE算法的性能．具体改进措施是：a. 第一阶段以“懒惰”方式产生BFS森林；b. 适时地从其他状态对出发开始搜索，不再从BFS的边界出发；c. 降低检查状态对是否属于BFS森林这一操作的开销．文献[29]给出算法实现包含前瞻的启发式优化，消耗的存储空间为8m+2n+|Γ|，其中：m=n(n+1)/2；|Γ|为得到的重置字长．由于|Γ|=O(n3)，因此表3中给出的空间复杂度为O(n3)．4.2　基于构造短重置字的算法的并行化加速算法的并行化加速是指将算法与当前多核/众核的硬件平台深度融合，利用基于多核CPU和GPU的程序库改造串行算法使之达到并行化．文献[9]和[30]以经典的GREEDY算法为对象进行了并行化尝试．首先通过分析大量的随机自动机的实验数据，得出其在第一阶段耗时占整个算法耗时的90%以上，重点并行化改造了第一阶段，设计了前向和后向搜索混合的多线程搜索算法．文献[30]报告了利用现代处理器的多核架构在OpenMP库上实现的算法及实验，发现在字母表大小为128和状态数为4 000的自动机上，当线程数设置为16时，达到150倍的提速．文献[9]在文献[30]的基础上考虑了面向GPU的并行化改造，对状态对的最小融合字搜索算法在GPU上进行了并行化．使用NVidia公司的CUDA程序库实现整个算法，通过实验发现：对于大的自动机输入实例，采用GPU并行化的算法性能比采用多核CPU并行化的算法性能要好．文献[9]和[30]未讨论并行算法的存储空间，由串行GREEDY算法的空间复杂性、多核CPU和GPU的体系结构可得出其空间复杂性的保守估计为O(n3)．还须指出的是，对于这些多项式时间的重置算法的并行化，在复杂性理论研究层面应考虑问题的线路复杂性(circuit complexity)[31]，特别是证明某些问题是否属于NC类(NC类为刻画并行计算机能够有效求解的问题类)，但目前这方面的研究较少．4.3　基于限长参数的搜索算法4.3.1　BFS算法SynchroP，SynchroPL和FastSynchro算法在选择启发式策略时会前瞻一步或多步．每一步不像GREEDY算法那样挑选最短的融合字，而是取一对状态所对应的融合字v，使得对活跃状态集P的更新操作δ(P,v)在某种意义上最优，这种“最优”以某种权重函数f：𝒲(Q)→R的形式给出，其中𝒲(∙)是选择的融合字．以权重评估值来引导搜索是非常有效的，文献[32]将它和幂集自动机上的BFS算法结合设计了后向搜索算法(Cut-Off Inversal BFS)．后向搜索算法与传统的前向算法类似，只是将对后继的计算改为对前驱的计算．Cut-Off Inversal BFS算法的输入为自动机A=(Q,Σ,δ)，m1，m2，其中m1和m2分别为待搜索的重置字的最大长度限制和存储集合的最大数目限制．主要思想是在幂集自动机上执行逆向的BFS算法，同时保持每一轮处理的集合列表不能太大．算法从包含所有单点集{q}的列表开始，搜索到集合Q时终止．当实际存储的列表大小超过m2时，忽略含有最小权重的列表中的集合．由于剪枝的算法不一定能得到重置字，为保证得到重置字，在执行后向算法之前采用了前向算法，那么前向算法所发现的重置字的长度可用作m1的长度限制搜索，Cut-Off Inversal BFS会找到一个更短的字．算法的时间复杂度为O(lc|Σ|n)，空间复杂度为O(c|Σ|n)，其中：l≤m1，c=m2．为减少存储开销，引入堆来维护优先级队列，使位于堆的顶层的集合具有最大权重，改进后的算法空间复杂度为O(cn)．实验得出：当考虑时间、空间使用、解的质量和最优性的平衡时，后向搜索算法是最好选择，尽管比GREEDY算法慢，但能求解出更短的重置字．当自动机的状态数n为100～300之间时，超过90%的随机自动机实例中后向算法得到了最短的重置字．4.3.2　利用SAT求解的算法类似于限界模型检测，利用可满足性(satisfiability，SAT)求解的方法是将自动机的变迁在一定范围内展开为合取范式(conjunctive normal form，CNF)的公式形式，将初始状态和可重置条件也设计为CNF公式，交给SAT求解器求解．由于最短重置字的最小值有O(n3)的界，因此可设重置字长度的参数l=n3/6．该方法更多地出现在非确定的有限自动机和部分归约的确定的有限自动机的重置字求解上．须注意的是，限长的有限自动机的重置问题到SAT的归约是多项式时间归约，两个问题都是NP-难的，而其他类型的自动机在考虑以字长为参数时，存在到SAT的固定参数易解的(fixed parameterized tractable，fpt)归约，这就限制了SAT公式的大小为n的多项式．最早的代表性工作是Skvortsov等的[33]，其他工作(比如文献[8])均在此基础上做了适当修改或扩充．这种方法本质上也是搜索．4.4　基因算法基因算法本质上是基于随机搜索的算法．最早研究自动机重置问题的基因算法是Roman[34]，在经典的“简单基因算法”框架下设计和实现求解短重置字的基因算法，用染色体表示字，基因表示字母．初始种群设置时，基因中字母的出现概率考虑了与其底层图(某字母对应的底层图是指删除了其他字母标记的边后形成的子图)的强连通分量有关的因素和占比，字长则利用了以下经验：对于大部分可重置的自动机，其重置字的长度很可能在2n范围内．算法执行中考虑了字母出现概率的适应性分布，设计了(单点)交叉和三种变异操作，定义了适应性函数．实验发现：该算法的收敛性在随机自动机上表现良好，但在一些“同步困难”的自动机上，收敛性随自动机状态数的增长而降低，出现了失败的情况．文献[35]研究了自动机重置问题的新演化算法，采用的是“可能-不可能的双种群基因算法”框架．为挑选最好的算子组合方式，实验中将基于搜索的最短重置字求解算法[36]、Cut-Off Inversal BFS算法及GREEDY算法进行了对比．得出的结论是该基因算法的伸缩性好，通过定义种群大小和退出标准控制内存用量和运行时间，但在大自动机上结果比Cut-Off Inversal BFS算法差，相比文献[34]，算法在一般情况下要好一些，更合适于小的自动机和“同步困难”的自动机．5 求解最短重置字的算法进展5.1　基于搜索的最短重置字求解算法文献[36-37]提出的算法是目前已知的最好的最短重置字求解算法．算法在实验过程中可处理n=350，|Σ|=10的自动机，证实了面对大自动机时的实用性．其主要思想是用双向广度优先搜索和radix trie树的数据结构保存和对比集合．算法利用前述判定算法(如GREEDY算法的第一阶段)判断自动机是否可重置．如果是可重置的，那么算法将在对应的幂集自动机上执行BFS搜索，可从包含所有状态的集合Q开始搜索，通过枚举字母表Σ的字母逐个计算后继，也可采用后向BFS搜索，即从单点集开始，计算结点的前驱．这两种搜索都具有|Σ|个分支，须计算O(|Σ|l)个集合，后向BFS搜索则须计算O(n|Σ|l)个集合以便找到最短长度为l的重置字．由于双向搜索的思想是同时执行两种搜索并且检查它们是否相遇，因此只用计算O(n|Σ|l/2)个集合就可以找到一个重置字．该高效算法成功的一个关键是估算前向搜索和后向搜索的执行时间以便决定采用哪种搜索策略，具体实现利用子集检查操作中已经访问过的结点的平均数量上界，近似估计了搜索的执行时间；另一个关键是利用radix trie树的数据结构高效地实现子集合的检查操作，即通过在这种树上执行深度优先搜索来检查给定的集合S⊆Q是否包含某个已经访问过叶子所代表的子集．通过在随机产生的自动机上实验，与SAT结合二分搜索的方法相比，执行时间更快，也优于传统的BFS搜索．文献[37]指出这是指数时间的算法，其空间复杂度为O(|Σ|n2)+min{O(n3),C}，其中C为有关内存限制的参数．5.2　SAT结合二分搜索的最短重置字求解算法在基于SAT的求解限长为l的重置字的算法中，当求解最短重置字时，可利用二分搜索策略，由于每次将长度增量折半形成新长度[33]，并转化出新的公式交给求解器查询，因此须要调用SAT求解器的次数为log l，其中对数函数log(⋅)的底数为2．5.3　近似算法的近似比界限求解短重置字的算法属于近似算法范畴．衡量重置字的质量时，会较多考虑短重置字与最短重置字的比值和算法的运行时间，希望该近似比接近1且具有多项式的运行时间．概率可验证明(probabilistically checkable proofs，PCP)定理[10]常用来证明某个NP-难问题在某个近似比内不存在有多项式时间算法．近年的工作主要有以下三个：a. 文献[38]证明了对任意给定的k≥2，最短重置字问题存在O(k|Σ|n4+n4/k)运行时间的近似比为(n-1)/(k-1)的算法；b. 文献[16]证明了对于每个常数ε0，在字母表大小为3的有限自动机上，近似比在n1-ε内近似计算最短重置字的多项式时间算法是不存在的，除非NP坍塌到P；c. 文献[39]提出的SYNCH-SUBSET(k)算法族概念含有关于子集选择和融合字选择的两个神谕(oracle)，分析了这类算法的近似比，其中Eppstein的GREEDY算法其实就是两个采用了贪心策略的神谕在k=2时的算法SYNCH-SUBSET(2)．文献[39]的主要结论是：当k3/n时，带有任意贪心策略的两个神谕的算法SYNCH-SUBSET(k)的近似比至少为n/(6(k-1))．对于启发式算法及其优化，目前尚无比较精确地分析这些算法近似比的工作．比如，Natarajan算法给出的重置字长为O(|Σ|n3)，假设Černý猜想的最短重置长有O(n2)的界，那么可看到算法的近似比为O(n)，类似可以分析GREEDY算法的近似比为n-1，与理论极限值有不小的差距．寻找有更佳的近似比的多项式时间算法一直是努力的方向．6 总结与讨论6.1　算法的空间复杂度和适用性由于空间可重复使用，因此空间复杂度的渐近函数大小不会超过时间复杂度的函数．并非所有的算法都进行了空间复杂度分析，对于有多项式时间的重置算法，其存储空间消耗会在O(n3)内．对于指数时间的算法，优化时为减少时间，存储空间的消耗会更多，比如文献[37]讨论了实际情况下当内存受限时的策略．在判定基本问题过程中，应采用Berlinkov的算法．一般当自动机的规模比较大时，不建议求最短重置字，可考虑多项式时间的重置算法；当自动机规模较小时，可根据需要任意选择．碰到“同步困难的”自动机时，可采取基因算法[35]．推荐基于SAT的方法[33]，因为可利用当前最先进的SAT工具的求解能力和标准接口，算法较容易实现且性能较好，方便扩展到更多类型的自动机上．6.2　算法的评估框架和基准测试集目前，对于自动机的重置问题，评价算法尚无统一的框架和基准测试集．主要考虑的是算法的性能(对时间和空间资源的消耗)和解的质量(长度、近似比和返回的是最短重置字的概率)；其次考虑算法的伸缩性(是否可以根据实际情况设置参数，如搜索的最大长度、内存限制等)．测试重置算法的正确性和性能时，一般会采用文献中出现过的实例(如“同步困难”的自动机)和基于均匀分布模型随机产生的自动机和工业中的有关电路的测试基准集(如文献[40-41])．进行算法的对照实验时，至少会以Eppstein的GREEDY贪心算法作为测试基准之一．6.3　算法的优化策略GREEDY算法采用最简单的启发式策略，寻找具有最短融合字的状态对融合．FASTSYNCHRO算法的启发式策略较复杂，对所有可能的输入符号计算其评估函数，选择函数值最小的字母作为下一轮的动作．双向BFS搜索算法引入对权重函数[32]的讨论．这些启发式策略考虑的因素是否全面及决策的好坏直接影响了搜索中下一轮迭代．当然，人们也希望启发式策略(权重评估函数)能够比较容易计算，比如要求是线性时间或不超过2次的多项式时间．最近在重置字求解的算法优化中出现了“懒惰策略”的应用，比如文献[28-29]．该策略包含“事情等到需要时再做，不需要的一定不要做”的哲学思想．文献[28]只预先计算那些须要计算的状态对的融合字的代价，不须要的不计算．文献[29]将算法在第一阶段须要提前准备的BFS森林初始化为只含根，当第二阶段须要使用时再逐渐构造出来．另一策略是采用混合型的双向搜索．文献[42]指出后向BFS可以极大地降低遍历时的边数，其优势在于：适合边界上包含了相当大的一部分结点的、具有低效直径的大连通分量的情况(比如小世界网络)．传统的BFS在搜索的开始和结束阶段表现较好，因为这时边界只占小部分结点．文献[9]、[30]和[36-37]的算法加速都采用了这种混合型的双向搜索策略，提高了算法性能．6.4　与算法理论有关的待研究问题自动机的重置问题本质上属于带标记图上的搜索问题，须进一步研究的理论问题有：a. 对于基本问题，回答二次的多项式时间是否为它的(有条件)紧致下界；b. 对于最优问题，回答是否存在亚指数时间的参数化算法；c. 对于最优问题，研究在某些分布上它的平均复杂性和相变现象．此外，可以将重置问题泛化到其他类型的自动机模型上．