利用计算机求解的问题,CCCF专栏 | 裘宗燕：计算机问题求解的三类方法

向右看齐 2022-10-07 15:58 135阅读 0赞

问题和问题求解

实际问题千变万化，我们考虑一种抽象的统一说法：一个问题就是从一个实例描述集合到解集合的映射，

![156230237\_1\_2019031105054598][156230237_1_2019031105054598]。如果I是有穷集，T 就是有穷问题，否则T 是无穷问题。

![156230237\_2\_20190311050545113][156230237_2_20190311050545113]或

![156230237\_3\_20190311050545144][156230237_3_20190311050545144]称为问题 T 的实例，o=T(i) 称为问题T对应i的解。

计算机只会做一件事，就是自动执行程序。用计算机解决一个问题，就要写出一个解决这个问题的有穷程序(无穷长的程序写不完)。如果针对问题T写了程序P，把T的任意实例i作为P的输入，P的输出总是o=T(i)，我们就可以说P解决了问题T。

针对问题写出程序是计算机领域最重要的工作。要完成这种工作，首先要确定一种技术路线(一种方法)，确定需要从问题中挖掘出什么信息(知识)，怎样利用得到的知识构造程序。参考几十年的研究和实践，本文总结出三类方法。是否还有第四类？请读者考虑。

基于算法的系统(Algorithm-Based Systems, ABS)

这个太显然。但是，采用这一方法有什么前提条件？在什么情况下有可能得到解决问题的算法，并实际写出能解决问题的程序？我们可以提出下面一些条件。

首先，该问题必须是“可计算的”，这是理论要求。证明问题是否可计算常常很不容易，但做出算法就是正面的证明。其次，要做出算法，要求我们对问题及其求解完全理解，知道如何处理问题的任意实例，能处理求解过程中可能遇到的任何情况。

算法的优点是直接针对具体问题，是专用的，因此效率高。另一方面，我们比较容易把算法转换为解决问题的程序，也比较容易判断一个程序是否确实解决了问题。

注意：任何有穷问题都有算法。由于情况(输入)有穷，理论上总是可以对其做穷尽分析，分情况给出解。求解程序如下(假定问题只有n个实例，x是输入)：

![156230237\_4\_20190311050545176][156230237_4_20190311050545176]

无穷问题也可能写出有穷算法，例如求最大公约数问题。

现在看看用计算机下围棋的问题。围棋要求对弈双方在19×19的棋盘上交替落子，目标是占据最大的地盘。下围棋程序只需要解决一个问题：对任何棋局，确定下一个棋子的最佳位置。由于局面有穷，本问题为有穷问题。按前面的说法，存在确定最佳位置的算法。基于这一算法的围棋程序绝不会犯错，其棋力不会弱于(昨天、今天或未来的)任何棋手，或任何下围棋的程序，包括AlphaGo和AlphaZero。

我们很容易规划出一套写这个算法的系统化方法，只要有充分的耐心和时间，就能做出一个这样的围棋程序。但是，由于可能局面太多(约为3361≈10172)，彻底分析每个局面需要的时间太长，这一工作不可能在合理的时间内完成。另一方面，即使能写出来，程序也太长，计算机没有足够的存储器存放它。这一实例说明，理论上有算法，但并不代表能用算法解决问题。

算法的另一个限制是计算机专业人士最熟悉的：必须足够高效(复杂性不高)，保证每次执行可以在合理时间内完成。例如，如果一个围棋程序在求解中，需要检查的局面个数可能达到10172，则这个程序(实际上)毫无意义。

下面是能用算法解决问题的一些条件：首先对问题要有完整的认识，对求解过程有全面完整的把握，否则只能考虑其他方法。

建模后得到的抽象问题是可计算的(理论条件)，否则只能考虑解决原问题的恰当的可计算子问题，或降低要求，解决结果类似但要求较低的问题。

算法存在有穷长度的描述，而且描述不“过于长”，可在合理时间内写完。

每个实例的求解都能在合理时间内完成。如果效率太低，只能设法找其他算法，或收缩问题(解决合适的子问题)，或降低要求，如最优解改为近似解等。

如果找不到算法，或者虽然有算法但不适用，我们就只能考虑其他方法。

