1.2 计算机问题求解周期

在具体讨论问题求解之前，先看看数学家G. 波利亚在1944年提出的“怎样解题表”：

……

你以前见过它吗？你是否见过相同的问题而形式稍有不同？

你是否知道与此有关的问题？你是否知道一个可能用得上的定理？

看看未知数！试想出一个具有相同未知数的或相似未知数的熟悉的问题。

这里有一个与你现在的问题有关，且早已解决的问题。

你能不能利用它？你能利用它的结果吗？你能利用它的方法吗？为了能利用它，你是否应该引入某些辅助元素？

你能不能重新叙述这个问题？你能不能用不同的方法重新叙述它？

回到定义去。

如果你不能解决所提出的问题，可先解决一个与此有关的问题。你能不能想出一个更容易着手的有关问题？一个更普遍的问题？一个更特殊的问题？一个类比的问题？你能否解决这个问题的一部分？……如果需要的话，你能不能改变未知数或数据，或者二者都改变，以使新未知数和新数据彼此更接近？

……

尽管这张表是为解决数学问题而设计的，但是它对计算机问题求解具有深刻的启迪意义，在问题求解时离不开类似的分析问题的思维方法。

在设计算法求解特定问题时，算法的准确性和复杂性往往是人们关注的重点。首先，算法执行的结果必须正确。严格意义上，算法正确是指对于问题界定的所有问题实例，算法执行后都能得到正确的结果。其次，算法的复杂性要适中。计算机的资源（包括时间和内存）是有限的，所以算法必须在有限的资源条件下正确地求解问题，有关算法复杂性分析的更多讨论见1.4节。可见，用计算机算法求解问题不是一个容易的过程。

实际上，从一个问题的提出，到计算机可执行的、满足准确性和复杂性要求的程序实现，可以看作计算机问题求解的一个周期。问题求解周期包括问题简化、模型构建、算法设计、程序设计与调试等过程。

（1）问题简化

大多数实际问题涉及的因素很多，在求解之前必须经过简化，得到问题的原型（Prototype）。这个原型应当是没有歧义的，可以用1.1节介绍的“问题描述–输入–输出”标准方法加以定义（本书所讨论的问题都是以原型的形式出现的）。

（2）模型构建

问题的原型简洁地叙述了问题的条件、限制和求解目标，但是没有表明问题的本质。很多表面上看起来完全不同的问题具有相同的本质。模型构建是一个非常灵活的过程，同一个问题可以构建不同的模型，模型求解的难度也有差异。

构建模型后，只要不是简单到可以直接求解或者套用经典模型的程度，一般需要进行模型分析，得到初步结论。很多经典模型前人已经做过详细而透彻的研究，学习算法时应当尽量多地积累这样的经典模型及其求解算法。另一方面，如果是新模型，需要继续进行算法设计，这一步往往比构建模型更有挑战性。

（3）算法设计

由于问题答案最终需要由计算机执行得到，因此模型构建和分析后要进行算法设计。这是本书探讨的重点，也是计算机问题求解的核心要素。

（4）程序设计与调试

这是用特定程序设计语言实现算法的过程，属于程序设计的范畴。

例1-3展示了一个实际问题的求解过程。

【例1-3】 补丁与Bug问题

错误就是人们所说的Bug。用户在使用软件时总是希望其错误越少越好，最好是没有错误的。但是一个没有错误的软件几乎是不可能的，所以很多软件公司都在疯狂地发放补丁（有时这种补丁甚至是收费的）。T公司就是其中之一。上个月，T公司推出了一个新的字处理软件，随后发放了一批补丁。最近T公司发现其发放的补丁有致命的问题，那就是一个补丁在排除某些错误的同时，往往会新增一些错误。假设此软件中只可能出现n个特定的错误，这n个错误是由软件本身决定的。T公司目前共发放了m个补丁，对于每个补丁都有特定的适用环境，某个补丁只有在当前软件中包含某些错误同时不包含另一些错误时才可以使用；而且，补丁修复某些错误的同时会加入其他错误。另外，每个补丁都要消耗一定的时间（即补丁程序的运行时间）。

