缪子阳+李婷玉+祝梦琳

摘要：文章将设置办事处個数问题转化为办事处覆盖范围问题，通过枚举法找出10种方案，使得办事处数量n最少为7。然后运用prim算法在最少办事处数量为7的条件下对各个方案算出最小生成树从而得出连线总长最小为15。

Abstract： The article will set the number of office problems into the office coverage problem， through the enumeration method to find 10 kinds of programs， making the number of office n at least 7. Then use the prim algorithm to calculate the minimum spanning tree for each program in the minimum number of office for 7 to achieve the minimum length of the connection is 15.

关键词：枚举法；prim算法；最小生成树

Key words： enumeration method；prim algorithm；minimum spanning tree

中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2017）17-0228-02

1 问题重述

某城市为东西长5公里，南北长4公里的矩形，每隔0.5公里有一条南北（或东西）方向的道路，参见图1。

（1）某公司要在该市设置n个办事处，要求该市内每一点到它最近的办事处的距离d不超过d0=1.5公里。问这些办事处应如何设置可使n最小？n最小为多少？（“距离d”如下定义：市内一居民只能沿水平或垂直线路到某一街道，然后再沿街道到达离他最近的办事处，他所走的最短路程即为“距离d”）

（2）若要将这n个办事处用专用网络线连接起来，这些网络线只能沿街道布置，应如何布线可使总长L最小？L的最小值为多少？

2 问题分析

2.1 对问题（1）的分析

第一小问要求设置n个办事处使得市内每一点到它最近的办事处的距离d不超过d0=1.5公里。

①此问题不适用于目标函数模型，尽管可以在这张图上建立坐标系，将目标函数确定为最小个数n，但约束条件无法确定市内某一点到某个办事处是否到的是最近的办事处，因此无法具体化约束条件，所以本题放弃了建立目标函数模型。

②此问题也不适用范围圆的交叉点来确定最小个数n，一来距离的定义是沿水平或者垂直路线到某一街道，以半径为1.5公里来划圆会将一些不满足d0=1.5公里的点划进去，二来有99个点，划99个圈无法识别。

③由划范围圆想到密铺方法，一个办事处可以覆盖一定范围的点，然后通过枚举法列出方案，可行且较简单。

2.2 对问题（2）的分析

①专用网络线连接的理解：不是两两互联，一条线串在一起即可。

②采用prim算法，可以求得最小生成树，从而可以算出L的最短长度。

3 基本模型假设

①题中的基本参数设定正确。

②若市内某一点距离两个办事处距离相等，且最短，则选择任一个。

③街道畅通，不考虑交通堵塞对选择最短距离的影响。

4 基本符号说明

n：办事处的个数；

L：专用网络线的长度；

V：办事处；

注：局部符号会在引用处说明。

5 模型建立与求解

5.1 对问题（1）的求解

要求设立办事处，使得市内每一点到它最近的办事处的距离d不超过d0=1.5公里。将问题转化为办事处的覆盖范围。

首先保证四个顶点要在办事处的覆盖范围之内。以左上方的顶点为例，一开始有10个点可以选择设置办事处。其次采取四个顶点对称的方式，依次取遍10个顶点作为第一个办事处。得到几组解。然后采取四个顶点不对称的方式，依次取遍10个顶点作为第一个办事处。得到几组解。本文中做了10组解，没有全部解完。小黑点表示办事处的位置，小灰点表示可供选择的办事处的位置，小方块表示正好距离办事处1.5公里的点。

5.2 对问题（2）的求解

以图2的方案为例。使用prim算法求解专用网络线的最小总长。

首先绘制加权连通图：将各个办事处连接起来，为了方便作图，将沿水平或者垂直路线到某一办事处的距离简化为一条线。

其次使用prim算法计算结果。为了更方便地说明相关计算细节，我们重述一下prim算法的原理。

基本思想：prim算法的基本思想是：设G=（V，E）是一个无向连通网，令T=（U，TE）是G的最小生成树。T的初始状态为U={v0}（v0∈V）TE={}，然后重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边（u，v）并入集合TE，同时v并入U，直至U=V为止[2]。

算法关键：prim算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。设当前T中有k个点（即T的顶点集U中有k个顶点）则所有满足u∈U，v∈V-U的边最多有k×（n-k）条，从如此大的边集中选取最短边是不太经济的[3]。利用MST性质，可以用下述方法构造候选最小边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边，取候选边最短边集为V-U中的n-k个顶点所关联的n-k条最短边的集合。为表示候选最短边集，需设置两个一维数组lowcost[n]和adjvex[n]，其中lowcost用来保存集合V-U中的各顶点与集合U中顶点的最短边的权值，lowcost[v]=0表示顶点v已经加入最小生成树中；adjvex用来保存依附于该边在集合U中的顶点[1]。

然后得出结果：

5.3 解题补充

根据所画的最小生成树图，将每条线的长度相加，就可以得到L的最短长度。

需要注意的是，上述求解只是第一问中的一种方案的求解，其他九种方案求解过程类似，唯一的不同就是根据加权连通图所写的权矩阵不同，在此不再赘述。

6 模型的评价

6.1 模型的优点

①简单清晰，无论是加权连通图还是最小生成树，都给人直观的印象。

②对于建模的要求不高，可以直接用算法求解出答案。

③本模型选择的算法可以快速得出不同方案下的最小程度，从而做出比较。

6.2 模型的缺点

①本文第一问采用的枚举法具有一定的局限性，对于较小的区域可以适用，对于大范围的设置办事处就难以适用了。

②本文认为是只需要将这几个办事处连接起来，而不用两两相连，没有考虑两两互连的情况。

参考文献：

[1]江波，张黎.基于Prim算法的最小生成树优化研究[J].计算机工程与设计，2009（13）：3244-3247.

[2]江波，张黎. 基于Prim算法的最小生成树优化研究[J].计算机工程与设计，2009（13）.

[3]陈新.基于最小生成树的聚类分析方法研究[D].重庆大学，2013.