·168 智能系统学报 第7卷 邻接矩阵的优势在于容易判断2点间的关系，但 选取图中的1、2、3、4、5点作说明，如图2所示 缺点是存储稀疏图所占用的空间过大，并且算法时间 例如：节点1指向节点2、3，那么节点1的指针指向 复杂度较高，为O(n2+m*n),这对于实际应用中具 节点序列中的2、3，依此类推，将转向条件计入在下 有成千上万个节点的交通路网图并不合适.十字链表 一个节点中，就是图2中代价函数值所代表的， 和邻接多重链表要求的存储空间都非常小，但是本身 节点指针节点序列 代价听数值 结构较为复杂，在实际中应用也比较有限. 0 2 空 12右12直 13左13直 邻接链表的实现方法是链表，缺点在于不易判 5 空 21石 空 断2点间的关系，但是对于关联点的查询较为有效， 4 空 24右24直24左 12 空 27石 空 优点是节省存储空间，算法时间复杂度为0(m+ 31右 空 空 粉 n).因此适用于实际交通网络这类大型稀疏图，本 4 34左 空 34右 34直 空 35左 空 空 文采用的存储方式就是邻接链表1」 42左 空 42右 436 1.2路径代价函数值的计算 空 43左 53直53石 空 源点和终点间的所有可达路径中，路径总代价 函数值最小者即为最优路径.可达路径的总代价函 图2前向关联边结构及其对应代价函数值 Fig.2 Associated side of the structure and its cost 数值是全部构成路段的代价函数值的总和，此外，由 function value 于交叉路口对转向的种种限制，延误时间可达到总 根据指针对应的节点序列找到二维数组的行，再 时间的17%~35%[91，因此在计算每条可达路径的 通过下一结点的偏移量找到对应的二维数组的列，即 代价函数值时，还必须考虑交叉口转向因素的影响， 在作者前期的工作中o,已利用RBF神经网 可求出每一段路径的代价函数值，最后将路径中每一 络方法建立了路段的代价函数模型，将5种道路属 路段的代价函数值加起来，就得到了整条路径的代价 性作为影响因素设为RBF网络的输人，网络输出为 函数值，然后根据代价函数值从小到大对可达路径进 路段代价函数值，这5种道路属性包括：道路交通实 行排序并显示出来，供使用者参考选择21」 时路况、车道数、自助红绿灯数、路段长度及车辆转 1.3城市交通可达路径算法的优化 向方向对行车代价函数值的影响，从而为计算整条 本文采用深度优先遍历算法求得交通图中任意 路径的总代价函数值打下了基础. 2点之间的所有可达路径，具体通过深度优先遍历 但是，计算整条路径代价函数值的难度在于每 算法中的迭代算法来实现.迭代算法利用一个堆栈 ·条路段的代价函数值是在已知转向的情况下得到 S来记录访问过程，当初始点（源点）压入栈后，并建 的结果.因此，本文通过建立前向关联边，并采用查 立一个ist[]数组来标记节点是否被访问过，然后 表的方法解决每一条路径总的代价函数值的计 进行迭代，步骤如下： 算们，即将3个点之间的关系两两合并，得出二维 1)检测堆栈是否为空，若堆栈为空，则迭代结 数组的行数和列数，然后将每一段加起来，即可得到 束；否则，进行下一步； 每一条路径的代价函数值.特别地，在终点和它上一 2)访问源点的邻接表中的点，找出isit[v]为0 个节点的代价函数值的计算中，设置了一个数组存 的点v,将其标记为源点的下一节点，并置isit[v] 放最后一段路段的代价，因为通常到达了终点不存 的值为1，判断是否为终点，如是，则弹出终点，并 在选择方向的问题，从而将这个数组中的值设置为 记录路径数组route[],否则进行下一步； 直行的代价函数值.以图1为例，进行简单说明. 3)求v的邻接点表，将v未被访问过的邻接顶 点压入栈，同样进行判断是否为终点，如是终点则 弹出，记录路径，否则进行下一步； 重复进行1)~3)： 设计程序流程如图3所示.在此过程中，每一个 节点都已经记录了上一个节点，即route[v],算法结 束后，逆序打印每一条路径，即可得到图中任意2点 间的所有可达路径 上述算法并不复杂，对于有向图中寻找任意2 图1有向图 Fig.1 Directed graph 点间所有可达路径十分有效.但是该算法存在2个 问题：1)搜索很多冗余可达路径，不符合常理的“绕