1.5 贪心算法思想

本节所要讲解的贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。

1.5.1 贪心算法基础

贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3个问题。

①不能保证最后的解是最优的。

②不能用来求最大或最小解问题。

③只能求满足某些约束条件的可行解的范围。贪心算法的基本思路如下。

①建立数学模型来描述问题。

②把求解的问题分成若干个子问题。

③对每一子问题求解，得到子问题的局部最优解。

④把子问题的局部最优解合并成原来解问题的一个解。实现该算法的基本过程如下。

（1）从问题的某一初始解出发。

（2）while能向给定总目标前进一步。

（3）求出可行解的一个解元素。

（4）由所有解元素组合成问题的一个可行解。

1.6 试探法算法思想

试探法也叫回溯法，试探法的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

1.6.1 试探法算法基础

使用试探算法解题的基本步骤如下所示。

①针对所给问题，定义问题的解空间。

②确定易于搜索的解空间结构。

③以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

试探法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

假设存在一个可以用试探法求解的问题P，该问题表达为：对于已知的由n元组(y1，y2，…，yn)组成的一个状态空间E={(y1，y2，…，yn)∣yi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中，Si是分量yi的定义域，且

Si

有限，i=1，2，…，n。E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最简单方法是使用枚举法，即对E中的所有n元组逐一检测其是否满足D的全部约束，如果满足，则为问题P的一个解。

但是这种方法的计算量非常大。

对于现实中的许多问题，所给定的约束集D具有完备性，即i元组(y1，y2，…，yi)满足D中仅涉及y1，y2，…，yj的所有约束，这意味着j（j＜i）元组(y1，y2，…，yj)一定也满足d中仅涉及y1，y2，…，yj的所有约束，i=1，2，…，n。换句话说，只要存在0＜=j＜=n−1，使得(y1，y2，…，yj)违反d中仅涉及y1，y2，…，yj的约束之一，则以(y1，y2，…，yj)为前缀的任何n元组(y1，y2，…，yj，yj+1，…，yn)一定也违反d中仅涉及y1，y2，…，yi的一个约束，n>=i>;j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(y1，y2，…，yj)违反D中仅涉及y1，y2，…，yj的一个约束，就可以肯定，以(y1，y2，…，yj)为前缀的任何n元组(y1，y2，…，yj，yj+1，…，yn)都不会是问题P的解，因而就不必去搜索它们、检测它们。试探法是针对这类问题而推出的，比枚举算法的效率更高。