穷举查找

许多重要问题要求在一个复杂度随实例规模指数增长的域中，查找一个具有特定属性的元素。一般来说，这个问题的元素是指组合对象，比如排列，组合以及一个给定集合的子集。许多这样的问题都是最值问题：它们要求一个元素，能使某些期望的特性最大化或者最小化，比如路径的长度或者分配的成本。

对于组合问题来说，穷举查找是一种简单蛮力方法。它要求生成问题域中的每一个元素，选出其中满足问题约束的元素，然后再找出一个期望元素（例如，使目标函数达到最值元素）。穷举查找常常会要求一个算法来生成某些组合对象。我们把这种算法放到第5章去讨论，在这里，我们假设这种算法已经存在了。下面通过三个重要的应用来阐明穷举查找：旅行商问题，背包问题以及分配问题。

旅行商问题

旅行商问题因有着重要应用以及和其他组合问题的重要关联而很值得研究。非专业的说法，这个问题要求找出一条n个给定的城市间的最短路径，使我们从一个城市出发，对每一个城市都只访问一次。这个问题可以很方便地用加权图来建模，也就是说，用图的顶点代表城市，用边的权重表示城市间的距离。然后这个问题就可以表述为求一个图的最短哈密顿回路问题。（哈密顿回路定义为一个对图的每个顶点都只穿越一次的回路）。

哈密顿回路定义为n＋1个相邻顶点Vi0,…,Vin-1,Vi0的一个序列。其中，序列的第一个顶点和最后一个顶点是相同的，而其他n－1个顶点都是互不相同的。因此，通过生成n－1个中间城市的组合来得到所有旅行线路，计算这些线路的长度，然后求得最短的线路。图3.7介绍了该问题的一个小规模实例，并用该方法求出了它的解。

观察图3.7，我们有3对不同的线路，对每对线路来说，不同的只是线路的方向。因此，我们定义一条线路的方向可以把顶戴呢排列的数量减半。

然而这个改进并不能大大改善效率。排列的总次数仍然需要(n-1)!/2次，这意味着除了一些非常小的n之外，穷举查找法几乎是不实用的。

背包问题

给定n个重量为Wi,…,Wn, 价值为Vi,..,Vn的物品和一个承重为W的背包，求这些物品中一个最有价值的子集，并且要能够装到背包中。

图(a)介绍了背包问题的一个小规模的实例。

这个问题，穷举查找考虑给定的n个物品集合的所有子集，计算出每个子集的总重量，然后在它们中间找到价值最大的子集。图(b)给出图(a)问题的解。

因为一个n元素集合的子集数量是2^n,所以无论生成独立子集的额效率有多高，穷举查找都会导致一个Ω(2^n)的算法。

旅行商问题和背包问题就是所谓的NP困难问题.对于NP困难问题，目前没有已知的，效率可以用多项式来表示的算法。一些更复杂的方法——回溯法和分支界限法（参见11.1节和11.2节），可以在优于指数级的效率下解决部分问题。

分配问题

用穷举查找求解的问题第三个例子，有n个任务需要分配给n个人执行，每个任务只分配给一个人，每个人只分配一个任务。对于每一对i,j=1,…,n来说，将第j个任务分配给第i个人的成本是C[i, j].该问题要找出总成本最小的分配方案。

下面是该问题的一个小规模的实例，表中的单元格代表的是分配成本C[i,j]:

一个分配问题的实例完全可以用它的成本矩阵C来表示。就这个矩阵来说，这个问题要求在矩阵的每一行中选出一个元素，这些元素分别属于不同的列，而且元素的和是最小的。请注意，求解该问题并没有一个显而易见的策略。例如，我们不能选择每行中的最小元素，因为这些元素可能属于同一列。而且整个矩阵的最小元素并不一定是最优解的一部分。因此，似乎无法避免地要采用穷举查找。

我们用一个n维元组< j1,…jn>来描述分配问题的一个可能的解，其中第i个分量，表示的是在第i行中选择的列号（也就是说，给第i个人分配的任务号）。例如，对于上面的成本矩阵来说，<2,3,4,1>表示这样一种可行的分配；任务2分配给人员1，任务3分配给人员2，任务4分配给人员3，任务1分配给人员4。分配问题的穷举查找生成蒸熟1，2，…,n的全部排列，然后把成本矩阵中的相应元素相加来求得美中分配方案的总成本，最后选出其中具有最小和的方案。图3.9是用穷举查找解决一个小规模分配问题的最初几循环。

由于在分配问题的一般情况下，需要考虑得分排列数量是n!.幸运的是，对于该问题有一个效率高的多的算法，称为匈牙利方法.