算法分析与设计及案例习题解析

习 题 解 析

第1章

1. 解析：

算法主要是指求解问题的方法。计算机中的算法是求解问题的方法在计算机上的实现。 2. 解析：

算法的五大特征是确定性、有穷性、输入、输出和可行性。 3. 解析：

计算?n?的算法，其中n是正整数。可以取循环变量i的值从1开始，算i的平方，

??取平方值最接近且小于或者等于n的i即可。 4. 解析：

可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i，n=b*i，且a与b互质，这时m mod n=（a-x*b）*i，只需要证明b和a-x*b互质，假设二者不互质，可以推出a与b不互质，因此可以得到证明。 5. 解析：

自然语言描述：十进制整数转换为二进制整数采用“除2取余，逆序排列”法。 具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

流程图：如图*.1

开始输入n长度len=(logn/log2)len>=0Y输出(n>>len)&1)len=len-1N结束

图*.1 十进制整数转换成二进制整数流程图

6. 解析：

a.如果线性表是数组，则可以进行随机查找。由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。

b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。 7. 解析：

本题主要是举例让大家了解算法的精确性。过程中不能有含糊不清或者二义性的步骤。大家根据可行的方式总结一下阅读一本书的过程即可。 8. 解析：

数据结构中介绍的字典是一种抽象数据结构， 由一组键值对组成， 各个键值对的键各不相同， 程序可以将新的键值对添加到字典中， 或者基于键进行查找、更新或删除等操作。由于本题已知元素唯一，因此大家可以据此建立一个自己的字典结构。实现字典的方法有很多种：

? ? ?

最简单的就是使用链表或数组， 但是这种方式只适用于元素个数不多的情况下； 要兼顾高效和简单性，可以使用哈希表；

如果追求更为稳定的性能特征， 并且希望高效地实现排序操作的话， 则可以使用更为复杂的平衡树。

在字典之上的主要操作可以有：创建操作，添加操作，删除操作，查找操作，以及必要的字典维护操作。

第2章

1. 解析：

根据本章所述，递归算法和非递归算法的数学分析方法分为5个步骤。 2. 解析：

本题相当于对多项式找“主项”，也就是在除去常系数外，影响函数值递增速度最快的项。

a)

3n2?10n??(n2)

n2?2n??(2n) b)

10c) d)

121???(c)，c为常数

nlog2n3??(logn)

e) 10log3n??(n) 3. 解析：

本题中如果手套分左右手，则最优情况选2只，最差情况选12只。 本题中如果手套不分左右手，则最优情况仍然选2只，最差情况选4只。

从本题的初衷推测设置题目应该是分左右手的手套，在考虑颜色的情况下，选择一双进行匹配。 4. 解析：

本题的一般解法可以使用高等数学中求二者比值的极限来确定结果。 a) 相同 b) 第一个小 c) 二者相同 d) 第一个大 e) 二者相同 f) 第一个小 5. 解析：

a) x(n)?x(n?1)?5?5n?5 b) x(n)?3x(n?1)?4*3c) x(n)?x(n?1)?n?n?1 n*(n?1) 2d) x(n)?x(n)?n?2n?1 26. 解析：

参见本章例2.7。

第3章

1. 解析：

蛮力法主要依靠问题的定义，采用简单直接的求解方法。由此决定了蛮力法是解决问题的最简单也是最普遍的算法，同时其经常作为简单问题求解的方法和衡量其他算法的依据。 2. 解析：

2，6，1，4，5，3，2

选择排序： |2 1 1 1 1 1 1

6 |6 2 2 2 2 2

1 2 |6 2 2 2 2

4 4 4 |4 3 3 3

5 5 5 5 |5 4 4

3 3 3 3 4 |5 5

2 2 2 6 6 6 |6

i=0: min最后得2，交换二者。 i=1: min最后得2，交换二者。 i=2: min最后得6，交换二者。 i=3: min最后得5，交换二者。 i=4: min最后得5，交换二者 i=5: min最后得5。 结束。