基于搜索的系统(Searching-Based Systems, SBS)

用计算机解决问题的另一类方法是搜索，也就是通过探查和回溯的方法寻找解。搜索方法并不要求我们对问题及其求解过程有全面的认识，但需要有一些清晰的知识片段，以这些知识片段作为搜索的基础。例如，对基于规则的系统，需要有针对问题的规则库；自动推理需要有事实和推理规则。基于搜索的系统由两部分组成：一部分是针对问题的知识库，包含一集知识片段(规则)；一部分是搜索算法，它设法利用知识库去拼凑出实例的解。

人工智能领域研究过许多搜索方法，开发了一些通用框架(如产生式系统、黑板系统)；提出了许多技术(如各种启发式搜索算法)，实现了一些应用(如基于规则的专家系统)；提出了一些编程泛型(如逻辑程序设计、约束程序设计)。还有自动推理、定理证明等方面的大量研究和成果。赫伯特·西蒙(司马贺)等人称搜索为通用问题求解(general problem solving)方法。

只有解决问题的片段知识(规则)，通常做不出算法。规则可能不完全，无法处理所有实例或所有情况，也没有处理策略(顺序和过程)。但规则可以用于搜索，通过试探和回溯的方式去求解。搜索的特点是，算法不直接针对问题，而是针对规则的使用。规则可独立描述，也可以嵌入搜索算法中。搜索也已广泛用于实践，例如自动泊车系统常包含搜索。

关于计算机下棋的研究已有几十年历史，基本方法就是博弈树搜索，评价各种可能，选出最佳棋着。围棋的规则很简单，很容易实现一个基于搜索的围棋程序。为此，我们只需实现一个处理博弈的通用搜索引擎，让它用围棋规则去做穷尽搜索，找出最佳棋着。

当然，稍微了解计算机的人都会说上述方案不可行。规模为10172的状态空间太大，朴素搜索方法实际无用。这个不可行的原因是实际计算开销，而不是理论不正确。这也说明了搜索方法的一个重要弱点：求解中需要探查的空间通常以相对于实例规模的指数方式增长。因此，对复杂一些的问题或规模较大的实例，我们可能无法等到结果。

实际围棋程序(包括AlphaGo和AlphaZero)都采用了一些策略，如限制最大搜索深度(或限制搜索时间)，加入随机性因素等。设法在不能穷尽搜索的情况下合理地评估局面，只能评估检查到的那些局面，并从中选择可能通向“最佳路径”的棋着等。

搜索方法的优势是有可能利用部分知识解决问题，但也存在许多固有的缺陷：搜索策略或规则选择策略不当，可能使搜索进入无穷的或巨大的无解区域，导致实际有解，但却(很长时间)找不到。也难保证对不同实例的(时间)行为一致性。

搜索状态爆炸的本质性问题。

规则集不完全，可能导致某些实例无法求解；而规则集越大，状态爆炸问题越严重(规则集丰富表示对问题的认识丰富。这是搜索方法的一个固有矛盾)。

假设有了一集规则，在采用基于搜索的方法时，需要考虑搜索策略(宽度优先、深度优先、其他)，规则选择策略(固定顺序、估值序、随机等)，还需考虑状态评估，可能的剪枝策略，局部搜索(限制搜索深度、与评估结合)等问题。

基于实例的系统(Case-Based Systems, CBS)

如果对问题的了解非常少，或基本上没有有关求解的知识，还能用计算机吗？实际情况经常如此：我们认为面临的是一个问题，有需要处理的情况，人能得到有用的结果。例如，医生看了检查报告说“可能××有炎症”，或围棋大师看到一个局面说“感觉不错”。

假设我们“认定”了一组输入和结果

![156230237\_5\_20190311050545207][156230237_5_20190311050545207]是一个问题的实例，就可能实现一个简单的求解程序(设x为输入)：

![156230237\_6\_20190311050545238][156230237_6_20190311050545238]

这个程序与前面类似，但本质不同。这里的实例可能只是所有可能实例中的一部分。

人们通常不满意这种“死记硬背”，希望推而广之，这样就需要“归纳”或“学习”。用计算机自动推广就是“机器学习”，也就是第三种方法——基于(实例)学习的求解方法，设法通过自动处理一些“情况-解”实例，得到一个能处理该问题的更多实例的系统。

