算法设计与分析王晓东

8 9 4 7 6 5

则初始状态用向量S0=（8，1，2，3，4，5，7，0，6）表示，目标状态用S*=（1，2，3，4，5，6，7，8，0）表示。

我们使用一个堆heap, 将启发函数值H(x)最小的状态x置于堆顶优先搜索。H(x)定义如下： H(x)=h1(x)+3h2(x)

其中，h1(x)为状态x与目标状态不相同的数字的数目，h2（x)= y=e ∑N(y) ， 这里，

N(y)=0,y和其后继的相对位置不变 N(y)=1,y处于中心 N(y)=2,q其他 算法：

Algorithm LC(S0, S*)

Input: 初始状态向量S0 , 目标状态S*； Output: 达到目标状态的状态序列； Begin S=S0;

if S目标状态S* then Output(S及其所有前驱) else add (S, heap) while heap非空 do 取出堆heap顶部状态E ； for E 的每个可能的后继状态x do

if x为目标状态S* then Output(x及其所有前驱); return else

计算x的启发函数H(x); add(x, heap) endif endfor endwhile end

第八章 NP完全问题

习题8-1 证明析取范式的可满足性问题属于P类。 分析与解答：

析取范式α是由因子之和的和式给出的。这里因子是指变量x或x拔 ，每个因子之积称为一个析取式。例如 x1x2+x2x3+ x3就是一个析取范式。

设给定一个析取范式α= i=1 ∑ m fi(x1,x2,x3,...,xn)，其中fi(x1,x2,..,xn) 是变量xj 或xj拔 ，j=1~n的一个析取范式，i=1~m。α是可满足的，当且仅当存在i, 1≤i≤m ，使fi(x1,x2,..,xn) 是可满足的。如果有一个多项式时间算法能判断任何一个析取式的可满足性，则用该算法对α的每个析取项逐一判断就可以在多项式时间内确定析取范式α的可满足性。因此，问题可简化为找一个确定析取式可满足性的多项式时间算法。

设析取范式f(x1,x2,..,xn) =α1α2..αk ，其中αi∈{xj,｜1≤j≤n} 。

可以设计在O(n+k)时间内确定析取式f(x1,x2,..,xn)=α1α2...αn可满足性的算法。因此，析取范式的可满足性问题是多项式时间可解的，即它属于P类。