企业官网建设流程全解析

1.预备知识

1.1多项式

1.3约化

一个问题A可以约化为B的含义是，可以用问题B的解法解决问题A。
例如：求解一个一元一次方程A和求解一个一元二次方程B，你若会求解B，你一定会求解A。那么我们说，A可以约化为B。可以理解为问题约化后会变难。

1.4Hamilton回路

从图中的一个顶点出发，沿着边行走，经过图的每个顶点，且每个顶点仅访问一次，之后再回到起始点的一条路径。

2.p类问题（polynominal，多项式）

2.1定义：一个可以在多项式时间复杂度内解决的问题。

2.2举例：n个数的排序问题（不超过O(n2)）

为什么我们要研究这个呢？为什么以多项式为标准而不是其他的？因为计算机处理的数据量是非常大的，想象一下，当计算机处理的数据达到100万个的时候，时间复杂度为O(n²)和O(2ⁿ)的算法，所需的运行次数是天文之数，指数级的可能运行好几天都没法完成任务。但多项式级别的时间是可以接受的。所以我们也只在乎一个问题是否存在多项式算法，而一个时间复杂度比多项式还要复杂的算法研究起来是几乎没有意义的。

3.np问题（Nondeterministic polynominal，非确定多项式）

3.1定义：

可以在多项式的时间里验证一个解的问题，即给出一个答案，可以很快地（在多项式时间内）验证这个答案是对的还是错的，但是不一定能在多项式时间内求出正确的解

P类问题是np问题的子集

4.np难问题

4.1定义：

任意np问题可以在多项式时间内约化成该问题，即为了解决np问题A，先将问题A约化为另一个问题B，解决问题B同时也间接解决了问题A，问题B就是一个np难问题

4.2注意：

np难问题并不完全包含np类问题，因为一个问题约化后会变得更难，就不一定还能在多项式时间内验证答案。

4.3举例

旅行商求最短回路
设一个推销员需要从香港出发，经过广州、北京、上海、…等 n 个城市，最后返回香港。任意两个城市之间都有飞机直达，但双向的票价不等。求总路程最少的行程安排。

分析：想要知道所有方案中花费最少的，必须检查所有可能的旅行安排才能找到，即(n-1)!种方案，很显然这不是P问题。给出任意一个行程安排，你能算出它的总路程，但无法在多项式时间内验证这条路径是否是最短路。所以不是NP问题。

而之前提出的Hamilton回路问题可以约化到这个问题上。即如果我能解决旅行商问题，那么说明我能解决如何找到Hamilton回路。因此这个问题是NP难问题。