现在T公司的问题很简单，其软件的初始版本不幸地包含了全部n个错误，有没有可能通过使用这m个补丁（任意顺序地使用，一个补丁可使用多次），让软件成为一个没有错误的软件。如果可能，希望找到总耗时最少的方案。

显然，这是一个比较复杂的实际问题，在求解之前，我们需要对该问题进行适当简化和形式化的定义，得到如下问题原型。

问题描述：T公司的字处理软件中可能出现的n个错误记为集合B={b₁,b₂,…,b_n}，目前发放的m个补丁记为集合P={p₁,p₂,…,p_m}。对于每个补丁p_i，假设存在错误集合B_i+和B_i−：当软件包含了B_i+中的所有错误而没有包含B_i−中的任何错误时，补丁p_i才可以被使用，否则不能使用。显然，B_i+与B_i−的交集为空。补丁p_i将修复某些错误而同时加入某些错误，设错误集合有F_i+和F_i−，使用过补丁p_i后，F_i−中的任何错误都不会在软件中出现，而软件将包含F_i+中的所有错误。同样，F_i+与F_i−交集为空。另外，每个补丁都要耗费一定的时间T_i。

现在T公司的字处理软件的初始版本不幸地包含了全部n个错误，试编写程序来求解这个问题。

输入格式：第一行有两个正整数n和m，n表示Bug总数，m表示补丁总数，1≤n≤15, 1≤m≤100。接下来的m行给出了m个补丁的信息。每行包括一个正整数T_i（表示此补丁程序p_i的运行耗时）和两个长度为n的字符串，中间用一个空格符隔开。

第一个字符串，若第k个字符为“+”，则表示b_k属于B_i+；若为“-”，则表示b_k属于B_i−；若为“0”，则表示b_k既不属于B_i+也不属于B_i−，即软件中是否包含b_k不影响补丁p_i是否可用。

第二个字符串，若第k个字符为“+”，则表示b_k属于F_i+；若为“-”，则表示b_k属于F_i−；若为“0”，则表示b_k既不属于F_i+也不属于F_i−，即软件中是否包含b_k不会因使用补丁p_i而改变。

输出格式：输出一个整数，如果问题有解，输出总耗时，否则输出null。

获得问题原型后，下一步就是对该问题进行分析，构建相应的模型。客观世界是纷繁复杂的，当人们面对一个新问题时，通常的想法是通过分析、变形和转换，得到本质相同且熟悉的问题，这就是归化思想。如果把初始的问题或对象称为原型，则把归化后的相对定型的模拟化或理想化的对象称为模型。模型化的方向主要有图论模型、数学模型和规划（动态规划）模型。

因为补丁与Bug问题涉及耗时“最少”的要求，自然可以联想到图论中的最短路径问题。如果把n个Bug的状态（存在和不存在）的组合用一个0-1字符串表示（称为模式串），显然，所有n个Bug构成的模式串的数目最多是2n个；同时，运行一个补丁就会导致从一个模式串转换到另一个模式串。如果把模式串组成一个图模型的顶点，那么特定的补丁就构成该图的有向边，该补丁运行的时间则是该边的权重，如图1-2所示。当构建完了补丁和Bug问题的图模型后，原问题的解就对应了从起点模式串（11⋅⋅⋅11）到终点模式串（00⋅⋅⋅00）的一条最短路径。

下一步就是针对补丁与Bug的图模型设计求解算法。学过图论的读者应该容易想到，此问题可以直接应用Dijkstra最短路径算法求解。鉴于Dijkstra最短路径算法的典型性，Dijkstra算法的程序设计和调试的过程请读者自己完成。

另外，补丁与Bug问题也可以应用有限状态自动机模型，但是基于该模型的求解过程会复杂些，学有余力的读者可以自己设计和实现。