冒泡排序： 2 2 1 1 1 1 1

6 1 2 2 2 2 |2

1 4 4 3 2 |2 2

4 5 3 2 |3 3 3

5 3 2 |4 4 4 4

3 2 |5 5 5 5 5

2 |6 6 6 6 6 6

i=0: 最大值6就位。 i=1：第二大值5就位。 i=2：第三大值4就位。 i=3：第四大值3就位。 i=4：第五大值2就位。

i=5：第六大值2就位，剩余的1也就位，排序结束。

3. 解析：

选择排序不稳定，如3.1.1节例子：4,4,2。冒泡排序稳定。

4. 解析：

如2题例子，到i=4时就没有发生交换的活动了。这时可以在冒泡排序的交换部分加入一个布尔变量，如本次循环中没有发生交换，则以后的扫描就可以不进行。 5. 解析：

如果n个点共线，则其最近对只需要考察相邻的点对，因此在对点进行按行坐标排序后，只需要两两计算相邻两点距离，就可以找到最近对。 6. 解析：

所有的过程与寻找二维空间中的最近点对类似，只是计算距离的公式变为： sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z)

使用循环计算任意两个点之间的距离，然后记录最小值即可。

类似的，如果推广到n维空间，需要考虑空间中任意两点的距离计算公式，同样计算每两个点之间的距离，并记录最小距离即可。 7. 解析：

a) 线段的凸包为本身，极点为两个端点。 b) 正方形的凸包为本身，极点为四个顶点。

c) 正方形的边界不是凸包，凸包为正方形（包括边界和内部）。 d) 直线的凸包为本身，没有极点。 8. 解析：

哈密顿回路的穷举查找算法，首选选择起点（图中任意一个点开始），之后不断寻找下一个点，下一个点应该满足：

1) 不在已经走过的点中； 2) 与上一个点有直连路径。

如果这样能找到回到起点的路径，并且遍历所有点，则为一条哈密顿回路。然后依次进行下一个可行点的选择。 9. 解析：

生成给定元素的一个排列，通过连续比较它们之间的元素，检查它们是否符合排序的要求。如果符合就停止，否则重新生成新的排列。

最差情况生成排列的个数是n!，每趟连续元素比较次数为n-1次。所以效率类型为

O(n!*(n?1))。

};

};

}; else { };

t=k-1; k=??s?t?; ??2?if(A[k]

for(j=i-1; j>=k; j--)

A[j+1] = A[j];

A[k] = v;

｝；

最差效率为：?(nlogn)。 5. 解析：

用减一法进行拓扑排序，每次删除入度为0的结点即可，所有可能情况共有7种： d-a-b-c-g-e-f；d-a-b-c-g-f-e；d-a-b-g-c-e-f； d-a-b-g-c-f-e；d-a-c-b-g-e-f；d-a-c-b-g-f-e； d-a-b-g-e-c-f。

同样，可以用深度优先遍历时，出栈顺序的逆序作为拓扑排序。 6．解析：

字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。它的整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345，然后12354，然后12435，12453....逐渐地从后往前递增。

看看算法描述：

首先，将待排序列变成有序（升序）序列。然后，从后向前寻找，找到相邻的两个元素，TiTi(很多时候k=j)，找到它，交换Ti跟Tk，并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij。 例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下： 自右至左找出排列中第一个比右边数字小的数字4 839647521 在该数字后的数字中找出比4大的数中最小的一个5 839647521 将5与4交换 839657421 将7421倒转 839651247 所以839647521的下一个排列是839651247。 839651247的下一个排列是839651274。 以下是C语言的代码： #include #define MAX 1000 int n=4; int set[MAX]={1,2,3,4}; int flag=0; //swap a and b void swap(int *a,int *b) { int temp=*a; *a=*b; *b=temp; }

//reverse a range of a set void reverse(int start,int end) {

int index_r=0; int new_end=end-start;

for(index_r=0;index_r<=new_end/2;index_r++)

swap(&set[index_r+start],&set[new_end-index_r+start]); }

