《基于最短路径问题在企业设备更新中的应用》由会员分享，可在线阅读，更多相关《基于最短路径问题在企业设备更新中的应用（4页珍藏版）》请在金锄头文库上搜索。
1、基于最短路径问题在企业设备更新中的应用摘要：介绍通过应用书本中最短路径的算法，来解决企业中设备的更新换代问题。文中给出了企业设备更新中的数学模型，举例说明了如何更新企业中设备，使得企业的投入最小，即最大限度地减少企业的成本。本例也说明了用数据结构中的算法在解决实际问题中的应用是十分广泛、重要的。关键词：最短路径；Dijkstra 算法;企业设备更新1. 问题的提出1.1 问题的实质设备更新问题。某企业使用某种设备，在每年的年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备
2、更新计划，使得总的支付费用最少。1.2 问题的意义由于现代企业竞争形势的日益严峻，使得企业要降低生产成本，以取得最大限度利润。而生产材料价格的透明化、生产力成本的固定化，迫使企业从生产设备着手来考虑生产成本的问题。设备更新问题，这对一个单位、公司来说是一笔较大的资金，所以如何使设备每年的投入最少，这是一个最短路径问题，该问题可以使用 Dijkstra 算法来解决。1.3 问题的分析在带权连通平面图中求最短路径，是图论的基本问题之一，在实际的工作中具有很重要的意义。对该问题的两个比较典型的算法是 Dijkstra 算法。由于 Dijkstra 算法适合于较为复杂的带权连通图，所以在本文中应用了最
3、短路径求解中的 Dijkstra 算法，来解决如何以最低的代价换取最大的经济利润。2.算法的基本概念2.1 Dijkstra 算法基本思想把顶点集 V 分为两组，令 S 表示已求出最短路径的顶点集合为第一组，其余尚未确定最短路径的顶点集合 T 为第二组。初始状态时，集合 S 中只包含源点 V，T 中含除源点之外的其余顶点，此时各顶点的当前最短路径长度为源点到该结点的弧上的权值。然后不断从集合 T 中选取到顶点 V 路径长度最短的顶点 u 加入到集合 S 中，集合 S 中每加入一个新的u，都要修改顶点 V 到集合 T 中剩余顶点的最短路径长度的值，集合 T 中各顶点新的最短路径长度值为原来的最短
4、路径的值加上 u 到该顶点的路径长度值中的较小值。重复此过程，直到集合 T 中的顶点全部加入集合 S 为止。2.2 Dijkstra 算法实现过程假设用带权的邻接矩阵 arcs 表示带权有向图，arcsij表示弧上的权值。若不存在，则置为(在计算机上可用允许的最大值代替)。S 为已找到从 v出发的最短路径的终点的集合，它的初始状态为空集。那么，从 v 出发到图上其余各顶点(终点)v i可能达到的最短路径长度的初值为：Di=arcsLoacate Vex(G,v)i v iV。选择 vj,使得 Dj=MinDi| vV-S，v j就是当前求得的一条从 v 出发的最短路径的终点，令 S=Sj。修改
5、从 v 出发到集合 V-S 上任一顶点 vk可达的最短路径长度。Dj+arcsjkDK+W(K, j),则 Dj=DK+W(K,j)，否则不改变 Dj的原来值。若 T=V-S 为空，或 T=V-S 中顶点的 Dj全为终止，否则继续。3.3 算法实现输入：顶点数；各顶点之间的路径值。输出：最优方案，包括起始顶点、中间顶点、终止顶点及顶点之间的路径值之和。方法：SN为布尔向量，当 i 号顶点纳入时 Si=TRUE；Di初值为源点 s 到其它各顶点的直接距离。1）输入顶点数：6；2）再输入边数：15；3）然后输入每条边的起点、终点及对应权值；4）最后输入源点序号。此过程为一个程序，其功能是：输入 n
6、 年年初设备的价格与使用不同时间（年）的设备所需要的维修费用，为该企业领导部门确定一个方案使得在 n 年内为这台机器支付的总费用最少。3.4 运行结果及说明最后求得V 1，V 3，V 6及V 1，V 4，V 6均为最短路径。即有两个最优方案：一个方案是第 1 年、第 3 年各购置一台新设备。4.计算复杂度分析通过该算法编写的程序已经在 Microsoft Visual C+6.0 的运行环境下编译通过，并运行成功，得出的结果与预期的相同，有两条备选方案。第一个循环的时间复杂度是 O(n)，第二个循环共进行 n-1 次，每次执行的时间是 O(n)。所以总的时间复杂度是 O(n2)。如果用带权的邻
7、接表作为有向图的存储结构，则显然修改 D 的时间可以减少，但由于在 D 向量中选择最小分量的时间不变，所以总的时间仍为. O(n2)。5.结语Dijkstra 算法总是做出在当前看来最好的选择，也就是说该算法并不是从整体上的最优考虑，它做出的选择只是在某种意义上的局部最优选择，但最终能得到整个问题的最优解。Dijkstra 算法不仅仅应用于企业设备更新问题，还可应用于其他很多地方，例如：网线和电线的辅设、管道的辅设等，用此算法都可以得到最优的布线路径，达到省时、省料、省力的目的。从此算法也可以看出，Dijkstra 算法在现实生活中的应用是十分广泛的。参考文献:1严蔚敏，吴伟民.数据结构题集（C 语言版）M.北京：清华大学出版社，1997.2谭浩强.C 语言程序设计（第二版）M.北京：清华大学出版社， 2000.3余祥宣，崔国华，邹海明.计算机算法基础（第二版）M.武汉：华中科技大学出版，2004.4王晓东.算法设计与分析M.北京：清华大学出版社，2003.5殷人昆，陶永雷，谢若阳，等.数据结构（用面向对象方法与 C+描述）M.北京：清华大学出版社，1999.6美Clifford A. Shaffer.数据结构与算法分析（Java 版）M. 张铭，刘晓丹译，北京：电子工业出版社，2001.
