2010-2011学年第二学期GIS算法基础

显然，若D[j]+arcs[j][k]

vk的路径更短。因此，如果D[j]+arcs[j][k]

（4）重复操作第二步、第三步共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。

在动态缓冲区生成算法中主要是针对哪两类特殊情况提出的？并写出他们的生成方法。

答：动态缓冲区生成是针对两类特殊情况提出的：

一类是流域问题：从流域上游的某一点出发沿流域下朔，河流的影响半径或流域的辐射范围逐渐扩大；相反，则逐渐缩小。

另一类是污染问题。污染源对邻近对象的影响程度随距离的增大而逐渐缩小。

（一）对于流域问题，可以基于线目标的缓冲区生成算法，采用分段处理的办法分别生成各流域分段的缓冲区，然后按某种规则将各分段缓冲区光滑连接；也可以基于点目标的缓冲区生成算法，采用逐点处理的办法分别生成沿线各点的缓冲圆，然后求出缓冲圆序列的两两外切线，所有外切线相连即形成流域问题的动态缓冲区。

（二）针对污染问题，根据物体对周围空间影响度变化的性质，通过引入一个影响度参数，给出了3种动态缓冲区分析模型: （1）物体对周围空间的影响度Fi随距离di呈线性衰减： （2）物体对周围空间的影响度Fi随距离di呈二次函数衰减： （3）物体对周围空间的影响度Fi随距离di呈指数衰减：

以上三式中f0为综合影响指数；d0为最大影响距离；di为某点的实际距离；ri为距离比。 请写出数据挖掘的步骤。

答：（1）数据清理（消除噪音或不一致数据，补缺）； （2）数据集成（多种数据源可以组合在一起）； （3）数据选择（从数据库中提取相关的数据）； （4）数据变换（变换成适合挖掘的形式）； （5）数据挖掘（使用智能方法提取数据模式）； （6）模式评估（识别提供知识的真正有趣模式）； （7）知识表示（可视化和知识表示技术）。

已知前序遍历的结果：{ABHFDECKG}，中序遍历的结果：{HBDFAEKCG} 请画出其二叉树图。

请详细说明光栏法实现矢量数据压缩的基本思想和实施步骤并作图表示。 光栏法的基本思想是：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为｛pi｝，i＝1，2，?，n，光栏口经为d，可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：

1、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两

点a1和a2，使a1p2＝a2p2＝d／2，此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形内的所

有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。 2、若p3点在扇形内，则舍去p2点。然后连接p1和p3，过p3作p1p3的垂线，

该垂线与前面定义的扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1＝p3b2＝d／2，若b1或b2点落在原扇形外面，则用c1或c2取代。此时用p1b1和p1c2定义一个新的扇形，这当然是口径(b1c2)缩小了的“光栏”。 3、检查下一节点，若该点在新扇形内，则重复第(2)步；直到发现有一个

节点在最新定义的扇形外为止。

4、当发现在扇形外的节点，如p4，此时保留p3点，以p3作为新起点，重

复1°～3°。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。