void set_print() {

int index;

for(index=0;index

//find out all of the permutation in the set with first element 1 to n. void find_next() {

set_print();

int index_i,index_j,index_k; flag=0;

for(index_i=n-2;index_i>0;index_i--) if(set[index_i]

index_j=index_i+1; flag=1;

break; } if(flag==0) return ; for(index_k=n-1;index_k>0;index_k--) if(set[index_k]>set[index_i]) break; swap(&set[index_i],&set[index_k]); reverse(index_j,n-1); find_next(); } int main() { int count=1; int i=n-1; while(i>=0) { set[0]=count++; find_next(); swap(&set[0],&set[i]); reverse(1,n-1); i--; } return 0; } 7. 解析：

说到汉诺塔问题，首先想到的是最经典的递归解法。

在求格雷码的方法中，提到可以观察格雷码每一次改变的位数和汉诺塔每次移动的盘子的编号，从而产生一种不需要递归和堆栈的汉诺塔解法。 在生成格雷码的算法中，依次改变的位数是最低位和从右往左数第一个1所在位的左一位，对应汉诺塔的盘子就是最小的盘子和中间某个盘子。最小的盘子有两种可能的移动方案，其他的盘子只有一种可能。对于最小盘子移动到的柱子的解决方法是，根据观察，当盘子总数是奇数时，最小盘子的位置依次是“3->2->1->3->2->1...”；当总数是偶数时，这个顺序是“2->3->1->2->3->1...”。据此从格雷码到汉诺塔的一种对应解决方案就产生了。 如下是非递归方法的代码。 int main() {

char digit[MAX]; int position[MAX]; int i,j;

for(i = 0; i < MAX; i++){ digit[i] = '0'; position[i] = 1; }

int even = YES; int circle[3]; circle[2] = 1; if(n % 2 == 0){ circle[0] = 2; circle[1] = 3; } else{

circle[0] = 3; circle[1] = 2; } i = 0;

int m = 0; while(LOOP){ m++; if(m > 20) break; if(even){

cout<

FLIP_DIGIT(digit[0]); } else{

for(j = 0 ; j < n && digit[j]=='0'; j++) ; if(j == n-1){ break; }

FLIP_DIGIT(digit[j+1]);

cout<

FLIP(even); }

cout<<\ system(\ return 0; }

8. 解析：

n 52 26 13 6 3 1 9. 解析：

m 34 68 136 272 544 1088 1768 +136 +544+136 =1088+544+136 顺序查找的平均效率约为：Cavg(n)?n*(1?p)?最高效的排序算法其效率为：?(nlogn)。 p*(n?1)??(n)。 2因此，如果只做一次查找，不需要进行排序后再折半查找。 10. 解析：

构造2-3树的数据结构。之后建立插入节点和分裂的算法。

第6章

1. 解析：

以所经过的权值之和最大值为例进行说明。

行进的过程中，每次只有两种选择：向左或向右。一个有n层的数字三角形的完整路径有2n条，所以当n比较大的时候，搜索全部路径，从中找出最大值，效率较低。

采用动态规划方法实现。

用d(i,j)表示从位置(i,j)出发时得到的最大值（包括位置(i,j)本身），可以写出最大值的递归方程：

d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}

由于递归方程中包含了重复子问题，直接采用递归方程求解， 效率较低。采用动态规划的备忘录方法，用一张二维表记录中间过程的值，可以把时间效率提高到n2。 2. 解析：

采用动态规划方法实现。

用f[i]表示以ai为结尾的最长上升子序列的长度，可建立如下递归方程：

?1? f[i]??max{f[j]?1}1??j?i?]ai[]?a[j?i?1i?1

f[]是单调递增的，因为如果有i=f[j]，那么f[i]必定可以被f[j]的内容所更新。 每处理到一个ai，要找到一个k满足f[k–1]= ai，并用ai更新f[k]，最终max{k|f[k]!=∞}就是答案。

可以编写出时间复杂度为O(n2)的动态规划算法。 3. 解析：

用sum[i,j ] 表示将从第i 颗石子开始的接下来j 颗石子合并所得的分值。 用f [i,j ] 表示将第从第i 颗石子开始的接下来j 颗石子合并所得的重量的最小值。 有如下递归方程：

0?f[i,j]???min{f[i,k]?f[k?1,j]?sum(i,j)}可以编写出时间复杂度为O(n3)的动态规划算法。

i?j

i??k?j如果采用四边形不等式优化动态规划算法，可得到时间复杂度为O(n2)的动态规划算法，是一种比较高效的优化算法。 4. 解析：

按照动态规划求解多阶段决策的思路，每投资一个项目作为一个阶段，将原问题划分阶段，从而将静态模型转化为动态。用xk(k=1,2,3)表示第k个项目的投资额，其中用sk表示投资第k个项目前的资金数(k=1,2,3,4，k=4为虚设的阶段)，则有0≤xk≤sk 以及sk+1 = sk -xk 成立。用vk(sk, xk)表示在当前在资金数为sk，投资额为xk的情况下的投资效益值。为便于理解，如下图所示表示各阶段内容。

x1 s1 项目1 效益值 v1(s1,x1) s2 项目2 效益值 v2(s2, x2) 投资效益阶段表示图

根据以上分析，可写出求解问题的递归式和特殊值：

x2 s3 项目3 效益值 v3(s3, x3)

x3 s4 fk(xk)?max{vk(sk,xk)?fk?1(sk?1)}k?3,2,1

?sk?1?sk?xkxk?0,1,2,3,4(万元)?st.?f4(x4)?0?s1?4,s4?0?采用逆序倒推的方法，先计算在第三阶段，即投资项目3时的最大效益，再考虑第二阶段，即投资项目2时的最大效益，此时利用递归公式，其最大效益的获得是在所有在第二阶段的当前效益与第三阶段最大效益的累加和中求取最大值，同样方法获取第一阶段的最大效益。 5. 解析：

利用高斯公式，从1到n的自然数之和为：1+2+3……+n=n*(n+1)/2 。

题目要求：对于从1到N的连续整集合，划分为两个子集合，且保证每个集合的数字和是相等的。因而，划分之后每个子集全的数字应该为n*(n+1)/2的一半，即n*(n+1)/4由于两个子集中都是整数，所以n*(n+1)必为偶数，则可以设s=n*(n+1),并判断s%4 ，则，s/=4是划分之后子集合的数字和。

dyn[j]数组表示任意个数加起来等于j的组数， 则有下面公式成立：

dyn[j]= dyn[j]+dyn[j-i]; 其中dyn[j-i]表示加起来等于j-i的组数， 利用上述公式，可得到问题的解。 6. 解析：

按照样例输入：即3 4

2 -1 50 5 1 3 -1 6 -1 8 9 10

则表示迷宫如下：

a[i,j]保存第i行第j列的宝藏价值。令f[i,j]为从（1，1）走过第i行第j列时所能收集的宝藏的最大价值。有如下递归方程：

f[i,j]=max{f[i-1,j],f[i,j-1]}+a[i,j]i<=n,1<=m

同时满足：a[i,j]≠-1 初始 f[1,1]=a[1,1]

采用动态规划算法，利用递推公式构造并求解二维表f[i,j]，目标即求解出f[n,m]即可。 7. 解析：

按照样例输入如下：

5 6 4 4 3 4 4 5

a[i]表示第i首歌曲的长度。令f[i,j,k]表示前i首歌曲，用j张光盘，另加k分钟能够发行的最多歌曲树木。有如下递归方程：

f[i,j,k]=max{f[i-1,j,k]f[i-1,j,k-a[i]]+1//不刻录第i首歌//a[i]<=k:k分钟能够录制的歌曲if[i-1,j-1,t-a[i]]+1//(a[i]>k)and(j>=1)k分钟无法录制歌曲i但还有光盘可用} 采用动态规划算法，利用递推公式构造并求解二维表f[i,j,k]，目标即求解出f[n,m,0]或f[n,m-1,t]即可。 8. 解析：

按照样例输入如下：

ACDEF ABCDE

令f[i,j]为将A的前i个字符变成B的前j个字符所用的最少操作步数。 从后向前依次比较分析，f[i,j]有以下三种情况；

(1)删除A 中的前i-1 个字符中的最后一个字符，问题变为将A 中前i-1 个字符转换为B 中的前j 个字符，即：f[I,j]=f[i-1,j]+1;

(2)在A 的前i-1 个字符中的最后插入一个字符，插入后使a[i+1]=b[j]，问题变为将A 中的前i 个字符转换为B 中的前j-1 个字符，即：i[I,j]=f[i,j-1]+1;

(3)将A 中的一个字符转换为另一个字符。

如果a[i]=b[j]，则f[i,j]=f[i-1,j-1]

如果a[i]<>b[j]，将a[i] 换成b[j]；则f[i,j]=f[i-1,j-1]+1 综上所述，有如下递归方程：

第9章

1. 解析：

分枝限界法的基本思想是：宽度优先搜索（优先队列搜索）+剪枝。即，通过对搜索 树进行宽度优先搜索来寻找问题的解答，且在搜索中每搜索到一个结点处，都要考虑是否能 使用剪枝操作来剪枝，从而提高搜索效率。与回溯法相比，这种搜索方法具有更大的灵活性（搜索跳跃性更大），但是往往需要比回溯法多得多的空间。 2. 解析：

最优解为（110101），最优值为53，搜索空间树略 3. 解析：

解：K←1

X[1] ←1 , 返回 true

X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true

X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true 找到一个解 （1，2，3，3） 4. 解析：

a) 解向量的形式为（x1,x2,?，xn），其中 xi=1,2,3 表示图中第i个结点所着的颜色（1≤i≤n）。 搜索树为高度为n的满3叉树。

b) 剪枝操作如下：当搜索到结点 X=(x1,x2,?，xi )时，如果图中第i结点所着色xi与前1,2,?,i-1结点所作的颜色无冲突，即图中这些结点中与结点 i 有边相连的结点所着颜色都不是 xi， 则不剪枝，否则剪枝（即搜索跳过对子树 X 的搜索）。

c) 找到一个解所生成的部分搜索树如图 2 所示。所得解为 (1,2,3,2,1)。

