下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
..应用一图论算法图论在计算机处理问题中占有重要地位,现实中的很多问题最终都可以转化成图论问题,或者要借助图结构来存储和处理。但是怎么把一张图存入计算机就要涉及到数学建模的知识。比如下面一张图:如果要求出从节点v1到节点v5的所有路径,就可以借助计算机来很轻松的解决。但前提条件是,必须要把图以一种计算机可以理解的形式存进去,即要把它抽象为数学问题。在此,我们需要定义一些关于图的概念,以便更好的描述问题。边与顶点的关系有如下几种典型情况:简单图:无自回环,无重边的图。无向图:边没有指向,此时称边与顶点关联,称顶点与顶点邻接。有向图:边有指向,下面是具体涉及到图如何存储的问题:图G<V,E>的关联矩阵,若G<V,E>为无向图,若G<V,E>为有向图,因此该图可以用关联矩阵表示出来,如下所示这样,我们就可以以矩阵的形式将图存入计算机邻接矩阵图G<V,E>的邻接矩阵,若G<V,E>为无向图,=从到的边数,若不邻接,取0;若G<V,E>为有向图,=从到的有向边数,若无,取0.应用二动态规划问题动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。也是信息学竞赛中选手必须熟练掌握的一种算法。多阶段决策过程的最优化问题。含有递推的思想以及各种数学原理〔加法原理,乘法原理等等。动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。举例线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并,加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶。多阶段决策的实际问题很多,下面通过具体例子,说明什么是动态规划模型中数学建模知识的运用。最短路线问题:某工厂需要把一批货物从城市A运到城市E,中间可经过B1、B2、B3、C1、C2、C3、D1、D2等城市,各城市之间的交通线和距离如下图所示,问应该选择一条什么路线,使得从A到E的距离最短?C1BC1B13D18D1AB2564AB2EC298EC272D36D3671C3BC3B37下面引进几个动态规划的基本概念和相关符号。<1>阶段<Stage>把所给问题的过程,按时间和空间特征划分成若干个相互联系的阶段,以便按次序去求每个阶段的解,阶段总数一般用字母n表示,用字母k表示阶段变量。如例中<最短路线问题>可看作是n=4阶段的动态规划问题,k=2表示处于第二阶段。<2>状态<State>状态表示每个阶段开始时系统所处的自然状况或客观条件,它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量,常用字母sk表示第k阶段的状态变量,状态变量的取值范围称为状态集,用Sk表示。如例l中,第一阶段的状态为A〔即出发位置。第二阶段有三个状态:B1、B2、B3,状态变量s2=B2表示第2阶段系统所处的位置是B2。第2阶段的状态集S2={B1、B2、B3}。动态规划中的状态变量应具有如下性质:当某阶段状态给定以后,在这个阶段以后过程的发展不受这个阶段以前各个阶段状态的影响。也就是说,未来系统所处的状态只与系统当前所处的状态有关,而与系统过去所处的状态无关,即过去历史只能通过当前的状态去影响它未来的发展,这种特点称为无后效性〔又称马尔可夫性。如果所选定的状态变量不具备无后效性,就不能作为状态变量来构造动态规划模型。如例1中,当某阶段的初始状态即所在的城市选定以后,从这个状态以后的运货路线只与这个城市有关,不受以前的运货路线影响,所以是满足状态的无后效性的。〔3决策<Decision>当系统在某阶段处于某种状态,可以采取的行动〔或决定、选择,从而确定下一阶段系统将到达的状态,称这种行动为决策。描述决策的变量,称为决策变量。常用字母uk<sk>表示第k阶段系统处于状态sk时的决策变量。决策变量的取值范围称为决策集,用Dk<sk>表示。在例l的第二阶段中,若从状态B2出发,可以做出三种不同的决策,其允许的决策集为D2<B2>={C1、C2、C3},决策u2<B2>=C2表示第二阶段处于状态B2,选择的确行动下一阶段是走到C2。〔4策略<Policy>系统从第k阶段的状态sk开始由每阶段的决策按顺序组成的决策序列{uk<sk>,uk+1<sk+1>,…,un<sn>}称为一个策略〔k=1,2,…,n,记作。在例l中,p2,4<B2>={u2<B2>=C2,u3<C2>=D1,u4<D1>=E}是一个策略,表示第二阶段从状态B2出发,沿着B2→C2→D1→E的方向走到终点。注意策略必须是一串实际可行的序列行动。〔5状态转移方程系统由这一阶段的—个状态进行决策后转变到下—阶段的另—个状态称为状态转移,状态转移既与状态有关,又与决策有关,描述状态转移关系的方程称为状态转移方程,记为:sk+1=Tk<sk,uk>它的实际意义是当系统第k阶段处于状态sk做决策uk时,第k+1阶段系统转移到状态sk+1。状态转移方程在不同的问题中有不同的具体表现形式,在例l中,状态转移方程表示为:sk+1=uk<sk>。〔6阶段指标阶段效益是衡量系统阶段决策结果的一种数量指标,记为:表示系统在第k阶段处于状态sk做出决策uk时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例l中它表示两个中转站的距离,如表示从中转站B2走到中转站C2之间的距离为7。更一般地有。〔7指标函数指标函数是用来街量所实现过程的优劣的一种数量指标,它是一个定义在全过程和所有后部子过程上的确定的数量函数,记为:它应具有可分离性,并满足递推关系式:常见的指标函数的形式是:1过程和任一子过程的指标是它所包含的各阶段指标的和。既2过程和任一子过程的指标是它所包含的各阶段指标的积。既〔8最优值函数指标函数的最优值,称为最优值函数,记为。它表示系统在第k阶段处于状态sk时按最优策略行动所获得总的效益。既其中opt是最优化〔optimization的缩写,根据实际问题可取max<最大值>和min<最小值>,表示对所有允许策略使后面算式取最优。下面利用动态规划的逆推归纳法,将例1从最后一个城市E逐步推算到第一个城市A,在此表示第k阶段从城市sk到城市E最短路。1>当k=4时:要求,由于第4阶段只有两个城市D1、D2〔即s4的取值为D1、D2,从D1到E只有一条路,故,同理。2>当k=3时:s3的取值为C1、C2、C3,从C1出发到E有两条路,一条是经过D1到E,另一条是经过D2到E,显然:即从C1出发到E的最短路为7,相应决策为,最短路线是C1→D1→E。同理2>当k=2时:s2的取值为
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论