数学模型及其在信息学竞赛中的应用（2000国家集训队 郭一）

数学模型及其在信息学竞赛中的应用

上海市复旦附中高三（8）班 郭一

【关键字】

数学模型，可靠性，可解性

【引言】

数学模型是人们解决现实问题的有力武器。人们把现实问题经过科学地抽象、提炼得到数学模型，再用数学方法去解决。数学模型可分为离散和连续两种。连续数学模型需要大量的高等数学知识，中学生很少接触。在信息学竞赛经常出现的则是离散数学模型。本文主要介绍的就是离散数学模型的一般概念及建立方法。

【正文】

所谓数学模型，就是现实世界中某一类特殊的运动变化过程、关系或结构的一种模拟性的数学结构，其实也就是对现实模型进行科学抽象后得到的模型。在信息学竞赛中，试题给出的问题通常是一个现实问题，这也就需要选手在审清题意后首先把问题的关键因素总结、提炼出来，形成一个抽象的数学模型，这样有利于问题的分析与解决。

一般来说，我们在解一道有关现实问题的试题时，需要分以下几个步骤：

１．审清题意，了解题目的来龙去脉，弄清哪些量是已知的（输入），需要求什么（输出），数据规模如何等等。这是解决问题的前提。 ２．建立模型，使之能够简洁高效地表达出题目给出的现实模型。 ３．解决模型，得出算法。建模之后就是要解决模型。这步顺利与否很大部分上取决于所建模型的可解性如何。 ４．编程实现。

其中，２、３两步是关键。模型建立与解决得好与坏对能否成功解决该题起着决定性的作用。

（一）对于同一个现实问题，可能可以建立不同的数学模型

这种现象十分普遍，也就是平时所说的一题多解。既然如此，这里有必要讨论一下数学模型的选择问题，其实也就是评判一个模型好坏标准的问题。一个好的数学模型不仅要能够准确地反映出现实模型（可靠性），所建立的模型还必须能够被有效地解决（可解性）。这里“有效”指的是解决它的算法所需的空间与时间都在可以承受的范围之内。通常在解一些要求最优解或要求准确计数的一类具有唯一正确解的试题时，我们一般在保证可靠性的前提下，尽量提高模型的可解性。若几个模型都具有可靠性，则当然可解性越强的模型越好。

例： 最佳旅行路线问题 [IOI’93]

【问题描述】你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市出发，单方向从西向东经若干城市到达最东的一个城市（必须到达最东的城市）；然后再单方向从东向西飞回起点（可途径若干城市）。除起点城市外，任何城市只能访问１次，起点城市被访问２次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。

这是一个现实问题，我们首先可以做如下的抽象：把每个城市抽象成一个顶点。不妨设由西到东的城市对应编号分别是1至n。若两个城市之间有直通航线，则在相应的两点之间连一条边。这样，所有城市与直通航线就被抽象成了一个无向图。

【盲目搜索】这是最原始的想法。我们一开始假想有两架飞机都从最西边的城市飞向最东边的城市，并且在搜索的过程中保证两条路线中的城市除起点与终点外都不相同。记下所有找到的路线中所经城市最多的方案，把其中的一条作为向东旅行的路线，一条作为向西旅行的路线，合并起来即得最佳旅行路线。

因为搜索的时间复杂度是指数级的，所以这样做的话，时间效率不够理想。究其主要原因就是所有模型的抽象程度不够，没有把试题中的限制充分融入数学模型中，盲目性太大。

【网络流模型】为了把更多的试题中的限制融入模型中，我们在原有的模型的基础上建立了如下的最大费用最大流的模型：

1）为了保证每个城市最多只能被访问一次，我们把每个城市i拆成两个顶

点i和i’，并在两个顶点之间连接一条i至i’的有向弧，单位费用设为0。

2）将原图中的无向边改为有向弧：若城市i到城市j有直通航线（i

则在顶点i’与顶点j之间连接一条弧，方向由顶点i’至顶点j，容量为1，这样可以保证这条航线最多只能通过一次；费用为(j-i+1)，表示这条航线从西至东飞过的城市数（包括起点和终点）。这样使得我们能够简单地从流量费用算出旅行路线上经过的城市数。 3）顶点1与1’，n与n’之间的弧的容量为2。

至此，本题的数学模型已经建立，试题给出的限制条件已体现在数学模型中，因此由此模型得出的解是可行的。我们求从1到n’的最大费用最大流。若得到的最大流量不是2，则无解（即不可能从西飞到东再飞回来），否则我们设得到的最大费用为C。因为有两条路线，所以每个未被访问的城市在费用中的贡献为2，被访问的城市的贡献为3。考虑到最西最东两个城市的贡献是2而不是3，旅行路线中访问城市数=C+2-2*N。因为C最大，所以访问城市数也一定最多，即方案最佳，模型具有可靠性。因为这是一个最大费用最大流的问题，我们可以使用Ford-Fulkerson算法去解。