5. 解析：

解：void backtrack (int i) {// 搜索第i层结点 if (i > n) // 到达叶结点 更新最优解bestx,bestw;return; r -= w[i];

if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; } 6. 解析：

斜线标识的部分完成的功能为：提前更新bestw值；这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。

为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。 7. 解析：

void compute() {

k=1;

while(!search(1,n)) {

k++;

if(k>maxdep) break; init(); };

if(found) output();

else cout<<”No Solution!”<

}

bool search(int dep,int n) {

If(dep>k) return false; for(int i=0;i<2;i++){ int n1=f(n,i);t[dep]=i; if(n1= =m||search(dep+1,n1)){ Found=true; Out(); return true; } return false; } 8. 解析：

a) 剪枝操作如下：当搜索到结点 X=(x1,x2,…，xi )时，如果 xi=1 且 x1+x2+…+xi >=M，则剪枝（即搜索跳过对子树X的搜索），否则不剪枝。

b)找到一个解所生成的部分搜索树如图所示。这个解为(1,0,1,0)。

9. 解析：

a) 解向量的形式为（x1,x2 , …，xn），其中xi=1,2,3 表示图中第 i 个结点所着的颜色（1≤i≤n）。当 n=3，k =3时搜索树为高度为3的满3叉树。

b) 剪枝操作如下：当搜索到结点X=(x1,x2, …，xi )时，如果图中第i结点所着色xi与前1,2, …,i-1结点所作的颜色无冲突，即图中这些结点中与结点i有边相连的结点所着颜色都不是 xi，则不剪枝，否则剪枝（即搜索跳过对子树X的搜索）。

