邮递员问题是p问题
tsp和cpp的差别？
什么叫P难题，NP问题和NPC难题？
旅行商问题（Traveling Salesman Problem, TSP）
这个问题字面的理解就是：有一个推销员，需到n个大城市推销产品，他想要找到一个包括全部n个城市具备最短路程的环城路。
TSP历史好长时间，最开始的描写是1759年欧拉探索的勇士环游难题，即针对国际象棋棋盘里的64个格子，走访调查64个格子一次且仅一次，而且最后返还到起始点。
TSP由美国RAND公司于1948年引进，公司的信誉及其线性规划问题这一新方式的发生促使TSP成为一个著名且最流行的难题。
2、我国快递员难题（Chinese Postman Problem CPP）
类似的问题，在我国还有另一个描述方法：一个快递员从邮政局考虑，到管辖街道社区递送电子邮件，最终回到邮政局，假如他务必踏遍管辖的一条街道社区最少一次，那他应当如何挑选递送路经，使所走的路程最少？这一叙述往往称之为我国快递员难题， 毕竟是我国学者管梅古谷专家教授于1962年所提出的这个问题而且提出了一个打法。
3、“一笔画”难题（Drawing by one line）
也有一个用图论语言表达的描写方法：平面内有n个点，用最少细线把全部一个点连起来。称之为“一笔画”难题。
4、配送路线难题（Route of Distribution）
TSP问题在货运物流中的描写是相匹配一个物流配送公司，欲将n个顾客的订购沿最短路线所有送至。怎么确定最短路线。
TSP难题简单的求得方法是什么枚举法。它解是多维度的、多局部极值的、趋向无穷错综复杂的解空间，搜索空间是n个点的全部排列的结合，尺寸为（n-1）！。能够生动地把解空间当做是一个无穷的丘陵地形，各高山或峡谷高度就是问题极大值。求得TSP，乃是在这里不可以可循的丘陵地形中攀爬从而达到峰顶或低谷的一个过程。
什么叫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或是PNP，但后来大家看到也有一系列的独特NP问题，这种问题的独特特性促使好多人坚信PNP，只不过是目前还没办法证明。这种特殊NP问题便是NP彻底难题（NPC难题，C意味着complete）。
NP彻底关键是求NP中判定问题的一个派生类.NPC难题存在一个令人惊讶的特性，即如果一个NPC难题存有多项式时间的算法，则每一个NP问题都能在多项式时间内求得，即P=NP创立！！主要是因为，每一个NPC难题还可以在多项式时间内转换成任何一个NP问题。例如前面说的哈米尔顿回路问题也是一个NPC难题。NPC问题历史时间并没多久，cook在1971年找到第一个NPC难题，自此大家又相继发现一些NPC难题，如今或许已经有3000好几个了。因此，大家一般认为NPC关键是难破问题，因为她不大可能存在一个多项式时间的算法（如果出现则每一个NP问题都存在着多项式时间算法，这太不可思议了，可是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担难题，集团公司难题，最少边覆盖难题（留意和途径覆盖差别），这些许多问题全是NPC难题，所以都是难破问题。