5、图论模型建立.ppt

图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 图论建模 * 常州市第一中学 林厚从 信息学竞赛解题的一个重要步骤是数学建模，如几何模型、代数模型、运筹学模型等。图论模型的构造（图论建模）也是数学建模的一个分支。 在建立一个问题的模型之前，首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛而言，这一步大部分已经由命题者完成）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；然后用恰当的模型来描述这些要素及联系。 图论建模是指对一些客观事物进行抽象、化简，并利用图来描述事物特征及其内在联系的过程。建立图论模型的目的和建立其它数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或构造性问题；并且和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具。 图论模型和其它模型在研究方法上有着很大的不同，例如可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。 一般通过《数据结构》来学习图论，但它介绍的往往只限于图论的基本要素、基本概念、相关理论、经典算法等，至于如何建立图论模型，如何运用这些理论、算法来研究图论问题，都只有靠自己理解和领会，并通过大量实践来验证这些理解和感觉，通过摸索、总结来提高。 在建立图论模型的过程中，常常会遇到一些困难，例如难以建立顶点、边、权这些关系，或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽然能表示原型，但却无法求解等等。但最困难的还是很多题目拿到手后，无法想到要把问题转化成图论模型来求解，是“想不到”而不是“做不到”。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，多学习、多比较、多应用。 例1、奇怪的电梯（LIFT.???） 问题描述： 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1=i=N)上有一个数字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？ 输入： 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用1个空格隔开的正整数，表示Ki。 输出： 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。 样例输入： 5 1 5 3 3 1 2 5 样例输出： 3 [问题分析] 1、问题的数据规模只有200，所以很容易想到用有哪些信誉好的足球投注网站，由于要输出最优解（要求的是最快的次数）,所以是宽搜。 我们可以用一个集合记录上一层到达层，并用一个变量来储存集合中的个数，当某次有哪些信誉好的足球投注网站后，该变量值为0，那么可见以后的有哪些信誉好的足球投注网站也不会有新的层被加入，这就是输出“-1”的时候。 设：n是总层数,a是起始层,b是终止层, x是记录上层到达层数的个数； r,r1:set of 1..200; {记录上一次到达层的集合} k,s:array[1..200]of longint; {记录到达该层所需的次数} for i:=1 to n do s[i]:=maxlongint; s[a]:=0;r:=[a];x:=1; while (s[b]=maxlongint)and(x0) do {宽度优先有哪些信誉好的足球投注网站} begin x:=0;r1:=[]; for i:=1 to n do if i in r then {求出上一层的顶点，进行枚举} begin if (i+k[i]=n)and(s[i]+1s[i+k[i]])then {如果可以向上乘电梯} begin x:=x+1; s[i+k[i]]:=s[i]+1;