由sat问题展开说.docVIP

由SAT问题展开说 XML:namespace prefix = o ns = urn:schemas-microsoft-com:Office:office / 作者： 李连华 崔涛 摘要：本文试图以活泼的笔调，讨论一个计算机科学难题，SAT问题。并由此展开，展示计算机算法的魅力，与计算机算法分析和设计的一些基本思想。最后，给出一个SAT问题的演化计算的算法和程序实现。 关键字：SAT问题，组合爆炸，爬山法，A算法，演化计算 由SAT问题展开说（1） 序言 计算机是一门科学。科学离不开问题；计算机科学也面临着一大批问题，尤其以NPC问题称著。它们目前都没有得到很好的解决。如果你仔细审视它们，就会发现科学发展的急迫与艰难，及美好。 在众多NPC问题中，有一个问题被称为其它问题的“种子”，那就是SAT问题。SAT问题是Cook提出的著名计算机科学难题，依据 Cook’s Theorem SATIsfIBILITY is NP-complete, SAT问题是一类问题的难度标准，所以又可称为NPC问题的种子。 我们不证明Cook定理（见注释1），叙述SAT问题如下。 问题的叙述 SAT问题或称为可满足性问题，我们要了解它，先看一些概念。 句子：为有限个逻辑变量（或其非?）的或（∨）式，例如句子 C1=x1 ∨?x2 ∨x3 ∨ ?x4， 每一个逻辑变量可取值为真或假，分别用1和0表示。则对于一个句子的值，可用逻辑变量的一组指派来求得。例如x1 、x2 、x3 、x4的一个指派为：0001，则C1的值为1（真），该指派为成真指派。 对于逻辑变量的集合 A={ x1,x2,…,xn },所形成的有限句子集合为F={ c1,c2,…,cm }。如何判断是否有一个A上的指派，使得F中所有句子皆为真？则这就是SAT问题。例如 F1={ (x1 ∨x2 ∨x3),(?x1∨x2),(?x2∨x3), (?x3∨x1),(?x1 ∨?x2∨ ?x3) }， 可以证明F1是不可满足的。 但对于一个一般性的集合F，就不是那么容易判断了。 问题的初步分析 不妨设逻辑变量的集合A={ x1,x2,…,xn }，即 |A|=n ，有限句子集合为F={ c1,c2,…,cm }，即 |F|=m。我们来讨论如何用计算机算法来解决这个问题。关于算法，这里须是有限时间停机的（见注释2） 。 这是一个有数理逻辑背景的问题，问题解空间的描述形式，使用长度为n的0/1串的集合是十分自然的。设这个集合为Ω，则若 s∈Ω，就有s是长度为n的0/1串，记作 s=（0|1）^n 。 显然我们要判断能否找出一个s*∈Ω，其中s*是F的成真指派。 集合Ω并不是无穷集，显然有|Ω|=2^n 。如果使用穷举法，是可解的，但算法的时间效率是O（2^n），指数级增长的，这个规模使得我们的计算机无法承担问题规模增长所带来的消耗。如此大的有哪些信誉好的足球投注网站空间，计算机在可等待的时间里算不完了，产生了组合爆炸问题。如下图： ASPectratio=t 2003-8-261022020.gif align=baseline border=0 这种有哪些信誉好的足球投注网站路径，只怕未至问题的解，大家都不知“今昔是何年”了。我们该如何办呢？如何才能得到尽可能快的有哪些信誉好的足球投注网站路径，接近我们的问题的解呢？ 依据直觉，我们需要某种限制，使得我们的有哪些信誉好的足球投注网站活动在一个较小的空间里接近问题的解，而走一个较直的有哪些信誉好的足球投注网站路径。当然，最好是直线走到问题的解，甚至一下子跳到目标那里，可是你我都知道，多数时候是办不到的。一般的，我们希望能如此： 可是，这个有哪些信誉好的足球投注网站的限制，对于每个问题，如何找到？图1和图2中我们还给出两个参数α（n）和β（n），都是关于问题的规模n的函数，分别表示解空间增长的速度和有哪些信誉好的足球投注网站限制的好坏，一般的，都不象是图中的边界那样为线性的。 这是本文的核心问题。我们以SAT问题为例展开，一起来领略计算机算法世界的神奇与艰辛。 问题的进一步分析 虽然SAT问题有数理逻辑的背景，可是数学模型也完全可以用图来描述。想一下，每个指派s都可视为一个状态，作为图中的结点。则集合Ω就是图中的结点集。考虑到集合Ω的势，我们可想象出这个图，而不全部画出它，如： 至于边，则可以自己因方便定义。 例如，在超立方体网络中，相临的结点的编码（0/1串）都是只有一位相异的，路由可以很方便的选择的算法为e立方体路由算法，受其启发，我们可以定义图中边（Ri，Rj）存在当且仅当Ri与Rj的编码只有一位不同。等等。 不论如何定义边，我们都可以方便的想到，我们的算法，都是由某个（些）结点出发，走一条尽可能短的路径，达到某个（些）特殊的结点----问题的解！ 在这个数学模型上，有些措施在有哪些信誉好的足球投注网站解时是可以方便的加以利用的，如深度优先有哪些信誉好的足球投注网站