图论模型的建立幻灯片.ppt
《图论模型的建立幻灯片.ppt》由会员分享,可在线阅读,更多相关《图论模型的建立幻灯片.ppt(24页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图论模型的建立第1页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 图论建模是指对一些客观事物进行抽象、化简,并利图论建模是指对一些客观事物进行抽象、化简,并利用图来描述事物特征及其内在联系的过程。建立图论模型用图来描述事物特征及其内在联系的过程。建立图论模型的目的和建立其它数学模型一样,都是为了简化问题,突的目的和建立其它数学模型一样,都是为了简化问题,突出要点,以便更深入地研究问题的本质;它的求解目标可出要点,以便更深入地研究问题的本质;它的求解目标可以是最优化问题,也可以是存在性或构造性问题;并且和以是最优化问题,也可以是存在性或构造性问题
2、;并且和几何模型、运筹学模型一样,在建立图论模型的过程中,几何模型、运筹学模型一样,在建立图论模型的过程中,也需要用到集合、映射、函数等基本的数学概念和工具。也需要用到集合、映射、函数等基本的数学概念和工具。第2页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 图论模型和其它模型在研究方法上有着很大的不图论模型和其它模型在研究方法上有着很大的不同,例如可以运用典型的图论算法来对图论模型进行同,例如可以运用典型的图论算法来对图论模型进行求解,或是根据图论的基本理论来分析图论模型的性求解,或是根据图论的基本理论来分析图论模型的性质,这些特殊的算法和理
3、论都是其它模型所不具备的,质,这些特殊的算法和理论都是其它模型所不具备的,而且在其它模型中,能用类似于图这种直观的结构来而且在其它模型中,能用类似于图这种直观的结构来描述的也很少。描述的也很少。第3页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 一般通过一般通过数据结构数据结构来学习图论,但它介绍的往往只来学习图论,但它介绍的往往只限于图论的基本要素、基本概念、相关理论、经典算法等,限于图论的基本要素、基本概念、相关理论、经典算法等,至于如何建立图论模型,如何运用这些理论、算法来研究至于如何建立图论模型,如何运用这些理论、算法来研究图论问题,都
4、只有靠自己理解和领会,并通过大量实践来图论问题,都只有靠自己理解和领会,并通过大量实践来验证这些理解和感觉,通过摸索、总结来提高。验证这些理解和感觉,通过摸索、总结来提高。第4页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 在建立图论模型的过程中,常常会遇到一些困难,例在建立图论模型的过程中,常常会遇到一些困难,例如难以建立顶点、边、权这些关系,或是原型中的一些重如难以建立顶点、边、权这些关系,或是原型中的一些重要因素无法纳入现有模型,或是现有模型虽然能表示原型,要因素无法纳入现有模型,或是现有模型虽然能表示原型,但却无法求解等等。但最困难的还
5、是很多题目拿到手后,但却无法求解等等。但最困难的还是很多题目拿到手后,无法想到要把问题转化成图论模型来求解,是无法想到要把问题转化成图论模型来求解,是“想不到想不到”而不是而不是“做不到做不到”。为了克服这些困难,就需要用到某些。为了克服这些困难,就需要用到某些独特的思想、方法和技巧,多学习、多比较、多应用。独特的思想、方法和技巧,多学习、多比较、多应用。第5页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模例例1 1、奇怪的电梯(、奇怪的电梯(LIFTLIFT.?.?)问题描述:问题描述:呵呵呵呵,有有一一天天我我做做了了一一个个梦梦,梦梦见见了
6、了一一种种很很奇奇怪怪的的电电梯梯。大大楼楼的的每每一一层层楼楼都都可可以以停停电电梯梯,而而且且第第i i层层楼楼(1=i=N)(1=i=N)上上有有一一个个数数字字Ki(0=Ki=N)Ki(0=Ki=N)。电电梯梯只只有有四四个个按按钮钮:开开,关关,上上,下下。上上下下的的层层数数等等于于当当前前楼楼层层上上的的那那个个数数字字。当当然然,如如果果不不能能满满足足要要求求,相相应应的的按按钮钮就就会会失失灵灵。例例如如:3 3 3 3 1 1 2 2 5 5代代表表了了Ki(K1=3,K2=3,Ki(K1=3,K2=3,),从从一一楼楼开开始始。在在一一楼楼,按按“上上”可可以以到到4
7、4楼楼,按按“下下”是是不不起起作作用的,因为没有用的,因为没有-2-2楼。那么,从楼。那么,从A A楼到楼到B B楼至少要按几次按钮呢?楼至少要按几次按钮呢?输入:输入:输输入入文文件件共共有有二二行行,第第一一行行为为三三个个用用空空格格隔隔开开的的正正整整数数,表表示示N,A,B(1N200,N,A,B(1N200,1A,BN)1A,BN),第第二二行行为为N N个个用用1 1个个空空格隔开的正整数,表示格隔开的正整数,表示KiKi。输出:输出:输出文件仅一行,即最少按键次数输出文件仅一行,即最少按键次数,若无法到达,则输出若无法到达,则输出-1-1。样例输入:样例输入:5 1 55 1
8、 5 3 3 1 2 5 3 3 1 2 5样例输出:样例输出:3 3 第6页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 问题分析问题分析 1 1、问题的数据规模只有、问题的数据规模只有200200,所以很容易想到用搜索,由于要,所以很容易想到用搜索,由于要输出最优解(要求的是最快的次数)输出最优解(要求的是最快的次数),所以是宽搜。所以是宽搜。我们可以用一个集合记录上一层到达层,并用一个变量来储存我们可以用一个集合记录上一层到达层,并用一个变量来储存集合中的个数,当某次搜索后,该变量值为集合中的个数,当某次搜索后,该变量值为0 0,那么可见
9、以后的搜索也,那么可见以后的搜索也不会有新的层被加入,这就是输出不会有新的层被加入,这就是输出“-1-1”的时候。的时候。设:设:n n是总层数是总层数,a,a是起始层是起始层,b,b是终止层是终止层,x x是记录上层到达层数的个数;是记录上层到达层数的个数;r,r1:set of 1.200;r,r1:set of 1.200;记录上一次到达层的集合记录上一次到达层的集合 k,s:array1.200of longint;k,s:array1.200of longint;记录到达该层所需的次数记录到达该层所需的次数 第7页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚
10、从林厚从图论建模图论建模for i:=1 to n do si:=maxlongint;for i:=1 to n do si:=maxlongint;sa:=0;r:=a;x:=1;sa:=0;r:=a;x:=1;while(sb=maxlongint)and(x0)do while(sb=maxlongint)and(x0)do 宽度优先搜索宽度优先搜索 begin begin x:=0;r1:=;x:=0;r1:=;for i:=1 to n do if i in r then for i:=1 to n do if i in r then 求出上一层的顶点,进行枚举求出上一层的顶点,进
11、行枚举 begin begin if(i+ki=n)and(si+1si+ki)then if(i+ki=n)and(si+1=0)and(si+1=0)and(si+1si-ki)then 如果能向下乘电梯如果能向下乘电梯 begin begin x:=x+1;x:=x+1;si-ki:=si+1;si-ki:=si+1;r1:=r1+i-ki r1:=r1+i-ki end;end;end;end;r:=r1 r:=r1 end;end;if sbmaxlongint then writeln(sb)else writeln(-1);if sbmaxlongint then writeln
12、(sb)else writeln(-1);主要程序段如下:主要程序段如下:第8页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 问题分析问题分析 1 1、问题的数据规模只有、问题的数据规模只有200200,所以很容易想到用搜索,由于要输,所以很容易想到用搜索,由于要输出最优解(要求的是最快的次数)出最优解(要求的是最快的次数),所以是宽搜。所以是宽搜。2 2、对于、对于A A楼而言,实际上对它最多只能做楼而言,实际上对它最多只能做2 2个操作,上到个操作,上到A+XA+X层或下到层或下到A-XA-X层,当然前提是存在层,当然前提是存在A+XA+X
13、或或A-XA-X层。显然,如果把每一层。显然,如果把每一层楼看做一个顶点,如果层楼看做一个顶点,如果A A楼可以到楼可以到B B楼,则从顶点楼,则从顶点A A引一条到引一条到顶点顶点B B的边。对于样例,如下图:的边。对于样例,如下图:第9页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 问题分析问题分析 1 1、问题的数据规模只有、问题的数据规模只有200200,所以很容易想到用搜索,由,所以很容易想到用搜索,由于要输出最优解(要求的是最快的次数)于要输出最优解(要求的是最快的次数),所以是宽搜。所以是宽搜。2 2、对于、对于A A楼而言,实际
14、上对它最多只能做楼而言,实际上对它最多只能做2 2个操作,上到个操作,上到A+XA+X层层或下到或下到A-XA-X层,当然前提是存在层,当然前提是存在A+XA+X或或A-XA-X层。显然,如果把每一层层。显然,如果把每一层楼看做一个顶点,如果楼看做一个顶点,如果A A楼可以到楼可以到B B楼,则从顶点楼,则从顶点A A引一条到顶点引一条到顶点B B的边。对于样例,如下图:的边。对于样例,如下图:这样一来,问题就变成了图论中的两顶点间最短路径问题这样一来,问题就变成了图论中的两顶点间最短路径问题了!我们只要套用了!我们只要套用FLOYDFLOYD算法等编程就可以了,当然权要设为算法等编程就可以了
15、,当然权要设为1 1。第10页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模例例2 2、渡河问题(、渡河问题(riverriver)一个人一个人带带了一只狼、一只羊和一棵白菜想要了一只狼、一只羊和一棵白菜想要过过河,河上有一只独木船,每次除了人以外,河,河上有一只独木船,每次除了人以外,只能只能带带一一样东样东西。另外如果人不在旁西。另外如果人不在旁边时边时狼就要吃羊,羊就要吃白菜。狼就要吃羊,羊就要吃白菜。问问:应该应该怎怎样样安排渡河,安排渡河,才能做到既把所有才能做到既把所有东东西西带过带过河,在河上来回的次数又最少呢?河,在河上来回的次数
16、又最少呢?问题分析问题分析我们用变量我们用变量M代表人、代表人、W代表狼、代表狼、S代表羊、代表羊、V代表白菜,代表白菜,代表空(什代表空(什么都没有)。开始时设人和所有东西都在左岸,这种情况用么都没有)。开始时设人和所有东西都在左岸,这种情况用MWSV表示。表示。我们用一个集合表示目前左岸的情况,很明显,可能出现我们用一个集合表示目前左岸的情况,很明显,可能出现16种情况:种情况:MWSVMWSMWVMSVWSVMWMSMVWSWVSVMWSV 但要剔除掉但要剔除掉6 6种可能发生狼吃羊和羊吃白菜的情况(红色),实际是种可能发生狼吃羊和羊吃白菜的情况(红色),实际是1010种。下面我种。下面
17、我们就把这们就把这1010种情况作为种情况作为1010个顶点,来构造一个无向图个顶点,来构造一个无向图G G,图,图G G的边按下列原则来定义:的边按下列原则来定义:如果经过一次渡河,情况甲能变成情况乙,那么就在情况甲与情况乙之间连一条如果经过一次渡河,情况甲能变成情况乙,那么就在情况甲与情况乙之间连一条边。得到下图:边。得到下图:第11页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模 这样,问题的解就归结为:在图这样,问题的解就归结为:在图G G中找一条连接顶点中找一条连接顶点MWSVMWSV和和,且包含边数,且包含边数最少的路了!把所有边的权
18、值(长度)都看成最少的路了!把所有边的权值(长度)都看成1 1,则渡河问题就归结为:找一条,则渡河问题就归结为:找一条连接连接MWSVMWSV和和的最短路径。的最短路径。第12页,共24页,编辑于2022年,星期五常州市第一中学常州市第一中学 林厚从林厚从图论建模图论建模例例3 3、奶牛排队、奶牛排队(queue.?,usaco1995(queue.?,usaco1995决赛决赛)问题描述:问题描述:一天一天,农夫农夫JOHNJOHN带着他的带着他的1919头最好的奶牛从牛场出发去赶集头最好的奶牛从牛场出发去赶集,奶牛可以分为两种奶牛可以分为两种:全黑的(全黑的(B B)或全白的()或全白的(
19、W W)。当奶牛排成一列经过他的家门时,他的妻子发现四头黑白奶牛)。当奶牛排成一列经过他的家门时,他的妻子发现四头黑白奶牛的所有的所有1616种组合(例如种组合(例如:BBBB,BBBW,BBWB,:BBBB,BBBW,BBWB,WWWW,WWWW),作为子序列在队列中都出现了作为子序列在队列中都出现了,当然当然,这些子序列之间可能有重叠。这些子序列之间可能有重叠。任务任务1:1:打印出一组这打印出一组这1919头黑白奶牛的可能的排列顺序,使得它包含所有四头奶头黑白奶牛的可能的排列顺序,使得它包含所有四头奶牛的组合。输出在文件的第牛的组合。输出在文件的第1 1行中,每个奶牛编号之间用一个空格隔
20、开。行中,每个奶牛编号之间用一个空格隔开。任务任务2:2:输入子序列的长度和奶牛的头数输入子序列的长度和奶牛的头数,打印出一组奶牛的可能排列打印出一组奶牛的可能排列,使得它包含全部使得它包含全部的可能子序列。例如子序列的长度和奶牛的头数可以是:的可能子序列。例如子序列的长度和奶牛的头数可以是:2 2和和5;35;3和和10;410;4和和19;519;5和和36;36;,奶牛的头数不会超过,奶牛的头数不会超过32782,32782,子序列的长度不超过子序列的长度不超过15,15,而且保证至少存在一个解。而且保证至少存在一个解。输入在一行中,两个数之间用一个空格隔开;输出在文件的第输入在一行中,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模型 建立 幻灯片
限制150内