天才一秒记住【久久文学】地址：https://www.jjwxx.com
的要求。
我们用抽象的方式来描述这个问题[28]：
首先给出一个包含n个人的列表（在上述例子中，这些人就是约翰、保罗、乔治和林戈，因此n=4），以及一个“禁止组队”
的列表（例如，“约翰和保罗不能在一起工作”
）。
那么，我们能否得到一个包含m个人的团队，使得所有禁止组队的条件都能得到满足？（显然，要使得这个问题有意义，m必须小于n。
）
必须指出的是，这个问题在原则上是很容易解决的。
简单地列出所有含有m个成员的团队名单，并检查每一个团队名单是否与禁止组队列表有冲突即可。
用计算机编程来做这个步骤非常容易。
因此，在图灵的观念里，这个问题很容易求解。
那么，问题的关键来了，我们需要检查多少种组合的可能性呢？如果是4人团队里面选3人，那很容易，你需要检查4个有可能的选择。
但当团队人数增多，会出现什么情况，我们来看看吧。
如果是10人团队选5人，你就得检测252种可能性。
好吧，很枯燥，但是还能忍受。
不过可以看到的是，选择可能性的增长速度远远大于整个团队成员或者目标团队成员的数量增长的速度。
如果是100人团队里面选50人，那你就得检测大约1029这么多种可能性了。
一台当代的大型计算机每秒可以评估大约1010种可能性——听起来挺多的，但是，稍微计算一下你就能意识到，即便算到宇宙末日，也无法检测完毕。
期待英特尔的工程师们提供计算速度更快的芯片也无济于事：传统计算机技术再怎么突飞猛进，也无法在合理的时间内完成这个数量级的计算任务。
我们在这里所看到的现象也是组合爆炸的例子。
在研究搜索树的时候我介绍过组合爆炸的概念，搜索树中的每个层级都呈指数型增长。
所以在层级增多的时候，组合爆炸会导致可能出现结果的增长速度超乎想象。
在团队建设的案例中，只要团队总人数增加1个人，我们必须考虑的潜在组合型就会翻倍。
所以，这种彻底列举每一种组合可能性的方式，是不可行的。
理论上它行得通（如果时间足够，总会得到正确的答案），但在实践中它毫无意义（因为对每种可能的组合做判断需要的时间是天文数字）。
因为我们的问题是一个NP完全问题的案例[2]。
恐怕这个首字母缩写对不熟悉计算机编程的人而言太过陌生：“NP”
代表“不确定多项式时间”
，具体的技术定义相当复杂。
幸运的是，NP完全问题背后的逻辑很简单。
组合问题是一个NP完全问题，就像我们团队建设的例子。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！