Floyd算法在中心小学选址上的应用

摘要：中心小学选址是一个非常重要的问题。是将地理信息作为选址的主要依据，将几个相邻的村子的地理信息抽象成数学当中的图，然后用图论中求中心点和中位点的方法来确定中心小学的位置。在求中心点、中位点时要用到图论中最短路径算法，对经典的最短路径算法Floyd算法作了介绍。最后，用实例来分析中心点与中位点选址模型，并对中位点模型作了进一步分析。

关键词：中心小学选址； Floyd算法； 最短路径

中图分类号：TP399 文献标识码：A文章编号：2095-2163（2013）02-0080-03

0引言

自1979年中国推行计划生育政策以来，农村人口出生率呈明显下降态势，而如何保证农村人口接受优质教育的问题日益迫切地摆在每个规范农村教育发展，关注农村教育进步的有识之士面前。农村教学点布局不尽合理，生源明显不足，学校规模局促、办学效益走低等。

2006年，教育部发出《关于实事求是地做好农村中小学布局调整工作的通知》，通知要求“大力发展乡镇中心学校，启动寄宿制学校的标准化建设，提高农村教育质量。”一些地方开始有目标、有规划、分阶段、分步骤地调整小学布局，对未达到一定规模的小学教学点陆续进行了撤并，设立乡镇中心小学。

但是，由目前农村中心小学选址的现状，其最终的选址结果却仍存在一定的缺陷和弊端。诸如：频繁出现的交通事故，学校布局过于密集或分散造成的不合理利用率等。通常，农村中心小学选址的影响因素则有许多，其中如交通条件、自然地理条件、道路状况和学生人数等，就是最为关键的影响因素。如何将这些因素有效纳入选址决策，并科学规划农村中心小学布局，在发挥其最大效益的同时，能够更为符合农村人口结构特征，并进一步保证学生上学、放学的安全则显得越发重要。本文探讨了一种基于Floyd算法的完整实用技术，可在广大农村辖区内为中心小学实现合理选址，选址效果满足了多项性能指标需求，因而具有一定的理论意义和实用价值。

1Floyd算法的基本思想

最短路径问题是图论中的一个基本内容.在赋权图中，每一条边都定义了一个权值（距离、成本、时间等），搜索得到两点之间权值总和最小的路径就是最小路径问题.最短路径问题，通常可分为三类[1]：单源最短路径问题；确定起点、终点的最短路径问题；全局最短路径问题。

Floyd算法[2]可借助于权矩阵，直接求得任意两点间的最短路径。假设需要求取由节点i到j的最短路径，实现步骤是：

（1）如果i、j间有边，则由i到j存在一条长度为cost[i，j]的路径，该路径不一定是最短的路径，还需要进行n次试探.

（2）从i经过若干个节点k到j。所以，假设Dis（i，j）为节点i到节点j的最短路径距离，对于每一个节点k，检查Dis （i，k） + Dis （k，j） < Dis （i，j）是否成立，如果成立，证明从ikj的路径比ij的路径短，便可设置Dis（i，j） = Dis（i，k） + Dis（k，j），当遍历完成所有节点k以后，Dis（i，j）就记录了ij的最短路径距离。

2中心小学选址模型的算法与分析

21选址模型介绍

根据选址设定的目标函数不同，可以分为中心点问题和中位点问题。中心点问题的目标函数是使得“最大距离达到最小”；中位点问题的目标函数是使得“距离总和达到最小”，本文选用的是中位点方法[3]。

中位点问题是研究如何选择一个服务站（本文是中心小学），使得需求点和服务站间的距离与需求量的乘积之和能够限定为最小。中位点问题可以用如下模型进行表示：

其中：Wi表示需求点和设施点间的最大距离；Vi代表可选的顶点；Vj代表任意顶点.第2期吴焕瑞，等：Floyd算法在中心小学选址上的应用智能计算机与应用第3卷

22建立拓扑图

农村的交通网络，可以将村庄和道路抽象为其组成节点和连接边均为有限的有向图G。在建立图G前，先进行如下处理：如果两个村子之间存在两条路，则以一条边实际计算，并确定其权值为两条路中最短长度。如此处理，是为了使图G成为一个简单图。

例如：选取河北省三河市泃阳镇的几个相邻的村落来讨论中心小学的选址模型，图1是从搜狗地图中下载的地图图片，对图1抽象处理，得到的拓扑如图2所示。其中，顶点代表村落，边代表两顶点所对应的村落之间有连接道路，边上的权值代表两个村落间的距离，单位为500米。

23中心小学选址实例实现

建立图G所对应的邻接矩阵，如图3所示。采用C语言实现中位点求解。通过计算，在中位点选址模型中选取赵河沟（节点③）为中心小学的选址地点，可满足中位点的选址要求。程序调试结果如图4所示。

3.1模型分析

上述求取中位点的过程中，只是考虑了村落地理位置这一基本因素，却未考虑到每个村落的人口因素，而人口因素也是中心小学的选址的重要因素，因此可做如下处理以重新建立中位点选址模型。

每个村落都有相对固定的人口数和家庭数。可将图2中建立的图G的每个顶点再加上一个权值，这个权值用来体现人口因素，现在需要决策将每个村落顶点的权值设为该村子的人口数，还是设为其中的学龄儿童数.显然，选取每个村落的学龄儿童数作为顶点的权值，较为合理。

在带权值的顶点图上选取中位点，在邻接矩阵中求出了Edge[M][M]矩阵，其中，第i行第j列表示i与j间的最短路径长度。将顶点的权值按照顺序构造一个向量q，用向量q与矩阵Edge[M][M]相乘，得到一个新的向量，存到search[M]中，再从search[M]找到其中最小的，得到中位点位置[4]。当M=10时，其数学表达式为：

在si（i=0，…，9）中寻到最小值，该值所对应的顶点就是中位点。用此方法择选的中心小学位置，既考虑了村落之间的地理因素，也考虑了每个村落的人口因素，更具有全面的合理性，对中心小学的实际选址更为显明的借鉴和参考作用。

32实例求解

如前所述，利用每个村落的学龄儿童的数作为图顶点的权值，各个村落的具体数值是：赵屠庄村284人、李河沟村63人、马河沟村135人、大田庄村177人、赵河沟村355人、小田庄村和北陈庄村324人、方元屯村248人、郑辛庄户村188人、大丁河沟和小丁河沟357人、沟北庄户村438人。顶点权值构成的向量为：（24863135177355324248188357438）

这个模型求解结果是选取大丁河沟和小丁河沟作为中心小学的选址地点。在Visual C++6.0中计算结果如图5所示。图5 中位点加权法调试结果

Fig.5 The debugging results of Weighted method

4结束语

针对近年来中心小学的建设现状，介绍了图论知识在选址上的应用。本文将几个村落的地理信息作为中心小学选址需要考虑的因素，其做法就是将几个村落的地理信息抽象为数学中的拓扑图，再利用Floyd算法进行实例验证。在文章最后，还对中位点模型展开了更进一步的分析，将每个村落的人口因素看作是图G顶点的权值，由此，在中位点选址方案中，就考虑了地理和人口因素，选址的结果将更加科学合理，具有良好的推广应用价值。

参考文献：

[1]姬东. 图论最短路径问题在消防选址中的应用[J]. 武警学院学报，2009，25（12）：10-12.

[2]严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2007：186-192.

[3]杨丰梅， 华国伟， 邓猛，等. 选址问题研究的若干进展[J]. 运筹与管理，2005，14（6）：1-6.

[4]黎青松，杨伟，曾传华. 中心问题与中位问题的研究现状[J].系统工程，2005，23（5）：11-16.