详细设计-基于导航最优路径算法的设计与实现

基于导航最优路径算法的设计与实现详细设计总页数 正文 附录 生效日期 2013.12.23南昌航空大学东软班 详细设计报告 版本：0.1.0编制 批准南昌航空大学东软班 详细设计报告 版本：0.1.0修 改 履 历修改编号 日期 修改人 版本号 修改内容1 0.1.0 初始做成南昌航空大学东软班 详细设计报告 版本：0.1.0目 录1 文档概述 .31.1 文档目的和范围 .31.2 术语/缩略语 .41.3 参考文档 .42 处理 .42.1 模块数据结构定义 .42.1.1 全局变量定义 .42.2 模块功能实现 .52.2.1 模块内部函数 .5南昌航空大学东软班 详细设计报告 版本：0.1.01 文档概述1.1 文档目的和范围此文档是对基于导航最优路径算法的设计与实现的详细设计描述，主要是描述了本模块与其它模块的接口函数和内部接口函数以及内部函数的定义、流程图和构成图以及测试项目的记述。1.2 术语 /缩略语序号 术语/缩略语 说明1 Dijkstra 算法Dijkstra 算法是典型并且很有代表性的算法。Dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 OPEN, CLOSE 表的方式。2 Floyd 算法Floyd 算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。3 A*算法A*算法，A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。估价值与实际值越接近，估价函数取得就越好。1.3 参考文档序号 文档名 作者 时间 版本1 交通网络中最短路径算法的研究 戴文舟 20042 最短路问题在运输网络中的应用 李玲 2006南昌航空大学东软班 详细设计报告 版本：0.1.02 处理2.1 模块数据结构定义2.1.1 全局变量定义struct tagNode /保存地图中节点的信息的结构体long ID; /节点的编号long x,y;/节点的横纵坐标double g;/起点到该节点的路程权值double h;/该节点到终点的路程估计权值double f;/g和h的相加值long Neighbor10; /该节点的邻节点的编号 ;long shortest_pathnum; /最短路径上所经过节点的 ID 值2.2 模块功能实现2.2.1 模块内部函数2.2.1.1 Map_read【函数式样】函数名 Map_read（）文件名 Map_read.c功能概要 地图数据读取南昌航空大学东软班 详细设计报告 版本：0.1.0记述形式 Int Map_read ( int f )参数类型 变量名 I/O 说明Int f I 文件描述符类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明Map 初始化处理函数，提供给地图信息存取模块调用。使用注意事项无2.2.1.2 A_star_algorithm【函数式样】函数名 A_star_algorithm（）文件名 A_star_algorithm.cpp功能概要 用 a*算法计算起点与终点之间的最短路径记述形式 int A_star_algorithm(tagNode start , tagNode end)参数 GtkWidget *but,gpointer data类型 变量名 I/O 说明tagNode start I 起点tagNode end I 终点类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用 a*算法计算点 start 到点 end 的最短路径。南昌航空大学东软班 详细设计报告 版本：0.1.0使用注意事项数据类型 tagNode 为自行定义的点数据结构体。【函数处理流程】开始把起始点 S 添加到 o p e n l i s tO p e n l i s t 是否为空从 o p e n l i s t 取得一个节点 X ， 并将其从 o p e n l i s t 中删除判断该 X 节点是否是目标节点取出 X 的所有子节点 Y ， 组成集合 Y Y 是否在 o p e n l i s t 和c l o s e l i s t 当中求 Y 的估价值 ； 并将 Y 插入 O P E N 表中若 Y 的估价值小于 O P E N 表的估价值 ，则 更新 O P E N 表中的估价值更新 C L O S E 表中的估价值 ，从 C L O S E 表中移出节点 ， 并放入 O P E N 表中将 X 节点插入 C L O S E 表中 , 按照估价值将 O P E N 表中的节点排序结束检查 c l o s e l i s t 是否为空 ， 若不空则将 c l o s e l i s t 输入作为最优路径Y e sN oY 不在 O P E N 表和 C L O S E 表中Y 在 O P E N 表中Y 在 C L O S E 表中N oY e s图 1 A*算法流程图南昌航空大学东软班 详细设计报告 版本：0.1.02.2.1.3 Dijkstar_algorithm【函数式样】函数名 Dijkstra_algorithm（）文件名 Dijkstra_algorithm.cpp功能概要 用 Dijkstra 算法计算起点与终点之间的最短路径记述形式 int Dijkstra_algorithm(tagNode start , tagNode end)参数类型 变量名 I/O 说明tagNode start I 起点tagNode End I 终点类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用 Dijkstra 算法计算点 start 到点 end 的最短路径。使用注意事项数据类型 tagNode 为自行定义的点数据结构体。【函数处理流程】注解：S 中顶点：从 V0 到此顶点的长度T 中顶点：从 V0 到此顶点的只包括 S 中顶点作中间顶点的最短路径长度南昌航空大学东软班 详细设计报告 版本：0.1.0开始令 S = V 0 , T = 其余顶点 对应的距离值 从 T 中选取一个其距离值为最小的顶点 W 且不在 S 中 ， 加入 S对其余 T 中顶点的距离值进行修改W = V i ?结束Y e sN o图 2 Dijkstra 算法图2.2.1.4 Floyd_algorithm【函数式样】函数名 Floyd_algorithm ()文件名 Floyd_algorithm.cpp功能概要 用 Floyd 算法计算起点与终点之间的最短路径记述形式 int Floyd_algorithm(tagNode start , tagNode end)参数类型 变量名 I/O 说明tagNode start I 起点南昌航空大学东软班 详细设计报告 版本：0.1.0tagNode end I 终点类型 Int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用 Floyd 算法计算点 start 到点 end 的最短路径。使用注意事项数据类型 tagNode 为自行定义的点数据结构体。【函数处理流程】开始初始化D i s ( i , j ) = j选取除了 u ， v 以及探索过的 k 点外的任一节点 k 。检查 D i s ( i , k ) + D i s ( k , j ) D i s ( i , j ) 是否成立将点 k 假如 D i s ( i , j ) 中 ， 更新 D i s ( i , j )是否还存在未探寻到的节点 k结束Y e sN oY e sN o南昌航空大学东软班 详细设计报告 版本：0.1.0图 3 Floyd 算法图2.2.1.5 Get_se_node【函数式样】函数名 Get_se_node文件名 Get_se_node.cpp功能概要 从界面中接收用户输入的起点与终点数据记述形式 void show_err(char *err)参数类型 变量名 I/O 说明tagNode start O 起点信息tagNode end O 终点信息类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明从界面中接收用户输入的起点与终点数据，并通过传引用调用放入传入的参数中。使用注意事项传参方式为传引用调用。2.2.1.6 UI_display【函数式样】函数名 UI_display ()文件名 UI_display.cpp功能概要 界面显示记述形式 int UI_display(Map a)南昌航空大学东软班 详细设计报告 版本：0.1.0参数类型 变量名 I/O 说明Map a I 地图信息结构体类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用自定义的地图信息结构体，将地图信息显示在界面上。使用注意事项Map 为自定义的地图信息结构体类型。2.2.1.7 UI_update【函数式样】函数名 UI_update ()文件名 UI_update.cpp功能概要 将计算出的最短路径信息更新到界面上记述形式 int UI_up