c) 该算法的最坏时间复杂度是与搜索树中结点个数和在每个结点处花费的时间都有关。搜索树中结点个数为 O(kn)，而在搜索中每个结点处花费的时间为 O(n)，因此最坏时间复杂度是O(nkn)。 10. 解析：

a）由于解空间取为由 1,2,?,n 构成的n! 种排列所组成，所以表示解空间的搜索树为

高度 为 n 的排列树。

b）剪枝操作如下：当搜索到结点 X=(x1,?,xi)时，第 i 个皇后放在第xi列，此时需要对所有j (1≤j≤i-1)，要求|xi-xj |≠|i-j|。如果不成立，则剪枝。

c）该算法的最坏时间复杂度是与搜索树中结点个数和在每个结点处花费的时间都有关。搜索树中结点个数为 O(n!)，而在搜索中每个结点处花费的时间为 O(n)，因此最坏时间复杂度是 O(n n !)。 11. 解析：

应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。把每一个任务的最小代价相加，可以得到下界3+5+3+6=17。所以，目标函数的界为[17,21]。

限界函数为： lb?v?搜索空间如下：

k?i?1?第k行的最小值

n

第10章

1. 解析：

算法运行时间为O(nW)。这似乎是在多项式时间内解决了0-1背包问题，但是该算法 并非严格意义上的多项式时间算法。它的运行时间依赖背包载重量的大小。一个多项式 时间算法应该仅仅依赖于物品的数目，而不是他们本身重量或价值的大小。因此， DPKnapsack (I,W)算法是一个伪多项式时间算法。 2. 解析：

