p类算法

1. 能够被计算机解决的问题的特点是

1、分析问题。

用电脑来解决问题时，首先电脑要对问题进行定性、定量的分析，然后才能设计算法。定性分析法是对问题进行“质”的方面的分析，确定问题的性质，定量分析法，是对要解决的问题的数量特征、数量关系与数量变化进行分析的方法。

2、设计算法。

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

3、编写程序。

设计完算法后，就要使用某种程序设计语言编写程序代码，并最终得到相应结果。编程的语言包括汇编语言、机器语言和高级语言。高级语言中最简单、最常用的是Visual Basic语言和Pascal语言。

(1)p类算法扩展阅读：

人类解决问题：靠知识、见识、常识、经验、直觉、甚至赌博；

计算机解决问题：靠知识库、推理、推演、演绎、计算和预测以及概率分析。

人类会受外界因素和个人情感的干扰，导致同样的条件不同的结果；计算机则不受干扰，满足某个或某些条件，就会执行预先设定的命令。

利用计算机程序解决问题的基本过程：

了解利用计算机解决问题的基本过程。

了解问题分析与算法设计之间的关系。

2. 什么是P和NP

首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。 为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。。。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者P<>NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。

3. 举例说明算法领域的P类问题和NP类问题。为什么说现代计算机只能解决确

P:多项式时间内可以解决，太多了，如排序问题
NP:多项式时间内可以验证，如大数分解问题，随便给你一个非常大的数(该数由两个非常大的素数相乘得来)，你没法很快将其分解为两个素数的乘积，但若是把这两个素数告诉你，你可以很快的验证它是由这两个素数相乘得来（即多项式时间可验证）
上述两个概念一开始是用来描述判定问题的，后来被拓展到其他问题（如优化问题）上

现代计算机一就是冯洛伊曼结构，哪怕改成哈佛结构，也依旧只是一台图灵机，其表述能力无法超过图灵机范畴，所以只能解决确定性图灵机问题(这个名词我没听过，所以只能猜测其表示的意思)

4. 什么是P问题NP问题NPC问题三者关系如何

1、P问题
P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。

NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.
2、NP问题
然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。
NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.

3、NP完全问题
此外请注意，NP问题不一定都是难解的问题，比如，简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者P<>NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。
NP完全问题是求NP中判定问题的一个子类.NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。

5. 什么是G-p算法

遗传编程（GP）属于进化计算（Evolutionary Computation，EC）模型的一种。EC是一种借鉴自然界进化机制而产生的并行随机搜索算法。进化算法的基本原理是选择和改变，它区别于其他搜索方法有两个显着特征：首先这些算法都是基于种群（population）的；其次在种群中个体（indvial）之间存在竞争。 为搜索特定的（感兴趣的）查询需要一种工具，这种工具可智能生成一组查询并以它们是否能导出与用户给定的同样的对象集来进行评价。GP算法对这一类问题是很实用的。
1 函数集与端点集
一般GP中可生成的程序集是使用者定义的函数集和端点集。表1给出了相应的函数集和端点集，其中函数集由1.3中定义的查询算子、逻辑运算算子以及比较算子所组成。
函数集 {SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}， {>，>=，=，<，<=} 端点集类集，属性集，值集
表1 函数集和端点集
在我们的应用中还有一些具有不同句法的查询算子。每个算子具有不同的句法且假定的数据库是面向对象的。因此，它具有为创建个体而使用的特别的函数集（或算子集）和端点集。从而，构成种群的所有个体的创建必然受到每个算子的约束[3]。约束可以是算子的句法和查询的类型，或者是为创建查询选择适当属性值的领域知识。比较算子和逻辑算子只使用于查询的谓词。当比较符号操作数时，仅使用'='。
端点集由CLASS-SET、SLOT-SET和VALUE-SET组成。CLASS-SET由1.2中定义的类名组成，SLOT-SET由每个类的所有属性构成，VALUE-SET由数值和符号值所构成（它们均为属性值）。数值由整型或实型数构成，其数值范围由所用数据库模式定义。符号值由字符串表示的符号属性值构成。
[编辑本段]
2 创建初始种群
为了创建一个个体（查询），首先必须确定特定查询所返回的对象类型。结果类型被选择后，从所选类型返回例子的算子集中随机地选择一个算子，这个过程对查询的每个参数递归地进行。最初，那些句法正确的预定义数量的查询被随机地产生，形成初始种群。
[编辑本段]
3 选择属性值
由于可选择范围大，要从某个查询的值集中选择一个属性值（数值或符号常数）是相当困难的。对于一个范围为[1，10000]的整数集，随机选到一个特定整数的概率仅为1/10000。而对于符号常数，则需要很强的背景知识。因此，我们仅就发生在数据库里的范围选择属性值。
[编辑本段]
4 繁殖新一代种群
每个个体用预定义的适应函数来进行评价。较适应的查询有较高的概率被选来繁殖新种群，这个过程用三个遗传算子：选择、杂交和变异来完成。为了产生下一代，选择算子根据个体的适应值来选择个体。我们用一个树来表示一个查询，杂交算子用交换两个父辈的子树来创建两个后代。变异算子用一个新的子树来代替一个父辈的子树，从而产生一个新的后代。选择-杂交-变异循环反复地进行直到终止标准被满足。
[编辑本段]
5 评价（适应函数测量）
我们使用如下的适应函数f来评价种群中的个体查询i ：
f ( ni , hi ) = T - ( hi * hi ) / ni ,
其中：ni > 0 ， T ≥ hi ， 且 i = 1 ，2 ，… ，种群的大小（T是被确定的对象集的势，hi是一个个体查询i 被选中的次数，ni是查询 i 结果集的势）。
上述适应函数依赖于hi和ni ，如果一个查询没有被选中（hi=0），则函数的值为T，这是最差的一个适应值。另一方面，如果查询结果能够很好地匹配提交给系统的对象集，那么它的适应值为0（在这种情况下hi = ni = T ）。如果种群中出现个体适应值远远超过种群平均适应值，该个体很快就会在群体中占有绝对的比例，从而出现过早收敛的现象。另一方面，在搜索过程的后期，群体的平均适应值可能会接近群体的最优适应值，从而导致搜索目标难以得到改善，出现停滞现象[4]。为了防止上述情况的发生，我们将对一个个体查询的例子个数 ni 作为分母。

6. P类问题和NP类问题的定义和区别

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。
NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。

7. 世界七大数学难题之首是什么

NP 完全问题是世界七大数学难题之首。NP完全问题，是世界七大数学难题之一，排在百万美元大奖的首位。

NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

P类问题：所有可以在多项式时间内求解的判定问题构成P类问题。判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。

NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。

NP完全问题介绍：

有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题，这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。

人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题存在一个确定性算法，可以在多项式时间内直接算出或是搜寻出正确的答案呢？这就是着名的NP=P？的猜想。

8. 什么是p类问题什么是np类问题

P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任务的速度到底有多快。P对NP问题是Steve Cook于1971年首次提出。
“P/NP问题”，这里的P指多项式时间(Polynomial)，一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算;
NP指非确定性多项式时间(nondeterministic polynomial)，一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。
比NP问题更难的则是NP完全和NP-hard，如围棋便是一个NP-hard问题。2010年8月7日，来自惠普实验室的科学家Vinay Deolalikar声称已经解决了“P/NP问题”，并公开了证明文件。