ta栅格算法

1. A*算法用于路径规划，有什么缺点

缺点：A*算法通过比较当前路径栅格的8个邻居的启发式函数值F来逐步确定下一个路径栅格，当存在多个最小值时A*算法不能保证搜索的路径最优。
A*算法；A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。A*[1] （A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

2. 栅格数据的编码方法

编码方法
在栅格文件中，每个栅格只能赋予一个唯一的属性值，所以属性个数的总数是栅格文件的行数乘以列数的积，而为了保证精度，栅格单元分得一般都很小，这样需要存储的数据量就相当大了。通常一个栅格文件的栅格单元数以万计。但许多栅格单元与相邻的栅格单元都具有相同的值，因此使用了各式各样的数据编码技术与压缩编码技术。主要的编码技术简介如下：
（一）直接栅格编码
直接栅格编码是将栅格数据看作一个数据短阵，逐行或逐列逐个记录代码。可每行从左到右逐个记录，也可奇数行从左到右，偶数行从右到左记录，为特定目的也可采用其它特殊顺序。通常称这种编码的图像文件为栅格文件，这种网格文件直观性强，但无法采用任何种压缩编码方法。图2.1 (c)的栅格编码为：4，4，4，4，7，7，7，7；4，4，4，4，4，7，7，7；4，4，4，4，9，9，7，7；0，0，4，9，9，9，7，7；0，0，0，9，9，9，7，7；0，0，0，9，9，9，9，9；0，0，0，0，9，9，9，9；0，0，0，0，0，9，9，9。可用程序设计语言按顺序文件或随机文件记录这些数据。
（二）链式编码
链式编码又称弗里曼链码或世界链码。它由某一原始点和一系列在基本方向上数字确定的单位矢量链。基本方向有东、东南、南、西南、西、西北、北、东北等8个，每个后继点位于其前继点可能的8个基本方位之一。8个基本方向的代码可分别用0，1，2，3，4，5，6，7表示，既可按顺时针也可按逆时针表示。栅格结构按逆时针编码上图（2）可记录为：1，3，7，7，7，6，6，5，4。其中前两个数字1与3表示线状物起点的坐标，即在第一行第三列，从第三个数字起表示单位矢量的前进方向。
链式编码有效地压缩了栅格数据，尤其对多边形的表示最为显着，链式编码还有一定的运算能力，对计算长度、面积或转折方向的凸凹度更为方便。比较适于存储图形数据。但对边界做合并和插入等修改编辑工作很难实施，而且对局部修改要改变整体结构，效率较低。
（三）游程编码
游程编码是栅格数据压缩的重要且比较简单的编码方法。它的基本思路是：对于一幅栅格图像，常有行或列方向相邻的若干点具有相同的属性代码，因而可采用某种方法压缩重复的记录内容。方法之一是在栅格数据阵列的各行或列象元的特征数据的代码发生变化时，逐个记录该代码及相同代码重复的个数，从而可在二维平面内实现数据的大量压缩。另一种编码方案是在逐行逐列记录属性代码时，仅记录下发生变化的位置和相应的代码。图2.1 (c)栅格结构按游程编码方法可记录为：
第一行4,47,4
第二行4,57,3
第三行4,49,27,2
第四行0,24,19,37,2
第五行0,39,37,2
第六行0,39,5
第七行0,49,4
第八行0,59,3
在这个例子中，原本64个栅格数据，只用了40数值就完整地表示了出来，可见用游程编码方法压缩数据是十分有效的。
游程编码的编码和解码的算法都比较简单，占用的计算机资源少，游程编码还易于检索、叠加、合并等操作，在栅格单元分得更细时，数据的相关性越强，压缩效率更高，数据量并没有明显增加。因此，该编码适合微型计算机等中央处理器处理速度慢，存储容量小的设备进行图像处理。
（四）块式编码
块式编码是游程编码扩展到二维空间的情况，游程编码是在一维状态记录栅格单元的位置和属性，如果采用正方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由记录单元中左上角的栅格单元的行、列号（初始位置）和记录单元的边长（半径）与记录单元的属性代码三部分组成，这便是块式编码。因此可以说，游程编码是块式编码的特殊情况，块式编码是游程编码的一般形式。图2.1 (c)表示的栅格结构按块式编码方法可记录为：
（1，1，3，4），（1，4，1，4），（1，5，1，7），（1，6，2，7），（1，8，1，7）；
（2，4，1，4），（2，5，1，4），（2，8，1，7）；
（3，4，1，4），（3，5，2，9），（3，7，2，7）；
（4，1，2，0），（4，3，1，4），（4，4，1，9）；
（5，3，1，0），（5，4，2，9），（5，6，1，9），（5，7，1，7），（5，8，1，7）；
（6，1，3，0），（6，6，3，9）；
（7，4，1，0），（7，5，1，9），
（8，4，1，0），（8，5，1，0）。
从以上论述的块式编码的编码原理可知，一个记录单元所表示的地理数据相关性越强，也即记录单元包含的正方形边长越长，压缩效率越高。而地理数据相关性差时，也即多边形边界碎杂时，块式编码的效果较差。
块式编码的运算能力弱，必要时其编码的栅格数据须通过解码转换成栅格矩阵编码的数据形式才能顺利进行。块式编码在图像合并、插入、面积计算等功能方面较强。
（五）四叉树数据结构
四叉树编码又名四元树编码，可以通俗理解为一个具有四分枝结构的树，它具有栅格数据二维空间分布的特征，这是一种更为有效的编码方法。四叉树编码将整个图形区域按照四个象限递归分割成2n×2n象元阵列，形成过程是：将一个2×2图像分解成大小相等的四部分，每一部分又分解成大小相等的四部分，就这样一直分解下去，一直分解到正方形的大小正好与象元的大小相等为止，即逐步分解为包含单一类型的方形区域（均值块），最小的方形区域为一个栅格单元。这个倒向树状的图中“○”表示可继续分割的方形区域；“□”表示具有同类属性的方形区域；“■”表示不能再分的单个（最小）象元栅格，即所谓的树叶，树叶表示的是具有单一类型的地物或是符合既定要求的少数几种地物，可以在任意层上。
通过以上对四叉树结构的分析，可发现它有以下特点：
⑴ 存储空间小：因为记录的基本单位是块，不是象素点，因此大大地节省了存储空间。
⑵ 运算速度快：因为四叉树结构的图形操作是在数上进行的，比直接在图上运算要快得多。
⑶ 栅格阵列各部分的分辨率可变：不需要表示许多细节的地方，分级较少，因而分辨率低；边界复杂的地方分级较多，分辨率高，因而在减少数据量的基础上满足了数据精度。
⑷ 容易有效地计算多边形的数量特征。
⑸ 与栅格结构之间的转换，比其它压缩方法容易。
⑹ 四叉树编码表示多边形中嵌套其它属性的多边形时比较方便：它允许多边形嵌套多边形的结构，是非常实用的、重要的特点，这点深深得到地理信息系统数据编码设计者的青睐。
⑺ 四叉树编码的不足之处是：转换具有不确定性，对大小相等形状相同的多边形，不同人可能分解为不同的四叉树结构，因而不利于形状分析和模式识别。四叉树编码处理结构单调的图形区域比较适合，压缩效果好，但对具有复杂结构的图形区域，压缩效率会受到很大影响。
（六）八叉树与十六叉树结构
前面的数据结构都是基于二维的，在相当多的情况下，如地下资源埋藏、地下溶洞的空间分布，二维的坐标体系根本无法表达。因此需要有三维数据结构，如果考虑空间目标随时间变化，那还需要4维数据结构。较好的表达三维与四维结构是在四叉树基础上发展起来的八叉树（三维）和十六叉树（四维）。
是将空间区域不断地划分为八个同样大小的子区域，
（七）各种编码的比较分析
比较以上各种编码，可得出如下主要结论：
⑴ 直接栅格编码直观简单，但数据出现大量冗余；
⑵ 链式编码对边界的运算方便，压缩效果好，但区域运算较困难；
⑶ 游程编码即较大幅度地保留了原始栅格结构，又有较高的压缩效率，而且编码解码也较容易，但仅局限在一维空间上处理数据；
⑷ 块式编码在图像合并、插入、面积计算等功能方面较强，当所表示的地理数据相关性强时，压缩效率相当高；但地理数据相关性差时，块式编码的效果较差，而且块式编码的运算能力较弱；
⑸ 四叉树编码运算速度快，存储空间小，分辨率可变，压缩效率高，但其转换具有不确定性，难以形成统一算法。