注意这里TSP 是判定问题，可以类似书上图着色问题及上题类似求解，略。

3. 解析：

考虑如下算法： RunSlow(n) 1 s←a

2 for i←1 to n do 3 s←Concatenate(s, s)

调用O(n)个子程序，每个花线性时间。第一次调用Concatenate(s, s)，连接两个a，花时间O(2n)， 第2次调用连接大小各为2的字符串，花时间O(22n)，总共n次调用，所用的时间为

如果常数次调O(2n)?O(2n)??O(2n)??2kn时间复杂度显然不是多项式时间复杂度。

2nk?1n用，则仍然是多项式时间。

4. 解析：

由于停机问题是不可判定的，因此它不是NP 问题，按照定义，显然它也不是一个NPC问题。对于NPC 问题SAT，我们可以构造一个多项式时间转换算法：任给一个输入命题公式，该算法对该公式枚举其变元的所有赋值，如果存在赋值使其为真，则停机，否则进入无限循环。这样，判断公式是否可满足便转化为判断以公式为输入的算法是否停机。因此，NPC 问题SAT 可以多项式时间约简到停机问题，所以，停机问题是难问题。 5. 解析：

如果HamCycle?P，首先注意到对回路中的每个顶点精确地有两条边与之相连。可以如下找汉密尔顿回路:选择一个顶点v∈V ，令Ev 表示所有与v相连的边的集合。找到一对边e1,e2

∈Ev, 使得G′=(V,E-Ev)?{e1,e2}含有汉密尔顿回路，这个能够在多项式时间里通过尝试所有

可能的一对边来实现。对图G′，类似上述过程求解。最终在多项式时间里得到一个图H=(V,C)，

其中C为所求的一个汉密尔顿回路。

6. 解析：

要证明HamPath为NP 问题，只要找到一个多项式时间验证算法，具体如下： 输入为,证书为一个顶点序列v1,v2,…,vn, 1 检查是否有v1=u,vn=v;

2 检查该序列是否包含了图中所有的顶点； 3 检查序列中任意两个相邻点在图中是否存在边； 上述三步显然可以在多项式时间内完成，得证。 7. 解析：

因为我们只需要检查任一个子句是否可满足，从而可决定整个子句是否可满足。

本文来源：https://www.bwwdw.com/article/064v.html