目录
1.问题提出 ................................................................................................................................. 1 2.模型假设 ................................................................................................................................. 2 3.符号说明 ......................................................................................................... 2 4.模型建立与求解 ............................................................................................... 3 4.1基于Prim算法和Dijkstra算法的模型 ....................................................... 3 4.1.1模型建立 ............................................................................................. 3 4.1.2模型的求解与优化 ................................................................................ 4 4.2基于改进K?means聚类算法的模型 ......................................................... 7 4.2.1模型建立 ............................................................................................. 7 4.2.2模型求解 ............................................................................................. 9 4.3回归优化模型 ........................................................................................... 10 4.3.1模型建立 ........................................................................................... 10 4.3.2回归模型的求解与检验 ........................................................................ 11 5.模型优化 ....................................................................................................... 12
5.1距离代价函数和距离代价最小准则 ......................................................................... 12 5.2基于距离代价函数的空间聚类k值优化算法 ......................................................... 13 5.3 用K-means算法求解聚类中心 ............................................................................. 13 5.4 模型优化处理 ............................................................................................................. 13 6.模型分析与评价 ............................................................................................. 14 7.参考文献 ....................................................................................................... 14 附录1 .............................................................................................................. 15 附录2 .............................................................................................................. 16 附录3 .............................................................................................................. 18
1.问题提出
西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更好的生活和学习条件。在综合考虑了校园各地方平均人流量后，公园计划有若干个入口，为了保证公园里人员不过于拥挤和出入快捷方便，现在需建立一个模型去设计园内道路（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使任意两个入口相连，且总的道路长度和（这一总长度可能与成本成正比）最小，同时还要满足任意的两个入口间的最短道路长不大于两点连线的1.4倍。 考虑到不规则图形的复杂性、矩形的特殊性和普适性以及实际中的公园面积一般不会太小等因素，本题主要设计对象可假设为如图一所示的矩形公园，其相关数据为：长200米，宽100米，1至8号各入口的坐标分别为 P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),
P8(0,25)现完成以下问题：
（1）假定公园内确定要使用的4个道路交叉点为
A(50,75),B(40,40),C(120,40),D(115,70).图二所示即是一种满足要求的设计，但并不是最优的，问如何设计道路可使公园内道路的总路程最短。建立数学模型并给出算法。画出道路设计，计算新修路的总路程。
（2）现在公园内可以任意修建道路，如何在满足条件下使总路程最短？建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。
（3）若公园内有一条矩形的湖，如图三所示，新修的道路不能通过，但可以到达湖四周的边，重复完成问题二的任务。其中矩形湖位置坐标为R1(140,70),R2(140,45),R3(165,45),R4(165,70).
注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其他点。
图 一 公园及入口示意图 图二 一种可能的道路设计图
1
图三 有湖的示意图
2.模型假设
（1）设计道路只考虑路径长短，道路宽度处处相同且不考虑美观效果。 （2）经验值具有一定的科学规律，可实施。
3．符号说明
C1:记矩形边框网格线最小距离不大于连线距离1.4倍的无序点对为C1类无
序点对 C2:PC1类之外的无序点对记为C2类无1,P2,?,P8构成的所有无序点对中除
序点对
C:以公园8个入口P1,P2,?,P8为顶点的连通图的邻接矩阵
8个点中任意两点沿矩形边框的最短距离构成的矩阵 B:P1,P2,?,P8G:有n个顶点的连通图
T:连通图的最小生成树
l(i,j)：在确定路径中P,2,?,8) 两点间的道路长 i,Pj(i,j?1d(i,j)：用Dijkstra算法求得的P,2,?,8)两点最短路径的道路长 i,Pj(i,j?1w(i,j)：P,2,....,8)两点间的直线距离 i,Pj(i,j?1X:将8个入口点两两相连得到的交点（端点不算）记作
X??x1,x2,?,xnk：将X??x1,x2,?,xn?：X??x1,x2,?,xn?
?中的n个空间对象聚类为k类（簇）
?中的样本点
?的所有聚类结果构成的集合
p：空间中的任意一点，即X??x1,x2,?,xnCti：K-means算法求得的聚类数ki下的类（簇） mi：簇Cti所含样本的均值 m：全部样本的均值
2
4.模型建立与求解
4．1 基于Prim算法和Dijkstra算法的模型 4．1.1 模型建立
因为公园四周边上已经建好的道路不计入道路总长，要想园内道路总路程最短，应尽可能利用矩形边框道路。由于C1类无序点对满足边框最短距离不大于1.4倍连线距离，所以C1无序点对对应的入口可以通过公园边上道路连通，在进行道路设计时不予考虑；对C2类无序点对，可以将相关点连成连通图，通过Prim算法得出相应的最小生成树，再通过Dijkstra算法得到这些无序点对的最短路径，最后检验验证方案设计是否符合要求，若方案不合理，则需修改优化模型，直到得到符合条件的最佳道路设计方案为止。
（I）确定C1,C2类无序点对
根据图一坐标得到以公园8个入口P1,P2,?,P8为顶点的连通图的邻接矩阵C以及这8个点中任意两点沿矩形边框的最短距离构成的矩阵B。进行矩阵运算
M?1.4C?B
对矩阵元素进行分析，当mij?0时，1.4cij?bij，即Pi,Pj两点的矩形边框距离不大于两点连线的距离的1.4倍，Pi,Pj构成的无序点对属于C1类无序点对，在设计道路时，不需考虑这两点对应入口的道路连接问题；当mij?0时，Pi,Pj构成的无序点对属于C2类无序点对，需要设计合理的道路进行连接。
（II）用Prim算法和Dijkstra算法对C2类无序点对进行处理
在C2类无序点对中，任意一对的连接情况对其他无序点对的连接影响都较大，情况比较复杂。处理如下：
将所有与上述无序点对连接相关的点两两连接，对得到的连通图G用Prim算法得到相应的最小生成树T。
对算法Prim算法做一下说明： Prim算法：求加权连通图的最小生成树 输入：一个加权连通图G(n个顶点） 输出：图的权值最小的生成树
思想：从权值最小的边开始，通过不断地增加边且不形成圈来扩张，最后
形成树。先以权值递增的顺序排列各边，权值相同的边可以任意排序。 步骤：（1）设置集合T为空集，选出图的任意一顶点放入T中。
（2）把T中的顶点与不在T中的顶点的所有边中权值最小的边加
入T中。如果权值最小的边有多条则任选其一。
（3）如果T有n?1条边则停止，输出T，否则进入（2）。
3
（III）用Dijkstra算法对模型进行修改优化并检验模型的可行性 现对Dijkstra算法进行以下说明：
Dijkstra算法：求连通图中两顶点的最短路径的长度
输入：一个加权连通图G(n个顶点） 输出：连通图中两顶点的最短路径及其长度
思想：将连通图的顶点集分成两个互补的子集S,S,S的初始值为??o?，不
断将未处理的点中到顶点?0的最短距离中的最小的点加入S中，直到v0到?0的最短路径确定为止（或直到结束）。
步骤：（1）设置集合S=??o?，选出连通图除去S顶点中离?0最近的顶点
z放入S中。
（2）重复（1）直到v0到?0的最短路径确定为止（或直到结束），
每次迭代中，都用v与?0的直线距离（若这两点间无连线则取
距离为?）w(?0,v)和v与?0各路径距离l(?0,v)中的最小值替换d(?o,v)，直到v0?S。
用Dijkstra算法求出所有C2类无序点对间的最短路径和最短道路长d(i,j)，若不等关系
d(i,j)?1.4bij,i,j?1,2,3,5,6,7
成立，说明图四中相应的连线不符合要求，需要将结果进行修改优化。综合考虑所有无序点对间的最短道路长和最短道路总长，在已经连接好的路线不做太大改变的前提下，将不合理的路线进行适当的修改优化，直到所有路线都满足要求且道路总长最小为止。 4.1.2 模型的求解与优化
（I）根据图一坐标得到以公园8个入口P1,P2,?,P8为顶点的连通图的邻接矩阵 ?0?42.0000??196.0000?261.5416?C??197.9899??141.5662?140.6983??44.8219?42.0000196.0000261.5416197.9899141.5662140.69830154.0000221.3594170.8918141.5662150.7846154.0000089.6437150.7846224.1093252.3886221.359489.64370132.0757241.3732275.0564170.8918150.7846132.07570119.0000154.0000141.5662224.1093241.3732119.0000035.0000150.7846252.3886275.0564154.000035.0000078.2624226.7179282.1790198.1136115.8706105.92928P1,P2,?,P8这个点中任意两点沿矩形边框的最短距离构成的矩阵
44.8219?78.2624??226.7179??282.1790?
198.1136??115.8706?105.9292??0??4