基干Dijkstra最短路径算法教育装备更新问题.docVIP

基于Dijkstra最短路径算法的教育装备更新问题 　　摘 要 随着教育水平的不断提升，教育领域教育装备的投入步伐大大加快，设备的更新换代越发频繁。为了最大限度发挥教育装备的功能，保障优质教学，学校每年都要对教育装备进行更新与维护且使总费用最小化。首先建立教育装备更新数学模型，阐明如何更新教学中的设备使总费用最小化，并采用Dijkstra最短路径算法实现教育装备的更新 关键词 教育装备更新；最短路径；Dijkstra算法 中图分类号：G650 文献标识码：A 文章编号：1671-489X（2016）16-0001-03 随着计算机技术和教育信息化的发展，具有先进技术含量的教育装备在教育教学中得到广泛应用，教育装备的分配、管理、购置和维修等问题也随之变得更为复杂。先进的教育装备不仅能为学校提供良好的教学环境和丰富的教学资源，还能锻炼学生的实践能力和创新思维。因此，在当前的教育教学中，先进的教育装备已逐渐成为教学过程中不可或缺的重要条件 教育装备必须经历一个管理知识量化的过程，才能从经验管理向科学管理过渡，使得管理工作成为可预测、可测量、可重复、可控制的科学管理过程[1]。为此，就必须把管理学、运筹学等理论和方法引入教育装备管理中来，以科学方法解决实际问题。目前我国的经济发展水平和社会发展阶段共同决定了下发到各个学校的教育经费的有限性，在满足日常的教育需求和科研工作的前提下，学校要考虑教育装备的更新成本以及继续使用旧装备的维修费用等问题，尽可能地压缩教育装备的更新费用是教育装备管理工作中面临的难题。本文以解决教育装备更新问题为切入点，应用基于Dijkstra的最短路径算法实现其总费用最小化的求解，为教育装备资源分配工作提供科学依据 1 算法的基本概念 图论的起源可以追溯到瑞士数学家（E.Euler）在1736年发表的一篇解决“哥尼斯堡七桥问题”的论文。在自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图来描述[2]。随着现代生产和科学技术的迅猛发展，特别是计算机的出现和互联网的普及，使图论方法得以快速扩展，图论已成为运筹学中引人注目的重要分支，渗透到物理学、化学、电工学、管理学、控制论、信息论等诸多学科[3-4] 最短路径问题是图论中应用最广泛的问题之一。许多实际问题求最优解可以使用这个模型，如设备更新、管道铺设、选址布局等。所谓最短路径是指在一个连通图中，求从某一个指定结点（起始点）到另一个指定结点（终点）的距离最短的路径，即：寻求赋权图中任意两点之间的最短路径。这里的最短路径只是图中边权数的代名词，在解决实际问题时，它可以是时间、费用等其他不同含义的量[5] Dijkstra算法是解决最短路径问题的常用算法之一，适用于所有权wij≥0情况下求指定两点间的最短路径，目前已经被广泛应用。在这里可以把教育装备更新问题抽象为赋权有向图，利用Dijkstra算法进行求解，从而得到某段时间内总费用最少的路径，为教育装备的更新提供最优化方法 图的相关概念 1）图（Graph），即偶对（V，E），记作G（V，E）。其中，V是顶点（Vertex）的集合，E是边的集合 2）有向图（Digraph），即有序偶对（V，E），记作D=（V，A）。其中，V是顶点（Vertex）的集合，A是弧的集合。换言之，有向图就是所有边都具有一定方向的图 3）赋权图（Weighted graph），即在图G（V，E）中，每一条边（vi，vj）均有一个数wij与之对应，数wij即为边（vi，vj）的权值 4）连通图（Connected graph）：设vi和vj为图G中的两个点，若存在从点vi到点vj的链，则称vi和vj是连通 的；若图G中的任意一对顶点均连通，则图G被称为连通图 Dijkstra算法的基本思想 Dijkstra算法的基本思路是把图中的全部顶点分为两组，令V表示已标记最短路径的顶点集合，其余未标记最短路径的顶点集合为V；初始状态时，集合V中只含有起始点s，V中含有除起始点s之外的其余各顶点，此时各顶点的当前最短路径为起始点到该节点的弧上的权值；然后不断地从集合V中选取到顶点集V中各顶点的路径长度最短的顶点u加入到集合V中，集合V中每加入一个新的顶点u，都要分别修改已标记集合V和未标记集合V中的顶点。集合V中各顶点新的最短路径长度值为原来的最短路径长度值加上u到该顶点的路径长度值中的较小值。重复此过程，直到集合V包含图中所有顶点（即所有顶点都被标记）为止 定义dij是图中顶点i和j之间的距离，即： 给定赋权有向图D=（V，A），采用Dijkstra算法求从起始点s到终点t的最短路径的具体步骤如下 1）从起始点s出发，每个节点都进行标记，记作Lij；其中Lij