?0?30??140?230?B??240??155?130??45?30011020027018516075140110090220295270185230200900130215240275240270220130085110195155185295215850251101301602702401102508545?75??185??275? 195??110?85??0??进行矩阵运算M?1.4C?B后,得到的矩阵
12.000056.000031.5416?42.0101?13.433810.6983?0.1781??0?12.0000?044.000021.3594?99.1082?43.4338?9.21543.2624???56.000044.00000?0.3563?69.2154?70.8907?17.611441.7179???31.541621.3594?0.356302.075726.373235.05647.1790?M????42.0101?99.1082?69.21542.0757034.000044.00005.8706? ???13.4338?43.4338?70.890726.373234.0000010.00005.8706???10.6983?9.2154?17.611435.056444.000010.0000020.9292???41.71797.17903.11365.870620.92920????0.17813.2624?当mij?0时，点(i,j)属于C1类无序点对；当mij?0时，点(i,j)属于C2类无序点对。由矩阵M的输出结果知，C2类无序点对有
(1,5),(1,6),(1,8),(2,5),(2,6),(2,7),(3,4),(3,5),(3,6),(3,7)，其他无序点对均为C1类无序点对。
（II）用Prim算法和Dijkstra算法对C2类无序点对进行处理
经观察分析，在所有C2类无序点对中，P4,P8均只在一对无序点对中出现，所以优先单独分析（1，8）和（3，4）。
在图二所示的道路设计坐标图中可以看出，P1,P8经过其他任意点间接连接起来的路程l(1,8)满足不等关系
l(1,8)?b18?1.4c18
同理有，
l(3,4)?b34?1.4c34
所以，P1,P8和P3,P4对应的两对入口必须分别直接连通。
(3,(3,67)，余下未处理的C2类无序点对有(1,5),(1,6),(2,5),(2,6),(2,7),(3,5),),将与上述无序点对的连接有关的点（P1,P2,P3,P5,P6,P7,P8,A,B,C,D）两两连接，对得到的连通图G用Prim算法得到相应的最小生成树T。
算法运行后输出的最小生成树T如下图四所示：
5
10090807060504030820100765AD4BC102040260801001201401603180200
图四 最小生成树
由于最小生成树只保证了C2类无序点对连接总路程最短，并不一定满足无序点对对应的入口之间的道路长不大于两点连线距离的1.4倍，所以需要检验。
（III）用Dijkstra算法对模型进行修改优化并检验模型的可行性 优化一：经Dijkstra算法计算得到，P1,P5两点间的最短路径为P1?P8?B?A?D?P5,但最短道路长d(1,5)?1.4c15，所以该路径不可取。在道路总长最小的前提下，为减少入口2和入口5间的道路长，可以将上述路径优化为P1?P2?B?A?P5。
优化二：通过观察，在连通入口7的道路中，A?P7段可以优化，可以先假设优化模型再验证检验假设的合理性。假设该段道路可以用A?P6?P7优化代替，即在优化模型中去掉A?P7段，用Dijkstra算法可以求出P7点到其他各点的最短路径和最短距离，计算结果均满足不等关系
d(7,j)?1.4c7j,j?1,2,?,8
即仍然满足两点间的最短道路长不大于两点连线距离的1.4倍这一要求，同时减少了道路总长，所以这种假设是可行的。
修改优化后的道路设计方案如下图五所示：
6
1009080706050403020108765AD4BC1002040260801001201403160180200
图五 修改优化后的道路设计
对修改优化后的模型进行检验，对图五所示的连通图用Dijkstra算法计算出任意两点间的最短道路长，在运行Dijkstra算法时，分别令（?0,v0)为
(1,5),(1,6),(2,5),(2,6),(2,7),(3,5),(3,6),(3,7)，对图五所示的连通图分别运用迪克斯特拉(Dijkstral)算法，得到所有情况下的最短路径和最短道路长。
经计算知，任意两点间的最短道路长都不大于两点连线距离的1.4倍，所以图五是一种符合要求的设计方案，又因为修改优化模型是在最小生成树模型的基础上综合考虑两点间最短道路长和最短道路总长的，所以图五设计方案的道路总长也是最短的。C2类无序点对的连接方案应按照图五所示来连接。
综上，在园内有四个交叉路口A(50,75),B(40,40),C(120,40),D(115,70) 的情况下，园内最优道路设计方案如图五所示，它同时满足①任意两个入口相连；②园内总道路长最小；③任意两个入口间的最短道路长不大于两点连线距离的1.4倍。经计算，新修路的总路程约为392.3米。 4.2 基于改进K?means聚类算法的模型 4.2.1 模型建立
由于无给定的道路交叉点，要想继续利用问题一中的模型，需要先确定公园内道路交叉点的个数及位置。由于两点间直线最短，要使道路总长最短，道路交叉点应从8个入口点两两连线的交点出发，所以可以先求出8个入口点两两连线的交点坐标，利用经验准则给定聚类数k，并用空间聚类K值优化算法对k值进行优化，最后通过K-means算法求解该聚类数下的聚类中心。以所求聚类中心作为道路交叉点设计道路，回到问题一。 （I）确定8个入口点两两连线的交点
根据图一中8个入口点的坐标，经过算法1（见附表）计算得到交点坐标，将其记为X?(x1,x2,?,xn)。
（II）K-means算法求解聚类中心
7
由于典型的K-means算法是在k准确给定的条件下实现的，所以用该算法时需要给定一个确切的k值，根据经验准则设定k?2，在给定的k值下运用K-means算法计算相应的聚类中心mi和簇Cti，对K-means算法做以下说明：
K-means算法：求空间数据对象的聚类中心
步骤：
（1） 求出样本空间
X??x1,x2,?,xnn?所有样本点的均值m，
m??xi。
i?1（2） 假设xp和xq为两个初始聚类中心，满足xp距离全体对象均值最远，
xp和xq之间的距离也最大，且xp和xq的距离 dpq?max?dij,i,j?1,2,...,n? （3） 分别计算其余n?2个对象与xp和xq之间的距离，若
?n? xi?xp?xi?xq,(n??1,2,...,,q?)
p??则将xi归入xp对应的类中，反之归入xq对应的类中。xp和xq 对应的
两个类分别用Z1和Z2来表示
（4）计算S1中各对象到xp的最大距离
d1?maxxs?xp,xs?Z1
?? 计算（2）中个对象到xq的最大距离
d2?maxxt?xq,xt?Z2
?? 记dmax?max?d1,d2?
（5）如果dmax???dpq,(???0.5,1?)，则xi(i?s或t)为第三个聚类中心，类别数K?K?1;否则算法结束
（6）重复（3）?（5）
根据已经设定的聚类数k?2，运用K-means算法求出聚类数2下的聚类中心。
（III）以聚类中心为道路交叉点设计最佳道路
空间聚类一般使用距离作为划分准则，即任一空间对象与该对象所属簇的几何中心之间的距离比该对象到任何其他簇的几何中心的距离都小，所以，上
8
步中得到的聚类中心可以作为公园道路规划时园内交叉路口。在确定了道路交叉点的个数和位置后，我们可以套用问题一的模型来设计最优道路方案。 4.2.2 模型求解
1（I）输入P1,P2,?,P8各点的坐标，运用算法得到两两连线交点，输出结果
如下图六所示：
1009080706050403020100020406080100120140160180200
图六 入口两两连线示意图
重合的交点不计算在内，一共得到68个交点，用xi(i?1,2,?,68)表示各交点，交点坐标的输出结果见附录2 （II）K-means算法求解聚类中心
记A??x1,x2,?,xi,?,x68?(i?1,2,?,68)为样本空间，由经验准则给定聚类数k?2，用K-means算法求出聚类数k?2下的聚类空间。运行结束时输出
k?2时的聚类空间，将求得的两个中心分别记为S1,S2，计算结果为
S1?(172,42),S2?(60,77) (III)以聚类中心为道路交叉点设计最佳道路
以S1?(172,42),S2?(60,77)为道路交叉点设计道路使道路总长最短，可以套用问题一中的模型，最后输出结果如下图六所示：
9