大数据

当前位置:首页 > 大数据

《算法导论》第三十四章(续2)

   《算法导论》第三十四章(续)

34.2多项式时间的验证

现在来看看对语言成员进行“验证”的算法。例如,假定对判定问题PATH的一个给定实例《G,u,v,k),同时也给定了一条从u到v的路径p。我们可以很容易地检查p是否在图G中以及p的长度是否至多为k。如果是,就可以把p看做是该实例确属于PATH的“证书”。对于判定问题PATH来说,这一证书看似并没有使我们得益多少。但无论如何,PATH属于P,事实上,PATH可以在线性时间内求解,因此,根据指定的证书来验证成员所需的时间与从头开始解决问题的时间一样长。现在来考虑这样一个问题:我们已知此问题没有多项式时间的判定算法,但是对于指定的证书,验证却是比较容易的。

哈密顿回路

在无向图中找出哈密顿回路这一问题已被研究100多年了。形式化地说,无向图G(V,E)中的一条哈密顿回路是通过V中每个顶点的简单回路。具有这种回路的图称为哈密顿图,否则称为非哈密顿图。这一名字是为了纪念W.R. Hamiltonian,他曾经描述过这样-个在正十二面体上的数学游戏°:(图34-2(a))一个游戏者在任意5个连续顶点上钉上5个图钉,另一个游戏者必须完成一个包含所有顶点的回路。正十二面体是哈密顿图,图34-2(a)显示一条哈密顿回路。但是,并不是所有的图都是哈密顿图。例如,图34-2(b)显示了一个具有奇数个顶点的二分图。练习34.2-2中将要求读者证明所有这样的图都是非哈密顿图。

《算法导论》第三十四章(续)

图34-2 (a)一个表示正十二面体中顶点、边、面的图,其中哈密顿回路以阴影边示出。

(b)一个包含奇数个顶点的二分图。任何这样的图都是非哈密顿图

我们可以用下列形式语言定义哈密顿回路问题:“图G中是否具有一条哈密顿回路?”

HAM-CYCLE- {〈G>:G是哈密顿图}

那么如何用算法来判定语言HAM-CYCLE。给定一个问题实例(G),一种可能的判定算法就是罗列出G的顶点的所有排列,然后对每一种排列进行检查,以确定它是否是一条哈密顿回路。那么,该算法的运行时间是多少呢?如果我们使用“合理的”方式把图编码为其邻接矩阵,图中顶点数m为Q(vn),其中n=|G|为G的编码长度,则总共会有m!种可能的顶点排列,因此,算法的运行时间为Q(m!)=Q(√n!)=Q(2),而不是O(r*)(k为任意常数)。因此,这种朴素算法的运行时间不是多项式时间的。事实上,哈密顿问题是NP完全问题,我们将在34.5节中进一步证明这一结论。

验证算法

现在来考虑一个稍为容易一些的问题。假设有人说某给定图G是哈密顿图,并提出可以通过给出沿着此哈密顿回路排列的顶点来证明他的话。证明当然是非常容易的:仅仅需要检查所提供的回路是否是V中顶点的一个排列,以及沿回路的每条连续的边是否确实在图中存在。这样就可以验证给定的回路是否是哈密顿回路。当然,该验证算法可以在O(n')时间内实现,其中n是G的编码的长度。因此,我们可以在多项式时间内验证图中存在一条哈密顿回路。

我们定义验证算法为含两个自变量的算法A,其中一个自变量是普通输入串α,另一个是称为“证书”的二进制串y。如果存在一个证书y满足A(z,y)=1,则该含两个自变量的算法A验证了输入串x。由一个验证算法A所验证的语言是:

L= { ∈ {0,1}”:存在y ∈ {0,1}”,满足A(z,y)= 1}

从直观上来看,如果对任意串c∈L,都存在一个证书y,且算法A可以用y来证明: ∈L,则算法A就验证了语言L。此外,对任意串α(L,必然不存在一个能证明r∈L的证书。例如,在哈密顿回路问题中,证书是某一哈密顿回路中顶点的列表。如果一个图是哈密顿图,哈密顿回路本身就提供了足够的信息来验证这一事实。相反地,如果某个图不是哈密顿图,那么也不存在这样的顶点列表能使验证算法认为该图是哈密顿图,因为验证算法会仔细地检查该回路是否为哈密顿回路。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~