针时，把所遇到的各段弧线的代价加起来给出这条路径就是到目前为止用搜索算法找到的从到的最小代价路径。这个定义包含了。的估计依赖于有关问题的领域启发函数,。算法是种有序搜索算法，其特点在于对估价函数的定义。对于般有序搜索，总是选择值最小的节点作为拓展节点。因此是根据需要找到条最小代价路径的原则来估算节点的。可考虑每个节点的估价函数值分为两个分量从起始点到节点的代价以及从节点到达目标节点的代价。在算法中，最关键的问题是对下节点的选择，这就需要设置相应的启发函数进行优选。采用不同的启发函数可以有不同的效果。启发函数表示通常的表达式为其中是对试探点的估值，主要由和部分组成表示在状态空间中从起始点到节点的实际代价，即从起始搜索点到当前点的总代价，它代表了搜索的广度的优先趋势，当时，可以省略，而提高效率，减少计算的复杂度。是从到目标节点最佳路径的估计代价，即从当前节点到目标节点的估值，在这里主要体现了搜索的启发信息，因为是已知的。的设定是启发式搜索中最为重要的部分，设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为算法。由于估值函数是未知的，因此所构造的函数能否成为算法需要满足四条件路网中存在从起点到终点的最优路径，即解必须存在。问题域必须有限，即算法的有界性。路网中每个节点的代价值要大于零，即数据的非负性。设代表节点的实际代价值，则估计值必须小于等于，该条件需要对进行合理的设计,。当上述条件均能满足时，则采用该算法定能够找到最优解。般的对于实际情况中的搜索问题，都能满足前三个条件，其设计的难点在于上，在设计时不能与的差距过大，否则的区分能力会大为减弱。理想的情况的设计是能够小于并接近。因而值就是从开始约束通过节点的条最佳路径的代价，而。算法的搜索过程可以表述如下首先创建两个表和，表保存了所有已生成而未考察的节点，表中记录已访问过的节点。把放入表，记，令为空表。重复下列过程，直到找到目标节点为止。若为空表，则宣告失败。选取表中未设置过的具有最小值的节点为最佳节点，并将其放入表中。若为目标节点，则成功求得解。若不是目标节点，则继续扩展之，产生后继节点。对每个进行下列过程建立从返回的指针。计算,。如果属于，则称此节点为，并把它添加至的后继节点表中。比较新旧路径的代价。如果，则重新定义的父辈节点为，记下较小代价，并修正值。若节点的代价较低或者样，则停止扩展节点。若不在表中，则看其是否在表中。若不在表中，则转向。若在，中都不存在，则把它放入表中，并填入后裔表，然后转向。计算值算法的参考框图如图。图算法的程序框图开始把放入表中，记表是否为空失败取表中未设置过的具有最小值的节点，放入表中。是否属于否是成功否扩展，产生其后继节点若，添加到的后继节点表中把放进表中，添加到的后裔表中建立从返回的指针计算，是目标节点否是是否属于是否是否属于是重新确定的父辈节点为，并修正值和值，记下计算值根据算法的定义，我们可以对节点引入估价函数，定义为其中，是道路的长度是当前节点到目标节点的直线距离。总之，算法的目标是使最小化，从而获得最优路径。当然，估值函数的设计也不仅仅是的种，另外的估值函数也可以进行下权重的调节如采用不同的启发函数实际上是代表了不同的寻优策略，因而针对不同的具体问题也会出现不同的效果。很明显，算法占用的存储空间比算法小。若将节点的平均出度记为，从起点到终点的搜索深度记为，则算法的时间复杂度为。但是如果各路段上路阻权值为非线性的，用评价函数很难将其表达出来，在不同程度上使启发式算法性能降低。本章小结路径搜索问题本质上是在网络图中寻找特定节点之间代价最小的通行路径在这里不讨论单点对多点和多点对多点的情况。本章首先介绍了路径搜算法的般原理，主要介绍了盲目搜索和启发式搜索的原理和特点。分别选取经典的盲目算法算法和启发式算法算法。应该说两种算法各有优缺点，算法原理简单明了，应用方便，并且保证可以搜索到图中的最短路径，应用较为广泛，算法不仅可以找到特定两点见的最短路径，并且可以给出从起始点到所有顶点的最短路径。但是当网络中节点数目较多时，搜索的开销会很大大，导致效率很低。通过改进地图数据的存储结构可以定程度的提高算法的运行效率，今后可以在该方面进步研究。启发式算法是近年来兴起的新的研究方向，作为启发式算法的代表，具有启发式算法的系列特点。通过设置启发函数，能够从备选点中选择具有最小代价值的点作为优先的后继节点，因而避免了大范围的搜索过程，减少搜索的成本，特别是对于数据规模比较大的地图，其效率提升是非常明显的。但是启发式算法的目标性比较强，其对路径的选择也可能因为过于依赖启发算子导致丢失最优解。但是通过不断改进算法的启发函数，可以基本达到满意的求解结果。从未来的发展来看，路径搜索算法也不仅仅局限于这些经典的算法，很多研究通过将不同算法进行结合，来消除各种算法的缺点，达到有数互补。例如将双向搜索的原理应用到对最短路径算法和启发式搜索算法可以节省不少的运算过程，另外从数据结构方面进行定的优化设置也可以起到很好的效果。本文的研究主要侧重方法原理和算法实现，对于算法的改进还需进步的研究。第五章出警路径最优化算法的实现引言即地理信息系统，经过了年的发展，到今天已经逐渐成为门相当成熟的技术，并且得到了极广泛的应用。它通过将地图信息直接输入计算机，利用相关软件将信息存储于地图上与之相关联的地理位置上，使数据与地理信息紧密结合起来，实现数据的可视化，便于对数据进行有效的管理分析和组织，为进步做出决策提供良好的人机界面和依据。近些年，更以其强大的地理信息空间分析功能，在及路径优化中发挥着越来越重要的作用。地理信息系统是以地理空间数据库为基础，在计算机软硬件的支持下，运用系统工程和信息科学的理论，科学管理和综合分析具有空间内涵的地理数据，以提供管理决策等所需信息的技术系统。本章主要是在地图信息平台下，运用其自带的二次开发环境进行优化程序的开发。首先对潍坊市城区道路环境进行数字化，提取区域路网交通信息，在此基础上，对第四章介绍的两种路径优化算法进行实现。通过对实际道路信息进行算法优化发现，作为启发式算法代表的算法在运算时间上具有较大的优势，特别是在实际中，城市路网非常复杂，运算数据较多，启发式算法可以节省大量的运算时间。在结果上，算法得到的结果更加精准，对于全域来说算法的结果是最理想的。对于出警的实际需要来说，节省必要的运算时间更加重要，如果路网过于复杂，则倾向于算法，反之通过对算法进行必要的改进则更为合适。地图数字化在进行算法的实现时，首先要对地图进行数字化处理。这主要应用到地理信息系统技术进行处理。地理信息系统是门由地理学计算机科学测绘遥感学城市科学环境科学信息科学空间科学和管理科学融为体的新兴学科。系统以地理空间为基础，利用地理模型的分析方法及时提供多种空间动态的地理信息，从而为有关经济决策服务。越来越受到重视的种存储地理信息技术，它通过将地图信息转化为计算机数据，并利用相关软件将信息存储于地图上相应的地理位置上，使数据与地理信息紧密结合，实现数据的可视化，便于对数据进行有效的管理分析和组织，为进步做出决策提供良好的人机界面和依据,。地图数字化是将地图图形或图像的模拟量转换成离散的数字量的过程。其主要种类有跟踪数字化和扫描数字化。前者使用跟踪数字化仪手扶或自动将地图图形要素点线面进行定位跟踪，并量测和记录运动轨迹的，坐标值，获取矢量式地图数据。后者使用扫描数字化仪对地图沿或方向进行连续扫描，获取二维矩阵的象元要素，形成栅格数据结构。在数字化时，需要借助地理信息系统软件平台进行实现。数字化平台地理信息系统的核心是空间数据管理子系统，它由空间数据处理和空间数据分析构成。空间数据的主要来源有专题地图遥感图像数据统计数据及实测数据等。地理信息系统具有七大功能数据的提取转换和编辑，数据的存储与管理，数据重构和数据转换，空间数据的查询和检索，空间操作和分析，空间显示和成果输出以及空间数据的更新。与般的管理信息系统相比，地理信息系统更强调了空间分析功能，在分析处理问题中使用了空间数据与属性数据，这些特性为处理空间问题带来了极大的方便。是地理信息系统应用软件的种，该软件操作简便，并且提供了自带的二次开发平台，用户可以在该平台上开发自主的应用，具有极好的适应性。软件的数据结构采用文件系统，将非空间数据和空间数据揉合在起，它利用个文件来描述个图层。分别是文件文件文件以及交叉索引文件。其中文件是属性数据的结构定义，用于描述非空间数据的结构文件是对属性数据信息的描述，用于描述非空间数据的值文件顾名思义，即存储图形信息，用与存储空间图形对象数据交叉索引文件用来实现图形与属性数据的可视化，该文件利用交叉索引文件在空间数据和非空间数据之间建立关联，将图形与属性无缝融合。通过这四个文件的相互结合，在单机环境下运行时，就可以完美地形成空间图形数据和非空间属性数据之间的映射关系，实现地图与数据的互查互动，方便编程实现地图的处理功能。通过表的形式把地图和数据有机地结合在起，地图中的每个图层对应着个表，图层上的每个图形对象对应着表中的行记录。当在图层上新建或删除个对象时，相应的表中就增加条记录。二次开发的方法主要有两种，即利用自身所带的开发工具和利用诸如等优秀的开发工具。采用适当的开发工具对地理信息系统进行二次开发是系统建立的关键因素之。