这个模型与搜索相比，可解性大大提高，时间复杂度从指数级降低到了多项式级（大约为O（N^3））。但我们还是觉得这个模型不够简洁，抽象程度还是不够。

【动态规则模型】设f[i,j]为从顶点1出发的两条不相交的路线分别到达顶点i与顶点j时，两路线的所需乘航线之和的最大值。有两种情况，若i>j，或i=j=n时，我们考虑i的前趋顶点，不妨设为k。此时，到达顶点k与j的两条路线的所需乘航线之和也一定最大，否则与f[i,j]最大矛盾。若i

f[1,1]?0?Min?f?k,j???1(i?j或i?j?n)?k?i且(k,i)?Ef[i,j]???Min?f?i,k???1(i?j)?k?j且(k,j)?E f [i, i] 无意义 (1

实际最多可能的访问城市数为f [n,n]-2。时间复杂度降为O（N^2）。

对于最佳旅行路线这一个问题，我们建立了三种不同的数学模型。这三种模型都具有可靠性（可以得出最优解），但可解性不同。一般来说，建立的模型越简洁，抽象程度越高，算法实现时不必要的操作也越少，运行效率也就越高。

值得注意的是，最近的一些竞赛中有时会出现根据解的近似程度给分的题目。对于这类题目，我们更多考虑的则是所建模型的可解性。当然，可靠性的降低也是有限度的，这个限度就是方案的可行性及误差允许范围。此外，许多数学模型有近似解法，这些都是通过适当牺牲模型自身可靠性来提高模型的可解性。

（二）一个模型可能同时适用于多个现实问题。

这也就是我们要研究数学模型的主要原因之一。我们解决一个数学模型就相当于解决了一类问题。比如说，最短路径问题，可谓在现实生活中无处不在，上文中提到的网络流的模型也有着很高的实用价值。这些数学模型的解决使得许多实际问题迎刃而解。然而，数学模型的解决只是解决一个现实问题的

一半，另一半就是如何将现实问题转化为一个已经解决的数学模型，即如何建模。建模在现实与抽象之间起着桥梁的作用。尤其在竞赛中，后者有时显得更为重要。

（三）如何建立数学模型？

要能够建立数学模型，首先必须熟悉一些经典的数学模型及其算法。这是建模的基础，没有这个基础则根本谈不上建立什么数学模型。竞赛中许多问题最终都可以转化为经典的数学模型，因此必须掌握这些常见的模型。

其次建立数学模型需要选手有把实际问题相互联系，类比的能力。上文已经指出许多实际模型都有着相同或相似的数学模型。既然这样，它们之间必然存在着一些相同或相似。相互联系、类比是发掘这些信息的有效手段。这里先给出一个大家都很熟悉的模型：

【凸n边形分割】一个凸n边形，可以通过不相交的(n-3)根对角线，把n边形拆分成(n-2)个三角形。求方案数hn。当n=5时，方案数h5=5。

【配对括号序列】求由n个左括号‘(’，n个右括号‘)’，能组成多少种不同的配对括号序列，记作Qn。一个序列的配对与否定义如下： 1．（）是配对的。 2．若A是配对的，则(A)也是配对的。

3．若A、B都是配对的，则AB也是配对的。

这两题的模型都是大家十分熟悉的Catalan数Cn=1/(n+1)*C(2n,n)。通过数学计算可知，hn=Cn-2，Qn=Cn（证明略）。

【结和律】有n个数a1,a2,a3,…,an依据加法结合律，不改变其顺序，只用括号表示成对的和，问有几种求和方案Pn？

因为题目只要求求配对方案数，与a1,a2,a3,…,an的值无关。我们不妨令S=a1+a2+a3+…+an，并把ai（0<=i<=n）当成矢量（矢量加法也有结合律）。如下图。这样本题的方案与上题的方案就建立了一一对应的关系，本题的结果也就可以很容易地用Catalan数表示出来。Pn=hn+1=Cn-1。

【二叉树计数】问有n个结点的二叉树共有几种？

本题其实可以与【配对括号序列】联系。考虑从根结点开始中序遍历一个二叉树的过程。每当第一次到达一个结点时，将该结点压栈，记作‘(’，并开始递归访问其左子树；返回时访问该结点，并将该结点出栈，记作‘)’，再递归访问其右子树。这样一个二叉树就对应与一个配对的括号序列。反过来，根据任何一个配对的括号序列，我们都可以画出与其惟一对应的二叉树（证明略）。这样一来，每个结点都要出入栈一次，所以序列中一共有n对括号。即n个结点的二叉树共有Qn=Cn种。

本文来源：https://www.bwwdw.com/article/00fh.html