07-现实世界的应用

9.4　现实世界的应用

背包问题采用的动态规划技术适应范围比较广泛，能将貌似很棘手的问题分解成较小的问题，再把多个较小问题的部分解组合在一起形成整体解。背包问题本身与其他一些优化问题有关联，这些问题必须将有限的资源（背包的容纳能力）分配给有限但会耗尽该资源的可选目标集（要窃取的物品）。不妨想象一下，有一所大学需要分配运动经费预算。学校没有足够的资金提供给每个运动队，因此希望每个运动队会引入一些校友捐款。于是就可以求解一个类似背包的问题，以便获得最优的预算分配方案。这类问题在现实世界中十分常见。

旅行商问题是UPS和FedEx等运输和配送公司的日常事务。包裹快递公司希望司机能以最短的路线行驶。这不仅让司机工作起来更加愉悦，而且还节省了燃料和保养成本。人们都会出门旅行，或为工作或为游玩，在访问多个目的地时找到最优路线可以节省很多资源。但旅行商问题不仅仅是行进路径问题，几乎所有需要单次访问节点的寻路场景都会碰到该问题。假设需要为某社区连通电路，尽管第4章的最小生成树可以最小化所需电线的量，但如果每栋房子都必须只与其他房子连接一次，且需组成一个大的回路以便能回到起点位置，则最小生成树算法无法得出电线的最优量，而用旅行商问题就能解决。

对于各种蛮力算法的测试，排列生成技术（类似于旅行商问题和电话号码助记符问题的朴素解法）非常有用。例如，要破解某个短密码，就可以对能够出现在密码中的字符生成所有可能的排列。对于大规模的排列生成任务而言，从业人员会明智地选用类似堆（heap）算法^[2]之类的高效排列生成算法。