地理信息系统分析题
一、有关最短路径问题
单源点间最短路径：网络中某一点到其它点的最短路径.
所有点对之间的最短路径：在整个运算过程中，求得所有点对 之间的最短距离. 1. 最短路径问题
最短路径的含义——是指在网络中，找出从起点出发到终点的累计行程最短的路径。 1）“纯距离”意义上的最短路径
如需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？ 2）“经济距离”意义上的最短路径
某公司在世界上10大港口C1，C2…C10设有货栈，为了更好地适应市场供需形势， 经常在各港口之间运送各类货物。从Ci 到Cj 之间的直接航运价格，是由市场动态决
定的。如果两个港口之间无直接航运路线，需要通过第三个港口转运。那么各个港口之间最廉价的货运路线是什么？
3）“时间”意义上的最短路径
某家经营公司有一批货物从急需要从一个城市运往另一个城市，那么，在由公路、 铁路、河运和航空运输四种运输方式和各个城市所构成的交通网络中，究竟选择怎样的运输路线最节省时间？
最短路径的算法——Dijkstar 算法
1959年由E.W.Dijkstar 提出的标号法被认为是目前公认的最好的求解算法 该算法的优点是：
可以求出起点到终点的最短路径及其长度，而且可以求出起点到其它任何一个顶点的最短路径及其长度。不但适用于求解有向图上的最短路径问题，而且同样也适用于求解无向图上的最短路径问题。
基本思想：
首先从起点Vs 开始，给每个顶点标一个数(称为标号) ，
T 标号——表示从起点Vs 到该点的最短路径的上界，称为临时标号； P 标号——表示从Vs 到该点的最短路经，称为固定标号。
已经得到 P 标号的顶点不再改变，凡是没有标上 P 标号的顶点，标上T 标号。
算法的每一步就是把某一顶点的 T 标号改为变为 P 标号。那么，最多经过k -1步，就可以求得从起点Vs ，到终点Vk 的最短路径。
（1）. 距离矩阵的计算
为了求出最短路径，需先计算两点间的距离，并形成距离矩阵。若两点间没有路，则距离为∞
（2）. 最短路径搜索的依据
最短路径搜索的基本依据是，若从点S 到点 E 有一条最短路径， 则该路径上的任何点到S 的距离都是最短的。
为了进行最短路径搜索，令d(Vi, Vj)表示点Vi 到Vj 的距离， P(Vi)表示Vi 到起始点S 的最短距离。 （3）. 最短路径搜索的步骤
①对起始点S 作标记，且对所有顶点令P(Vs) = 0, T(Vi) ＝∞。 ② 对所有未作标记的点按以下公式计算距离， T(Vj) ＝min ｛ T(Vj), d(Vi, Vj) ＋P(Vi)｝ 其中Vi 是己确定作标记的点。取具有最小值的T(Vj) ，并对Vj 作标记，令P(Vj) ＝ T(Vj) 。 若最小值的T(Vj)为∞，则说明S 到所有未标记的点都没有路，算法终止；否则继续。 ③ 如果Vj 等于E ，则已找到S 到E 的最短路径，算法终止；否则转(2)。 需搜索A 到C 的最短路径
①对A 作P 标记，P(A)=0, 其它结点作T 标号，T(V)= +∞, V为B 、C 、D 、E 。 ② 因为A 已经得到P 标号，而与A 关联弧段的结点有B 、E 、D ， 且它们都是T 标号，所以要修改它们的T 标号
T(B) = min[T(B),P(A)+d(A,B)] = min[+∞,0+4] = 4 T(E) = min[T(E),P(A)+ d(A,E)] = min[+∞,0+2] = 2 T(D) = min[T(D),P(A)+ d(A,D)] = min[+∞,0+1] = 1 在所有的T 标号中，T(D) = 1最小，于是令P(D) = 1
③因为D 已经得到P 标号，而与D 关联弧段的结点有E 、C ， 且它们都是T 标号，所以要修改它们的T 标号
T(E) = min[T(E),P(D)+d(D,E)] = min[2,1+2] = 2 T(C) = min[T(C),P(D)+ d(D,C)] = min[+∞,1+9] = 10 在所有的T 标号中，T(E) = 2最小，于是令P(E) = 2 ④因为E 已经得到P 标号，而与E 关联弧段的结点有B 、C ， 且它们都是T 标号，所以要修改它们的T 标号
T(B) = min[T(B),P(E)+d(E,B)] = min[4,2+1] = 3 T(C) = min[T(C),P(E)+ d(E,C)] = min[10,2+6] = 8 在所有的T 标号中，T(B) = 3最小，于是令P(B) = 3
⑤因为B 已经得到P 标号，而与B 关联弧段的结点只有C ，且为T 标号，所以要修改它们的T 标号
T(C) = min[T(C),P(B)+d(B,C)] = min[8,3+7] = 8 在所有的T 标号中，只有T(C) = 8最小，于是令P(C) = 8
⑥根据顺序记录的标记点，以及最小值的取值情况，可得到最短路径为A→E→C， 最短距离为8。 2.Dijkstar 算法应用举例
在下图所示的赋权图中，每一个顶点Vi ( i=1,2,…)代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇 V1到 V7 之间的最短路径。
V2
V1
首先， 给V1标上P 标号P(V1) = 0，表示V1到V1的最短路径为0。其它点标上T 标号， T(Vj) = +∞(j = 2,3,4,5,6,7)
第一步，V1已得到P 标号的点。V2，V3，V4是T 标号，所以修改这三个点的T 标号 T(V2) = min[T(V2),P(V1)+w12] = min[+∞,0+2] = 2 T(V3) = min[T(V3),P(V1)+w13] = min[+∞,0+5] = 5 T(V4) = min[T(V4),P(V1)+w14] = min[+∞,0+3] = 3 在所有的T 标号中，T(V2) = 2最小，于是令P(V2) = 2
第二步，V2是刚得到P 标号的点。V3，V6是T 标号，所以修改这两个点的T 标号 T(V3) = min[T(V3),P(V2)+w23] = min[5, 2+2] = 4 T(V6) = min[T(V6),P(V2)+w26] = min[+∞,2+7] = 9 在所有的T 标号中，T(V4) = 3最小，于是令P(V4) = 3
第三步，V4是刚得到P 标号的点。V5是T 标号，所以修改这两个点的T 标号 T(V5) = min[T(V5),P(V4)+w45] = min[+∞, 3+5] = 8 在所有的T 标号中，T(V3) = 4最小，于是令P(V3) = 4
第四步，V3是刚得到P 标号的点。V5，V6是T 标号，所以修改这两个点的T 标号 T(V5) = min[T(V5),P(V3)+w35] = min[8, 4+3] = 7 T(V6) = min[T(V6),P(V3)+w36] = min[9,4+5] = 9
在所有的T 标号中，T(V5) = 7最小，于是令P(V5) = 7
第五步，V5是刚得到P 标号的点。V6，V7是T 标号，所以修改这两个点的T 标号 T(V6) = min[T(V6),P(V5)+w56] = min[9, 7+1] = 8 T(V7) = min[T(V7),P(V5)+w57] = min[+∞,7+7] = 14 在所有的T 标号中，T(V6) = 8最小，于是令P(V6) = 8
第六步，V6是刚得到P 标号的点。V7是T 标号，所以修改这两个点的T 标号 T(V7) = min[T(V7),P(V6)+w67] = min[14, 8+5] = 13 目前只有V7是T 标号，故令P(V7) = 13
至此，图中所有点都标上了P 标号，所以求解结束。显然从城镇V1到V7之间的最短路径为（V1，V2，V3，V5，V6，V7），最短路径长度为13
二、选址(定位) 问题举例 1. 中心选址问题
质量判断依据：使最佳选址位置所在的顶点的最大服务距离为最小。这类选址问题适宜于医院、消防站点等一类服务设施的布局问题 实质就是：求网络图中心点问题
假设某县下属的六个乡镇及其之间公路联系如下图，图中每一个顶点代表一个乡镇；每一条边代表连接两个乡镇之间的公路，数字代表该 公路的长度。现要设立一个消防站为全县6个乡镇服务。试问该消防站应该设在哪一个乡镇？
第一步，用标号法求出每一个顶点Vi 到其它各顶点Vj 的最短路径长度dij(i,j = 1,2…6) ，写出起距离矩阵
d11 d12 d13 d14 d15 d16 0 3 6 3 6 4 d21 d22 d23 d24 d25 d26 3 0 3 4 5 7 d31 d32 d33 d34 d35 d36 6 3 0 3 2 4 d41 d42 d43 d44 d45 d46 3 4 3 0 5 7 d31 d32 d33 d34 d35 d36 6 5 2 5 0 2 d41 d42 d43 d44 d45 d46 4 7 4 7 2 0 第二步，求每一个顶点的最大服务距离。显然，它们分别是矩阵中各行的最大值。即： e (V1) = 6， e(V2) = 7， e(V3) = 6，
e(V4) = 7， e(V5) = 6， e(V6) = 7， 第三步，判定。
因为e (V1) = e (V3) = e (V5) =min{e (Vi) }=6
所以V1，V3，V5都是图中的中心点，也就是说消防站设在V1，V3，V5中的任何一个顶点上都是可行的
2. 中位点选址问题
质量判断依据：使最佳选址位置所在的顶点的到网络图中其它各顶点的最短 路径距离的总和（或载荷加权求和）达到最小。 假设某县下属的七个乡镇，各乡镇所拥有人口数a(Vi)(i = 1,2…7),以及各乡镇之间的距wij(i,j = 1,2…7)如图所示。现需要设立一个中心邮局，为全县所管辖的七个乡镇共同服务。试问该
中
心邮局应该设在哪一个乡镇？
第一步，用标号法求出每一个顶点Vi 到其它各顶点Vj 的最短路径长度dij(i,j = 1,2…
7)
，写出起距离矩阵 d d 11d 12d 13d 14d 15d 16d 17d 21d 22d 23d 24d 25d 26d 27 d 31d 32d 33d 34d 35d 36d 37 41d 42d 43d d 44d 45d 46d 47
D = d 31d 32d 3334d 35d 36d
d 57
41d d d d d d d d [1**********]7
d 51
52d 53d 54d d 55d 56d 5761d 62d 63d 6465d 66d
d
d 6771d 72d 73d 74d 7576d 77 0 3 5 6.3 9.3 4.5 63 0 2 3.3 6.3 1.5 3 5 2 0 2.0 5.0 3.5 5= 6.3 3.3 2.0 0 3 1.8 3.3
9.3 6.3 5 3 0 4.8 6.3 4.5 1.5 3.5 1.8 4.8 0 1.5 6 3 5 3.3 6.3 1.5 0
第二步，以各顶点的载荷（人口数）加权，求每一个顶点至其它各个顶点的最短路径长度的加权和。 第三步，判定。
因为S (V3) = S (V4) =min{S (Vi) }=69.5， 所以V3，V4都是图中的中位点，也就是说中心邮局设在V3，V4中的任何一个顶点上都是可行的
a (V 2a (V 1) = 3
6) = 1
S (V 7
1)= Σa (V j ) d 1j = 122.3
j =1S (V 2
)=Σ7
a (V j
) d
2j
= 71.3
j =1
S (V 7
3)= Σa (V j ) d 3j = 69.5j =1
S (V 4)= Σ7a (V j ) d 4j = 69.5j S (V 7
=1
5)= Σa (V j ) d 5j = 108.5
j =1
S (V Σ7
6)= a (V j ) d 6j = 72.8
j =1
S (V 7
7)= Σa (V j ) d 7j = 95.3
j =1
栅格数据压缩
栅格数据压缩，是指为了删除冗余数据，减少数据存储量，节省存储空间，加快后继处理速度，对栅格数据所做得处理方法。 ①游程编码压缩方法
是指将原始栅格阵列的行或列中属性值相同的连续若干个栅格单元进行合并，并映射成一个游程，以减少数据存储冗余度的编码压缩方法。
每个游程的数据结构为（A ，P ）整数对, 其中A 代表属性值或属性值的指针，P 代表连续相同属性值的栅格个数
游程编码压缩方法是一种无损失的压缩编码结构
特点：1）区域越大，数据的相关性越强，则压缩比越大，适用于类型区域面积较大的专题图2）在栅格加密时，数据量不会明显增加，压缩率高，编码解码运算简单，且易于检索，叠加，合并等操作。
②链式编码压缩方法：
用从某一起点开始沿8个方向前进的单位矢量链来表示线状地物或多边形的边界， 从而达到压缩数据量的方法 建立步骤：1）首先定义一个3×3窗口，对中间栅格的走向的8种可能进行编码。 2）记下地物属性码和起点行、列后，进行追踪，得到矢量链。如下图所示：
③块状编码压缩方法
是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号) 和半径，再加上记录单元的代码组成。数据对格式(初始行、列，半径，属性值)
1）大块图斑记录单元大，分辨率低，压缩比高; 小块图斑记录单元小，分辨率高，压缩比低。 2）块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。
④四叉树编码压缩方法
是指将栅格或图像沿中央位置等分成四部分，如果某一子区的所有网格都具有同样的属性值，则这个子区就不再继续分割；否则，就要把这个子区再等分成四个区域，直到每个子区都含有相同的属性值为止，据此再进行编码的方法。
一种可变分率的非均匀网格系统，是最有效的栅格数据压缩编码方法之一。 1、基本思想： 将 2n×2n 象元组成的空间区域(不足的用背景补上) 按四个象限进行递归分割，并判断属性是否单一，若单一则不分，若不单一，则递归分割。最后得到一颗四分叉的倒向树——四叉树。
地理信息系统分析题
一、有关最短路径问题
单源点间最短路径：网络中某一点到其它点的最短路径.
所有点对之间的最短路径：在整个运算过程中，求得所有点对 之间的最短距离. 1. 最短路径问题
最短路径的含义——是指在网络中，找出从起点出发到终点的累计行程最短的路径。 1）“纯距离”意义上的最短路径
如需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？ 2）“经济距离”意义上的最短路径
某公司在世界上10大港口C1，C2…C10设有货栈，为了更好地适应市场供需形势， 经常在各港口之间运送各类货物。从Ci 到Cj 之间的直接航运价格，是由市场动态决
定的。如果两个港口之间无直接航运路线，需要通过第三个港口转运。那么各个港口之间最廉价的货运路线是什么？
3）“时间”意义上的最短路径
某家经营公司有一批货物从急需要从一个城市运往另一个城市，那么，在由公路、 铁路、河运和航空运输四种运输方式和各个城市所构成的交通网络中，究竟选择怎样的运输路线最节省时间？
最短路径的算法——Dijkstar 算法
1959年由E.W.Dijkstar 提出的标号法被认为是目前公认的最好的求解算法 该算法的优点是：
可以求出起点到终点的最短路径及其长度，而且可以求出起点到其它任何一个顶点的最短路径及其长度。不但适用于求解有向图上的最短路径问题，而且同样也适用于求解无向图上的最短路径问题。
基本思想：
首先从起点Vs 开始，给每个顶点标一个数(称为标号) ，
T 标号——表示从起点Vs 到该点的最短路径的上界，称为临时标号； P 标号——表示从Vs 到该点的最短路经，称为固定标号。
已经得到 P 标号的顶点不再改变，凡是没有标上 P 标号的顶点，标上T 标号。
算法的每一步就是把某一顶点的 T 标号改为变为 P 标号。那么，最多经过k -1步，就可以求得从起点Vs ，到终点Vk 的最短路径。
（1）. 距离矩阵的计算
为了求出最短路径，需先计算两点间的距离，并形成距离矩阵。若两点间没有路，则距离为∞
（2）. 最短路径搜索的依据
最短路径搜索的基本依据是，若从点S 到点 E 有一条最短路径， 则该路径上的任何点到S 的距离都是最短的。
为了进行最短路径搜索，令d(Vi, Vj)表示点Vi 到Vj 的距离， P(Vi)表示Vi 到起始点S 的最短距离。 （3）. 最短路径搜索的步骤
①对起始点S 作标记，且对所有顶点令P(Vs) = 0, T(Vi) ＝∞。 ② 对所有未作标记的点按以下公式计算距离， T(Vj) ＝min ｛ T(Vj), d(Vi, Vj) ＋P(Vi)｝ 其中Vi 是己确定作标记的点。取具有最小值的T(Vj) ，并对Vj 作标记，令P(Vj) ＝ T(Vj) 。 若最小值的T(Vj)为∞，则说明S 到所有未标记的点都没有路，算法终止；否则继续。 ③ 如果Vj 等于E ，则已找到S 到E 的最短路径，算法终止；否则转(2)。 需搜索A 到C 的最短路径
①对A 作P 标记，P(A)=0, 其它结点作T 标号，T(V)= +∞, V为B 、C 、D 、E 。 ② 因为A 已经得到P 标号，而与A 关联弧段的结点有B 、E 、D ， 且它们都是T 标号，所以要修改它们的T 标号
T(B) = min[T(B),P(A)+d(A,B)] = min[+∞,0+4] = 4 T(E) = min[T(E),P(A)+ d(A,E)] = min[+∞,0+2] = 2 T(D) = min[T(D),P(A)+ d(A,D)] = min[+∞,0+1] = 1 在所有的T 标号中，T(D) = 1最小，于是令P(D) = 1
③因为D 已经得到P 标号，而与D 关联弧段的结点有E 、C ， 且它们都是T 标号，所以要修改它们的T 标号
T(E) = min[T(E),P(D)+d(D,E)] = min[2,1+2] = 2 T(C) = min[T(C),P(D)+ d(D,C)] = min[+∞,1+9] = 10 在所有的T 标号中，T(E) = 2最小，于是令P(E) = 2 ④因为E 已经得到P 标号，而与E 关联弧段的结点有B 、C ， 且它们都是T 标号，所以要修改它们的T 标号
T(B) = min[T(B),P(E)+d(E,B)] = min[4,2+1] = 3 T(C) = min[T(C),P(E)+ d(E,C)] = min[10,2+6] = 8 在所有的T 标号中，T(B) = 3最小，于是令P(B) = 3
⑤因为B 已经得到P 标号，而与B 关联弧段的结点只有C ，且为T 标号，所以要修改它们的T 标号
T(C) = min[T(C),P(B)+d(B,C)] = min[8,3+7] = 8 在所有的T 标号中，只有T(C) = 8最小，于是令P(C) = 8
⑥根据顺序记录的标记点，以及最小值的取值情况，可得到最短路径为A→E→C， 最短距离为8。 2.Dijkstar 算法应用举例
在下图所示的赋权图中，每一个顶点Vi ( i=1,2,…)代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇 V1到 V7 之间的最短路径。
V2
V1
首先， 给V1标上P 标号P(V1) = 0，表示V1到V1的最短路径为0。其它点标上T 标号， T(Vj) = +∞(j = 2,3,4,5,6,7)
第一步，V1已得到P 标号的点。V2，V3，V4是T 标号，所以修改这三个点的T 标号 T(V2) = min[T(V2),P(V1)+w12] = min[+∞,0+2] = 2 T(V3) = min[T(V3),P(V1)+w13] = min[+∞,0+5] = 5 T(V4) = min[T(V4),P(V1)+w14] = min[+∞,0+3] = 3 在所有的T 标号中，T(V2) = 2最小，于是令P(V2) = 2
第二步，V2是刚得到P 标号的点。V3，V6是T 标号，所以修改这两个点的T 标号 T(V3) = min[T(V3),P(V2)+w23] = min[5, 2+2] = 4 T(V6) = min[T(V6),P(V2)+w26] = min[+∞,2+7] = 9 在所有的T 标号中，T(V4) = 3最小，于是令P(V4) = 3
第三步，V4是刚得到P 标号的点。V5是T 标号，所以修改这两个点的T 标号 T(V5) = min[T(V5),P(V4)+w45] = min[+∞, 3+5] = 8 在所有的T 标号中，T(V3) = 4最小，于是令P(V3) = 4
第四步，V3是刚得到P 标号的点。V5，V6是T 标号，所以修改这两个点的T 标号 T(V5) = min[T(V5),P(V3)+w35] = min[8, 4+3] = 7 T(V6) = min[T(V6),P(V3)+w36] = min[9,4+5] = 9
在所有的T 标号中，T(V5) = 7最小，于是令P(V5) = 7
第五步，V5是刚得到P 标号的点。V6，V7是T 标号，所以修改这两个点的T 标号 T(V6) = min[T(V6),P(V5)+w56] = min[9, 7+1] = 8 T(V7) = min[T(V7),P(V5)+w57] = min[+∞,7+7] = 14 在所有的T 标号中，T(V6) = 8最小，于是令P(V6) = 8
第六步，V6是刚得到P 标号的点。V7是T 标号，所以修改这两个点的T 标号 T(V7) = min[T(V7),P(V6)+w67] = min[14, 8+5] = 13 目前只有V7是T 标号，故令P(V7) = 13
至此，图中所有点都标上了P 标号，所以求解结束。显然从城镇V1到V7之间的最短路径为（V1，V2，V3，V5，V6，V7），最短路径长度为13
二、选址(定位) 问题举例 1. 中心选址问题
质量判断依据：使最佳选址位置所在的顶点的最大服务距离为最小。这类选址问题适宜于医院、消防站点等一类服务设施的布局问题 实质就是：求网络图中心点问题
假设某县下属的六个乡镇及其之间公路联系如下图，图中每一个顶点代表一个乡镇；每一条边代表连接两个乡镇之间的公路，数字代表该 公路的长度。现要设立一个消防站为全县6个乡镇服务。试问该消防站应该设在哪一个乡镇？
第一步，用标号法求出每一个顶点Vi 到其它各顶点Vj 的最短路径长度dij(i,j = 1,2…6) ，写出起距离矩阵
d11 d12 d13 d14 d15 d16 0 3 6 3 6 4 d21 d22 d23 d24 d25 d26 3 0 3 4 5 7 d31 d32 d33 d34 d35 d36 6 3 0 3 2 4 d41 d42 d43 d44 d45 d46 3 4 3 0 5 7 d31 d32 d33 d34 d35 d36 6 5 2 5 0 2 d41 d42 d43 d44 d45 d46 4 7 4 7 2 0 第二步，求每一个顶点的最大服务距离。显然，它们分别是矩阵中各行的最大值。即： e (V1) = 6， e(V2) = 7， e(V3) = 6，
e(V4) = 7， e(V5) = 6， e(V6) = 7， 第三步，判定。
因为e (V1) = e (V3) = e (V5) =min{e (Vi) }=6
所以V1，V3，V5都是图中的中心点，也就是说消防站设在V1，V3，V5中的任何一个顶点上都是可行的
2. 中位点选址问题
质量判断依据：使最佳选址位置所在的顶点的到网络图中其它各顶点的最短 路径距离的总和（或载荷加权求和）达到最小。 假设某县下属的七个乡镇，各乡镇所拥有人口数a(Vi)(i = 1,2…7),以及各乡镇之间的距wij(i,j = 1,2…7)如图所示。现需要设立一个中心邮局，为全县所管辖的七个乡镇共同服务。试问该
中
心邮局应该设在哪一个乡镇？
第一步，用标号法求出每一个顶点Vi 到其它各顶点Vj 的最短路径长度dij(i,j = 1,2…
7)
，写出起距离矩阵 d d 11d 12d 13d 14d 15d 16d 17d 21d 22d 23d 24d 25d 26d 27 d 31d 32d 33d 34d 35d 36d 37 41d 42d 43d d 44d 45d 46d 47
D = d 31d 32d 3334d 35d 36d
d 57
41d d d d d d d d [1**********]7
d 51
52d 53d 54d d 55d 56d 5761d 62d 63d 6465d 66d
d
d 6771d 72d 73d 74d 7576d 77 0 3 5 6.3 9.3 4.5 63 0 2 3.3 6.3 1.5 3 5 2 0 2.0 5.0 3.5 5= 6.3 3.3 2.0 0 3 1.8 3.3
9.3 6.3 5 3 0 4.8 6.3 4.5 1.5 3.5 1.8 4.8 0 1.5 6 3 5 3.3 6.3 1.5 0
第二步，以各顶点的载荷（人口数）加权，求每一个顶点至其它各个顶点的最短路径长度的加权和。 第三步，判定。
因为S (V3) = S (V4) =min{S (Vi) }=69.5， 所以V3，V4都是图中的中位点，也就是说中心邮局设在V3，V4中的任何一个顶点上都是可行的
a (V 2a (V 1) = 3
6) = 1
S (V 7
1)= Σa (V j ) d 1j = 122.3
j =1S (V 2
)=Σ7
a (V j
) d
2j
= 71.3
j =1
S (V 7
3)= Σa (V j ) d 3j = 69.5j =1
S (V 4)= Σ7a (V j ) d 4j = 69.5j S (V 7
=1
5)= Σa (V j ) d 5j = 108.5
j =1
S (V Σ7
6)= a (V j ) d 6j = 72.8
j =1
S (V 7
7)= Σa (V j ) d 7j = 95.3
j =1
栅格数据压缩
栅格数据压缩，是指为了删除冗余数据，减少数据存储量，节省存储空间，加快后继处理速度，对栅格数据所做得处理方法。 ①游程编码压缩方法
是指将原始栅格阵列的行或列中属性值相同的连续若干个栅格单元进行合并，并映射成一个游程，以减少数据存储冗余度的编码压缩方法。
每个游程的数据结构为（A ，P ）整数对, 其中A 代表属性值或属性值的指针，P 代表连续相同属性值的栅格个数
游程编码压缩方法是一种无损失的压缩编码结构
特点：1）区域越大，数据的相关性越强，则压缩比越大，适用于类型区域面积较大的专题图2）在栅格加密时，数据量不会明显增加，压缩率高，编码解码运算简单，且易于检索，叠加，合并等操作。
②链式编码压缩方法：
用从某一起点开始沿8个方向前进的单位矢量链来表示线状地物或多边形的边界， 从而达到压缩数据量的方法 建立步骤：1）首先定义一个3×3窗口，对中间栅格的走向的8种可能进行编码。 2）记下地物属性码和起点行、列后，进行追踪，得到矢量链。如下图所示：
③块状编码压缩方法
是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号) 和半径，再加上记录单元的代码组成。数据对格式(初始行、列，半径，属性值)
1）大块图斑记录单元大，分辨率低，压缩比高; 小块图斑记录单元小，分辨率高，压缩比低。 2）块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。
④四叉树编码压缩方法
是指将栅格或图像沿中央位置等分成四部分，如果某一子区的所有网格都具有同样的属性值，则这个子区就不再继续分割；否则，就要把这个子区再等分成四个区域，直到每个子区都含有相同的属性值为止，据此再进行编码的方法。
一种可变分率的非均匀网格系统，是最有效的栅格数据压缩编码方法之一。 1、基本思想： 将 2n×2n 象元组成的空间区域(不足的用背景补上) 按四个象限进行递归分割，并判断属性是否单一，若单一则不分，若不单一，则递归分割。最后得到一颗四分叉的倒向树——四叉树。