算法|6.18 狂欢背后，站着算法和程序员们( 二 ) |京东商城|程序员

本文插图

对于骑士环游问题，通常的做法是采用回溯算法求解。

从起点开始，依次尝试跳到下一个位置，并记录骑士已走的步数；
如果所有的下一个位置都已经走过一次，且骑士已走步数少于 63 ，则说明此种走法不可行。回溯到上一步尝试下一个可走位置；
当骑士不重复地走到 63 步时，判断下一步能否回到起点，只有下一步能回到起点的方案才是可行方案，否则继续回溯寻找路线。

回溯虽然能解决这类问题，但这实际上是一种非常暴力的算法，我们必须对比所有可行方案，从而找到最优解。在物流算法中，我们将这类求解算法称之为精确算法。除此之外的精确算法还有割平面法、分支定界法、动态规划法等。
在实际应用中，由于精确算法的计算量会跟随问题规模的增大呈指数级增长，导致这类算法在现有计算设备中无法用于复杂的组合优化问题的求解。

本文插图

长久以来，人们一直在寻找一种这类问题的通用解，使得我们不需要穷举所有的情况，就能直接找出问题的答案。比如：

如果一个人告诉你 13,717,421 可以写成两个较小的数的乘积，你想要知道这个说法是否正确的话，必须枚举出所有的情况，挨个数字尝试。但如果他告诉你，这个数可以写成 3607 乘上 3803 ，你只需要计算一次便可以知道他说的是对的。
在求质数时，我们可以用与 n 依次相除来判断 n 是否是质数，或者用筛掉质数的倍数的方式来过滤出质数，但我们并不能找到一个通用的公式，能直接计算出下一个质数是多少。

这类问题都属于不确定问题，由此引申出一个重要的数学难题 —— NP 完全问题。
# NP 完全问题NP 完全问题（NP-C 问题），是世界七大数学难题之一。 NP-C 的英文全称是 Non-deterministic Polynomial Complete ，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底有没有让 NP=P 的算法，或是如何证明 NP≠P 。
再举一个通俗的例子：当我们用数字密码解锁手机时，如果我们不知道密码是多少，必须将所有的数字组合依次尝试。但如果知道了密码，我们可以轻易地验证这个密码是对是错。
这听起来像是一句废话，如果将它抽象一点的表述，就是：能用电脑快速验证一个解的问题，是否也能够用电脑快速地求出解。
如果能解决 NP 问题，世界上所有的密码都将被轻易破解。虽然直觉告诉我们不可能，但 NP 完全问题至今还没有被下定论。近年来人工智能、机器学习的发展均与这个猜想有些关系。人们尝试用启发式算法替代精确算法，使得 NP 逐渐趋近于 P 。
启发式算法的思想是：在不断解决问题的过程中寻找解决问题的最优方案。启发式算法实际上是通过不断地选择调优，以寻找到近似的最优解。在物流算法中，人们也是以此来解决经典的旅行商问题。
# 旅行商问题旅行商问题，又称为 TSP 问题（Traveling Salesman Problem），是一个经典的组合优化问题。描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。他应如何选择行进路线，以使总的行程最短。
从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的哈密顿回路。
哈密顿回路：由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。
上文已说到，该问题的可行解就是所有顶点的全排列，随着顶点数的增加，可行解的数量会呈指数级增长，也就是组合爆炸，它本质上是一个 NP 完全问题。