1、第 9 章 怎样研究算法:遗传算法示例1、P 类问题、NP 类问题、NPC 类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于 P、NP 和 NPC 类问题，回答下列问题。(1)下列说法不正确的是_。(A) P 类问题是计算机可以在有限时间内能够求解的问题；(B) NP 类问题是计算机可以在有限时间内能够验证“解”的正确性的问题；(C) NPC 类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解”的正确性的问题，被称为 NP 完全问题；(D)上述说法有不正确的；答案：D解释：本题考核 P 类问题、NP 类问题、NPC 类问题的概念。P 类问题指计算机可以在有限时间内求解的
2、问题，(A)正确； NP 类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题，(B) 正确；NPC 问题指 NP 问题的所有可能答案都可以在多项式时间内进行正确与否的验算，称为 NP-Complete 问题，(C)正确；(A)(B)(C)都正确，所以(D) 错误。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。(2)可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_。(A) P 类问题是可解性问题，NP 类问题是难解性问题。(B) NP 类问题不一定是难解性问题，因为 P 类问题
3、也一定是 NP 类问题；(C) NP 类问题不确定是否是 P 类问题，但 NPC 类问题一定是难解性问题；(D)上述说法有不正确的；答案：A解释：本题考核对可解性问题和难解性问题概念的理解。P 类问题指计算机可以在有限时间内求解的问题，所以是可解性问题；NP 类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题，但 P 类问题是 NP 类问题的一个子集，所以 NP 类问题不一定是难解性问题；NPC 问题指 NP 问题的所有可能答案都大学计算机-计算思维练习题集可以在多项式时间内进行正确与否的验算，称为 NP-Complete 问题，是难解性问题，综上，(A)错误。具体内容请参考第
4、九章视频之“可求解与难求解问题”以及第九章课件。(3)下列说法正确的是_。(A) P 类问题是计算机可以在有限时间内能够求解的问题；(B) NP 类问题是计算机可以在有限时间内能够求解的问题；(C) NPC 类问题是计算机可以在有限时间内能够求解的问题；(D)上述说法都正确；答案：A解释：本题考核 P 类问题、NP 类问题、NPC 类问题的概念。只有 P 类问题是计算机可以在有限时间内能够求解的问题，所以(A)正确。具体内容请参考第九讲视频之“可求解与难求解问题”以及第九章课件。(4)P 类问题是多项式问题(Polynomial Problem)，NP 类问题是_。(A) 非多项式问题；(B)
5、 非确定性多项式问题；(C) 非 P 类问题；(D) 确定性非多项式问题；(E) 上述说法都正确；答案：B解释：本题考核对 NP 类问题的理解。P 类问题是多项式问题(Polynomial Problem)，NP 类问题是非确定性多项式问题(Non-deterministic Polynomial)， NPC 问题是完全非确定性多项式问题(NP-Complete) ，所以(B)正确。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。(5)下列说法不正确的是_。(A) P 类问题是总能找到一个多项式时间复杂性算法进行求解的问题；(B) NP 类问题是一定找不到多项式时间复杂性算法进
6、行求解的问题；(C) NP 类问题是不确定能够找到多项式时间复杂性算法进行求解的问题；(D) NP 类问题虽然是不确定能找到多项式时间复杂性算法进行求解，但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题；大学计算机-计算思维练习题集(E) 上述说法有不正确的；答案：B解释：本题考核对 P 类问题、NP 类问题概念的理解。P 类问题是总能找到一个多项式时间复杂性算法进行求解的问题，NP 类问题虽然是不确定能找到多项式时间复杂性算法进行求解，但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题，所以(B)错误。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。(*
7、6)非确定性多项式问题是指这样的问题，下列说法不正确的是_。(A)它能够找到一个算法、甚至是多项式时间复杂性算法进行求解，但算法中包含“不确定性” ，如“任意组合一个解，” 、 “随机组合一个解，”等；(B)它能够找到一个算法、甚至是多项式时间复杂性算法进行求解，但算法是通过“猜测”方式求出问题的解；(C)它能够通过“产生任何一个解，并验证解的正确性 ”的方法进行求解；(D)它一定是能够找到多项式时间复杂性算法以验证给定“解”的正确性的问题；(E)上述说法有不正确的；答案：E解释：本题考核对 NP 类问题概念的理解。NP 类问题：非确定性多项式问题(Non-deterministic Poly
8、nomial)。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，所以(A)(B)(C)(D)都是正确的，(E)错误。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。(7)、关于 NP 类问题求解，下列说法正确的是 _。(A)NP 类问题求精确解，可能找不到多项式时间复杂性算法；但 NP 类问题求近似解，则一定能够找到多项式时间复杂性算法；(B)NP 类问题求精确解，可能
9、找不到多项式时间复杂性算法；但 NP 类问题求近似解，则也可能找不到多项式时间复杂性算法；(C)虽然能够找到求 NP 类问题近似解的多项式时间复杂性算法，但所求得的解一定不是满意解；(D)既然能够找到求 NP 类问题近似解的多项式时间复杂性算法，则所求得的解就一定是满意解；大学计算机-计算思维练习题集(E)上述说法都正确；答案：A解释：本题考核对 NP 类问题求解的理解。NP 类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，所以 NP 类问题求精确解，可能找不到多项式时间复杂性算法，但 NP 类问题求近似解
10、，则一定能够找到多项式时间复杂性算法，(A) 正确(B)错误；虽然能够找到求 NP 类问题近似解的多项式时间复杂性算法，但所求得的解不一定是满意解，(C)(D)错误。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。2、下图能够基本反映生物学遗传与优胜劣汰的过程。理解该图，联想计算类问题求解，回答下列问题。大学计算机-计算思维练习题集(1)下列说法不正确的是_。(A)任何一个生物个体的性状是由其染色体确定的，染色体是由基因及其有规律的排列所构成的，因此生物个体可由染色体来代表；(B)生物的繁殖过程是通过将父代染色体的基因复制到子代染色体中完成的，在复制过程中会发生基因重组或基因突
11、变。基因重组是指同源的两个染色体之间基因的交叉组合，简称为“杂交/交配” 。基因突变是指复制过程中基因信息的变异，简称“突变” ； (C)不同染色体会产生不同生物个体的性状，其适应环境的能力也不同；(D)自然界体现的是 “优胜劣汰，适者生存 ”的丛林法则。不适应环境的生物个体将被淘汰，自然界生物的生存能力会越来越强；(E)上述说法有不正确的。答案：E解释：本题考核对生物遗传观点以及所给图片的理解。关于生物遗传进化的基本观点如下：生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；(ii) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；(iii) 生物的繁殖过程
12、是由其基因的复制过程来完成的；(iv) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(v) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。 故（A） 、 （B） 、 （C） 、 （D）均正确。于是， （E）错误。具体内容请参考课堂视频“遗传算法的缘起-生物学中的遗传与进化” 和第九章课件。(2-1)类比计算类问题求解，下列说法不正确的是_。(A)一个染色体即是指问题的一个“可能解” 。任何“可能解”都可以表达为编码形式，构成编码的基本单位即是基因； 大学计算机-计算思维练习题集(B)所谓的复制、杂交、突变，是指一个可能解或两个可
13、能解之间发生的、编码片段之间的复制、交叉或变异，它们都是产生新可能解的一种方式；(C)所谓的环境适应性，可以认为是对一个可能解的一种度量，即能够度量一个可能解的好与坏的某一函数值，被称为“适应度” ；(D)基于(A)(B)(C) ，遗传算法就是 “通过复制、交叉或变异，不断产生新的可能解；计算可能解的适应度；淘汰掉适应度差的可能解，保留适应度好的可能解。 ”(E)上述说法有不正确的；答案：E解释：本题考核对生物学中的概念与计算机中的概念的映射的理解。染色体映射到计算机中就是编码解。（A）正确。复制是指将一个解从一个解集复制到另外一个解集。杂交是指对两个可能解的编码通过交换某些编码位而形成两个新
14、的可能解的遗传操作，是新可能解的一种形成方式。突变是指随机地改变一个可能解的编码的某些片段( 或基因) 而使一个可能解变为一新的可能解的遗传操作 ，也是新解的一种形成方式。（B ）正确。适应度性是指一个可能解接近最优解的一个度量。 （C ）正确。由（A ） （B ）（C ） ，可以得到遗传算法的基本思想。 （D）正确。故（E）错误。综上， （E）错误。具体内容请参考课堂视频“计算学科的遗传算法”和第九章课件。(2-2)类比计算类问题求解，下列说法不正确的是_。(A)一个染色体即是指问题的一个“可能解” ，一个基因即是“可能解”的一个编码位或若干编码位的一个组合； (B)一个种群即是一个包含问题
15、满意解的“可能解”的集合；(C)适应度，即是对“可能解 ”的一个度量，它可以衡量“可能解”接近最优解或精确解的程度；(D)复制、交叉、变异等都是产生新“可能解”的方式；(E)上述说法有不正确的；答案：B解释：大学计算机-计算思维练习题集本题考核对生物学中的概念与计算机中的概念的映射的理解。染色体映射到计算机中就是编码解，即一个可能解的基因型。一个基因即是指可能解的某一位或几位，（A）正确。种群是指若干可能解的集合，而不一定包含问题的满意解，（B ）错误。适应度性是指一个可能解接近最优解的一个度量， （C ）正确。复制、交叉、变异等都是产生新“可能解”的方式， （D ）正确。因为（B）错误，故（
16、E）正确。综上，本题答案为（B） 。具体内容请参考课堂视频“计算学科的遗传算法”和第九章课件。3、类比生物遗传与优胜劣汰而形成的遗传算法的求解过程如下图示意。理解该图，回答下列问题。(1)图中给出了遗传算法的基本求解过程示意。关于图中包含了哪些过程，下列说法正确的是_。(A)可能解的编码过程和初始种群的产生过程；(B)交叉、变异形成候选种群的过程；(C)可能解的适应度计算过程和汰选可能解形成新一代种群的过程； (D)算法终止及最终解的形成过程； (E)上述全部过程。答案：E大学计算机-计算思维练习题集解释：本题考查学生对遗传算法基本求解过程的理解。图中第一行第一个箭头即是可能解的编码过程和初始
17、种群的产生过程。最右的大方框内的即是交叉、变异形成候选种群的过程。右下方的方框以及箭头即是可能解的适应度计算过程和汰选可能解形成新一代种群的过程。左下的图与箭头即是算法终止及最终解的形成过程。综上，（E）正确。具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。(2)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_。(A)初始种群中的可能解可以随机产生； (B)对于哪两个可能解进行交叉，可以采取随机方式从种群中选择出来； (C)对于两个可能解进行两段交叉，其交叉点是固定的，不可以采取随机方式确定；(D)对于哪个解进行变异，以及变异位置的确定，可以采取随机方式选
18、择和确定；(E)上述有不正确的说法。答案：C解释：本题考查学生对遗传算法随机性的理解。在遗传算法中，所有的解的产生，以及交叉，变异等可以随机的产生，并不是固定的。所以（C）的说法不正确。具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。(3)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_。(A)种群的规模，即种群中可能解的个数是预先设定且固定不变的，其大小影响遗传算法求解的质量和效率； (B)种群的规模，虽然是预先设定的，但其大小不会影响遗传算法求解的质量和效率； (C)种群的规模可以依据问题的所有可能解的个数来确定：太大，虽求解效果好但计算量却很大；太小
19、，虽计算量很小，但求解效果却难以保证；(D)种群规模不是随机确定的；(E)上述有不正确的说法。答案：B解释：本题考查学生对遗传算法种群规模及其确定方法的理解。大学计算机-计算思维练习题集在遗传算法的设计过程中，应该根据问题的具体情况设置合适的种群规模。如果规模过大，虽然求解效果好，但是计算量很大。如果规模太小，计算量虽然不大了，但是求解效果就难以保证了。所以，种群规模的大小一定会影响遗传算法求解的质量和效率。具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。(4)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_。(A)遗传算法可以一个轮次一个轮次迭代地进行(
20、被称为“进化”)，可以在迭代到一定次数后终止；(B)遗传算法一定可以求得满意解或最优解，它一定是在得到满意解或最优解时才终止；(C)遗传算法必定涉及随机处理，因为不仅仅是问题可能解的空间很大，而任何一个子解空间也都可能很大，穷举是难以办到的； (D)遗传算法是以交叉操作为产生新可能解的主要操作，而以变异操作作为产生新可能解的辅助操作； (E)上述有不正确的说法。答案：B解释：本题考查学生对遗传算法的迭代性和求解质量方面的理解。遗传算法就是通过不断的迭代来淘汰不好的解，留下好的解，（A）正确。不是任何问题采用遗传算法都可以得到满意解或最优解，因为遗传算法中会有随机的过程，算法每次执行的结果都不尽
21、相同，（B）的说法不正确。（C）（D）的说法都没有问题。故此题的答案为（B）。具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。(5)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_。(A)适应度，主要用于考察一个可能解是否接近最优解，以及接近的程度和方向，所以通常选择极值函数(如最大值函数或最小值函数 )作为度量函数；(B)一般而言，通过将可能解代入一个极值函数 (如最大值函数或最小值函数 )中获得函数值，以该函数值作为适应度的值；(C)一个问题，若要用遗传算法求解，则要能够将其映射为类似于求极值一样的函数，即函数的极大值(或极小值)对应了问题的最优解/
22、较优解，这是问题数学建模的一种方向；(D)适应度函数可以任取一个极值函数，它与求解问题本身可以没有什么关系；(E)上述有不正确的说法。大学计算机-计算思维练习题集答案：D解释：本题考查学生对遗传算法的适应度函数的理解。遗传算法的适应度函数用来考察解与最优解的关系（接近程度、方向等）。而极值函数可以简单、清晰地表现该关系。所以，极值函数经常被选为遗传算法的适应度函数，（A）（B）（C）正确。适应度函数不能随意选择，一定是问题映射形成的函数，否则该适应度函数没有意义，（D）错误。故此题的答案为：（D）具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。4、关于遗传算法为什么可
23、以求解 NPC 类问题。理解下图，回答下列问题。(1)遗传算法是典型的计算求解的方法，它通过“产生任何一个可能解，并验证可能解的正确性”的方法求解一个复杂问题。关于计算求解，下列说法正确的是_。(A)可以从所有可能解的集合中产生每一个可能解，并验证可能解的正确性。利用这种策略的算法，计算机一定能够在有限时间内找到精确解；(B)可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法，计算机一定能够在有限时间内找到精确解；(C)可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法，计算机一定能够在有限时间内找到满意解；(D)可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法，如果随机产生的可能解越多，则计算机找到满意解的概率也越大，但耗费时间也越长；(E)上述说法都正确；答案：D解释：本题考查遍历搜索与随机搜索的共性与差别；从可能解中产生的集合，也许这个集合里并没有精确解，那么计算机不可能在该集合中找到精确解。（A）（B）（C）说法不正确。但是，产生的随机解越多，找到满意解的概
