算法合集之数学模型及其在信息学竞赛中的应用.doc

数学模型及其在信息学竞赛中的应用 上海市复旦附中高三（8）班 郭一 【关键字】 数学模型，可靠性，可解性 【引言】 数学模型是人们解决现实问题的有力武器。人们把现实问题经过科学地抽象、提炼得到数学模型，再用数学方法去解决。数学模型可分为离散和连续两种。连续数学模型需要大量的高等数学知识，中学生很少接触。在信息学竞赛经常出现的则是离散数学模型。本文主要介绍的就是离散数学模型的一般概念及建立方法 【正文】 所谓数学模型，就是现实世界中某一类特殊的运动变化过程、关系或结构的一种模拟性的数学结构，其实也就是对现实模型进行科学抽象后得到的模型。在信息学竞赛中，试题给出的问题通常是一个现实问题，这也就需要选手在审清题意后首先把问题的关键因素总结、提炼出来，形成一个抽象的数学模型，这样有利于问题的分析与解决。 一般来说，我们在解一道有关现实问题的试题时，需要分以下几个步骤： 审清题意，了解题目的来龙去脉，弄清哪些量是已知的（输入），需要求什么（输出），数据规模如何等等。这是解决问题的前提。 建立模型，使之能够简洁高效地表达出题目给出的现实模型。 解决模型，得出算法。建模之后就是要解决模型。这步顺利与否很大部分上取决于所建模型的可解性如何。 编程实现。 其中，２、３两步是关键。模型建立与解决得好与坏对能否成功解决该题起着决定性的作用。 对于同一个现实问题，可能可以建立不同的数学模型 这种现象十分普遍，也就是平时所说的一题多解。既然如此，这里有必要讨论一下数学模型的选择问题，其实也就是评判一个模型好坏标准的问题。一个好的数学模型不仅要能够准确地反映出现实模型（可靠性），所建立的模型还必须能够被有效地解决（可解性）。这里“有效”指的是解决它的算法所需的空间与时间都在可以承受的范围之内。通常在解一些要求最优解或要求准确计数的一类具有唯一正确解的试题时，我们一般在保证可靠性的前提下，尽量提高模型的可解性。若几个模型都具有可靠性，则当然可解性越强的模型越好。 例： 最佳旅行路线问题 [IOI’93] 【问题描述】你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市出发，单方向从西向东经若干城市到达最东的一个城市（必须到达最东的城市）；然后再单方向从东向西飞回起点（可途径若干城市）。除起点城市外，任何城市只能访问１次，起点城市被访问２次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。 这是一个现实问题，我们首先可以做如下的抽象：把每个城市抽象成一个顶点。不妨设由西到东的城市对应编号分别是1至n。若两个城市之间有直通航线，则在相应的两点之间连一条边。这样，所有城市与直通航线就被抽象成了一个无向图。 【盲目有哪些信誉好的足球投注网站】这是最原始的想法。我们一开始假想有两架飞机都从最西边的城市飞向最东边的城市，并且在有哪些信誉好的足球投注网站的过程中保证两条路线中的城市除起点与终点外都不相同。记下所有找到的路线中所经城市最多的方案，把其中的一条作为向东旅行的路线，一条作为向西旅行的路线，合并起来即得最佳旅行路线。 因为有哪些信誉好的足球投注网站的时间复杂度是指数级的，所以这样做的话，时间效率不够理想。究其主要原因就是所有模型的抽象程度不够，没有把试题中的限制充分融入数学模型中，盲目性太大。 【网络流模型】为了把更多的试题中的限制融入模型中，我们在原有的模型的基础上建立了如下的最大费用最大流的模型： 为了保证每个城市最多只能被访问一次，我们把每个城市i拆成两个顶点i和i’，并在两个顶点之间连接一条i至i’的有向弧，单位费用设为0。 将原图中的无向边改为有向弧：若城市i到城市j有直通航线（ij），则在顶点i’与顶点j之间连接一条弧，方向由顶点i’至顶点j，容量为1，这样可以保证这条航线最多只能通过一次；费用为(j-i+1)，表示这条航线从西至东飞过的城市数（包括起点和终点）。这样使得我们能够简单地从流量费用算出旅行路线上经过的城市数。 顶点1与1’，n与n’之间的弧的容量为2。 至此，本题的数学模型已经建立，试题给出的限制条件已体现在数学模型中，因此由此模型得出的解是可行的。我们求从1到n’的最大费用最大流。若得到的最大流量不是2，则无解（即不可能从西飞到东再飞回来），否则我们设得到的最大费用为C。因为有两条路线，所以每个未被访问的城市在费用中的贡献为2，被访问的城市的贡献为3。考虑到最西最东两个城市的贡献是2而不是3，旅行路线中访问城市数=C+2-2*N。因为C最大，所以访问城市数也一定最