第9章怎样研究算法遗传算法示例练习题答案解析.docx

第9章怎样研究算法遗传算法示例练习题答案解析.docx第9章怎样研究算法:遗传算法示例1、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题,回答下列问题。下列说法不正确的是 oP类问题是计算机可以在冇限时间内能够求解的问题;NP类问题是计算机可以在有限时间内能够验证“解”的正确性的问题;NPC类问题是对问题的每一个可能解,计算机都可以在有限时间内验证“解”的正确性的问题,被称为NP完全问题;上述说法有不正确的;答案:D解释:本题考核P类问题、NP类问题、NPC类问题的概念。P类问题指计算机可以在有限时间内求解的问题,(A)正确;NP类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题,(B)正确;NPC问题指NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算,plete问题,(C)正确;(A)(B)(C)都正确,所以(D)错误。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。可解性问题是指能够找到多项式时间复杂性算法进行求解的问题,难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是 。P类问题是可解性问题,NP类问题是难解性问题。NP类问题不一•定是难解性问题,因为P类问题也定是NP类问题;NP类问题不确定是否是P类问题,但NPC类问题-淀是难解性问题;上述说法有不正确的;答案:A解释:本题考核对可解性问题和难解性问题概念的理解。P类问题指计算机町以在冇限时间内求解的问题,所以是可解性问题;NP类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题,但P类问题是NP类问题的一个了集,所以NP类问题不…定是难解性问题;NPC问题指NP问题的所仃可能答案都可以在多项式时间内进行正确与否的验算,plete问题,是难解性问题,综上(A)错误。具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。下列说法正确的 oP类问题是计算机可以在有限时间内能够求解的问题;NP类问题是计算机可以在有限时间内能够求解的问题;NPC类问题是计算机可以在有限时间内能够求解的问题;上述说法都正确;答案:A解释:本题考核P类问题、NP类问题、NPC类问题的概念。只有P类问题是计算机可以在有限时间内能够求解的问题,所以(A)正确。具体内容请参考第九讲视频之“可求解与难求解问题”以及第九章课件。P类问题是多项式问题(PolynomialProblem),NP类问题是 。非多项式问题;非确定性多项式问题;非P类问题;确定性非多项式问题;上述说法都正确;答案:B解释:本题考核对NP类问题的理解。P类问题是多项式问题(PolynomialProblem),NP类问题是非确定性多项式问题(Non-deterministicPolynomial),NPC问题是完全非确定性多项式问题(plete),所以(B)正确。具体内容请参考第九章视频Z“可求解与难求解问题”以及第九章课件。下列说法不正确的 oP类问题是总能找到一个多项式时间复杂性算法进行求解的问题;NP类问题是一定找不到多项式时间复杂性算法进行求解的问题;NP类问题是不确定能够找到多项式时间复朵性算法进行求解的问题;NP类问题虽然是不确定能找到多项式时间复杂性算法进行求解,但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题;上述说法有不正确的;答案:B解释:本题考核对P类问题、NP类问题概念的理解。P类问题是总能找到一个多项式时间复杂性算法进行求解的问题,NP类问题虽然是不确定能找到多项式时间复杂性算法进行求解,但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题,所以(B)错误。具体内容请参考第九章视频Z“对求解与难求解问题”以及笫九章课件。(*6)非确定性多项式问题是指这样的问题,下列说法不正确的是 o它能够找到一个算法、英至是多项式时间复杂性算法进行求解,但算法)|咆含“不确定性”,如“任意纟fl合一个解,“随机纟fl合一个解,…”等;它能够找到一个算法、甚至是多项式吋间复朵性算法进行求解,但算法是通过“猜测”方式求出问题的解;它能够通过“产生任何一个解,并验证解的正确性”的方法进行求解;它一定是能够找到多项式时间复杂性算法以验证给定“解”的正确性的问题;上述说法有不正确的;答案:E解释:本题考核对NP类问题概念的理解。NP类问题:非确定性多项式问题(Non-deterministicPolynomial)0有些问题,其答案是无法宜接计算得到的,只能通过间接的猜算或试算來彳寻到结果,这就是非确定性问iS(Non-deterministic)o虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题,B|J:在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题,所以(A)(B)(C)(D)都是