用机器学习方法解决问题，需要设计一种具有可调整要素的(数据)结构S，一个(能利用实例调整S的)学习算法L，和一个使用S解决问题的算法U。对已有的实例集E，学习算法得到L(E, S) = S'，而U\[S'\] 就是利用调整后的结构解决问题的程序。学习算法L有效，首先要求将U\[S'\] 应用于E中的实例输入

![156230237\_7\_20190311050545285][156230237_7_20190311050545285]时，得到的结果近似于

![156230237\_8\_20190311050545301][156230237_8_20190311050545301]。

例如，多层神经网络是目前常用的一种结构，其中的可调整要素就是神经元之间的连接系数。针对这种结构，人们提出了一些学习算法，该结构的使用算法很简单。

复杂性使我们无法通过穷尽搜索的方法评价围棋棋局。以前人们利用专家知识做评价，主观而且不准确。AlphaGo的创新就在于通过机器学习自动产生评价函数。AlphaZero和AlphaGo的差异在于学习实例的来源，AlphaGo用历史上的围棋实战作为实例，AlphaZero用自对弈棋局作为实例。结合其他机制，Alpha系列程序取得了令人瞩目的战绩。

实际上，机器学习就是用某一类函数去“拟合”一组数据。数学抽象就是：有一组数据和一个函数类，设法找到能最好地表达这组数据的函数表示。图1是一个用线性和二次多项式拟合几个数据点的例子。那么，哪个结果更好地表达了数据中蕴含的关系呢？![156230237\_9\_20190311050545332][156230237_9_20190311050545332]

图1 线性和二次多项式拟合数据点示例

我们的目标是希望拟合得到的函数能用于处理其他实例。但是，目前对问题的理解只有这一组数据(而且数据可能有误差)，因此我们无法回答“哪一个更好”这个问题。

对具体的基函数组，可以设计一种评价标准(某种最小偏差)。而对这组数据的拟合，则无法确认这种标准。真正的标准应该来自问题，基于对被处理问题的全面理解。只有目前这组实例，不可能做出“正确”判断。即使拟合函数对现有数据都完全重合，也未必是最好的预测。例如，对4项数据可以做一个3次多项式，使之经过每个点。图2表示了拟合函数的情况。人们一般都不认为这个拟合更好。![156230237\_10\_20190311050545394][156230237_10_20190311050545394]

图2 多种拟合示例

对函数拟合的研究提出了两个重要情况。欠拟合：由于函数结构太简单，无法反映问题的重要特征，对应于机器学习中使用的结构过于简单。过拟合：函数类过于丰富，反映具体实例的过多细节，掩盖了目标问题的本质性特征，对应于机器学习中使用的结构过于复杂，导致结果函数震荡剧烈，降低了学习结果的预测能力。从有关函数拟合的讨论中，可以看到学习方法固有的局限性：由于没有对问题的完整理解，我们无法讨论学习结果的正确性，只能问得到的结果“好不好”，而“好不好”也只能通过实例来检验。

常见检验方法有两种：一种是在真实世界里检验，例如自动驾驶，只能在实际道路上试验，希望车辆不出事故、不撞车、不撞物撞人等。另一种方法是把已有实例分为不相交的两部分R = R1 ⊕ R2，其中的R1用于学习，R2用于检验学习效果。

实际上，基于学习的方法还有一些未说明的假设，只有在这些条件下，学习方法才可能有效：首先是假设问题实例和解的关系是连续的；其次是假设每个样本(实例和解)都必定包含了一些反映问题的整体性质的全局信息，因此样本越多越好，信息越多偏差越小。实际上，这些假定都是有疑问的。另外，在不理解问题的情况下，这些条件都无法检查。因此机器学习系统的设计和实现有很大的主观性和试探性，最后只能是“结果决定一切”。

基于(实例)学习系统的另一个缺点是学习代价可能很高。例如，AlphaGo采用超级计算机，学习中对弈超过3000万盘。AlphaGo Zero自对弈3天(约500万盘)，水平可超越之前的AlphaGo，自对弈30天可以超越后来的AlphaGo Master版本。由于围棋的特点，实例易得。但很多问题难以得到大量实例，采用这种技术路线的有效性存疑。

根据上面讨论，我们可以总结出适合用机器学习求解的问题的一些特点。首先，问题具有信息完全的场景(静态的、公开的)。一些棋类有这种性质，包括围棋，但许多问题不是这样。其次，存在(或容易得到)大量可用实例。围棋有很多积累，而且容易自动生成。再次，学习效果比较容易判断。例如围棋的胜负和统计可以作为评价。最后，由于学习结果的不可控性，机器学习慎用于安全攸关的应用(否则就需要其他安全措施)。

目前机器学习领域非常热，许多研究者和企业投入其中，也有一些原因：首先是做出了一些有影响的实例，特别是AlphaGo及其后续工作；再就是已经取得了一些成果，使人们看到一些用传统方法不能处理的问题有了新的解决途径。人类不清楚如何解决的问题大量存在，因此存在丰富的有可能用机器学习去探索的问题和应用领域。随着有关研究工作的开展，人们也开发出各种与神经网络类似或有些不同的模型，这些情况都推动着机器学习领域研究和应用的开展。另一方面，计算机能力增强也是机器学习取得进展的重要原因。

但学习方法属于试探性方法，类似于实验科学，与计算机科学技术的常规方法距离比较远。通过学习，从实例得到的结果能外推到什么程度，实际上是不清楚的。因此，机器学习方法更适合于那些只有优良程度要求(而非判定性要求)的应用。例如：要求精确结果的整函数通常无法学习，如斐波那契函数、最大公因子等。我们也应该注意机器学习的性质和本质弱点，避免可能的危害。

三种方法的比较和总结

从前提条件看：采用算法，需要有对问题及其求解的完整知识；采用搜索方法，需要有对问题及其求解的片段知识；采用学习方法，只需要问题和解的实例，无需其他知识。

从技术上看：算法只需要一个直面问题的解决方案；采用搜索，通过一个间接的搜索算法去应用有关问题的片段知识。学习方法需要一个结构和两个算法：一个具有可调要素的结构承载学习结果，一个利用实例调整该结构的算法和一个利用该结构处理实例的算法。

从效果看：正确的算法必定给出正确的解，求解效率可以预估，但也有复杂性太高的可能性。由于知识有限，搜索方法通常不能保证得到解，得到解的代价也很难预估，但有可能保证解的正确性。另一方面，搜索通常不能保证得到一个解。由于知识贫乏，我们只能说学习方法得到的结果可能有用，其他方面都没有保证。

可见，这三类方法各有各的前提条件、优势，以及固有的缺陷。遇到一个问题时，我们应该根据对问题的潜在认识程度、问题的实际需要等选择合适的求解方法。

请注意，为了简单起见，本文对各方面情况做了极度简化。实际应用这些方法时可能有很大变化，也完全可能在一个求解系统里融合了多种方法的要素，特此说明。

作者介绍裘宗燕![156230237\_11\_20190311050545473][156230237_11_20190311050545473]CCF杰出会员，CCF中小学计算机教育发展委员会委员。北京大学数学学院信息科学系教授(退休)。主要研究方向为软件理论、程序设计语言及其理论基础、形式化方法等。![156230237\_12\_20190311050545504][156230237_12_20190311050545504]

[156230237_1_2019031105054598]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_1_2019031105054598
[156230237_2_20190311050545113]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_2_20190311050545113
[156230237_3_20190311050545144]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_3_20190311050545144
[156230237_4_20190311050545176]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_4_20190311050545176
[156230237_5_20190311050545207]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_5_20190311050545207
[156230237_6_20190311050545238]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_6_20190311050545238
[156230237_7_20190311050545285]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_7_20190311050545285
[156230237_8_20190311050545301]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_8_20190311050545301
[156230237_9_20190311050545332]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_9_20190311050545332
[156230237_10_20190311050545394]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_10_20190311050545394
[156230237_11_20190311050545473]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_11_20190311050545473
[156230237_12_20190311050545504]: http://image109.360doc.com/DownloadImg/2019/03/1117/156230237_12_20190311050545504