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

基于导航最优路径算法的设计与实现概要设计总页数 正文 附录 生效日期 2013.12编制 批准南昌航空大学东软班 概要设计修 改 履 历修改编号 日期 修改人 版本号 修改内容1 VER0.1.0 初始做成南昌航空大学东软班 概要设计目 录1 文档概述 .41.1 文档目的和范围 .41.2 术语/缩略语 .41.3 参考文档 .42 模块概述 .42.1 模块功能定义 .52.2 模块结构 .52.3 模块动作时序 .73 接口说明 .73.1 数据结构定义 .73.2 函数 .83.2.1 模块间接口函数 .83.2.2 模块内接口函数 .11南昌航空大学东软班 概要设计1 文档概述1.1 文档目的和范围该项目主要是完成地图中两点之间最优路径的搜索，界面的输入与输出，最短路径算法之间优劣的对比等。本文档就是对该项目模块的划分，模块的功能设计以及模块之间的调用关系做了概要性的描述。1.2 术语 /缩略语序号 术语/缩略语 说明1 Dijkstra 算法Dijkstra 算法是典型并且很有代表性的算法。Dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 OPEN, CLOSE 表的方式。2 Floyd 算法Floyd 算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。3 A*算法A*算法，A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。估价值与实际值越接近，估价函数取得就越好。1.3 参考文档序号 文档名 作者 时间 版本1 交通网络中最短路径算法的研究 戴文舟 20042 最短路问题在运输网络中的应用 李玲 20062 模块概述本项目主要分为地图数据存取、最优路径搜索、界面显示与输出等三个模块。地图数据存取模块负责将地图数据以文件的形式存储，并解析到程序中进行调用。最短路径算法模块主要通过界面模块传递的起点与终点信息，调用不同的最短路径算法求出最短路径。界面模块主要负责用多线程技术和绘图技南昌航空大学东软班 概要设计术实现界面的显示与输出功能。2.1 模块功能定义序号 功能点 功能点详细内容1.1 地图数据解析 从文件中读取地图信息，并将数据放入程序内数据结构中。1.2 地图数据存储 将用户更改过后的地图文件，以文件的形式存储起来。2.1 Dijkstra 算法实现 通过 Dijkstra 算法计算两点之间的最优路径。2.2 Floyd 算法实现 通过 Floyd 算法计算两点之间的最优路径。2.3 A*算法实现 通过 A*算法计算两点之间的最优路径。3.1 界面信息输入处理 接收用户在界面上输入的起点、终点等信息。3.2 地图载入 将存有地图信息的数据结构解析并绘制在界面中。3.3 最短路径显示 将最短路径模块计算出来的最短路径动态的显示在界面上。南昌航空大学东软班 概要设计2.2 模块结构最优路径算法研究地图数据处理模块最优路径搜索模块界面信息处理模块地图数据读出模块地图数据写入模块A * 算法搜索最优路径模块F l o y d算法搜索最优路径模块界面显示输出模块界面信息输入处理模块D i j k s t ra 算法搜索最优路径模块图 1 组织架构图模块名称 模块类型 概要说明地图数据写入 内部模块 接收界面信息写入模块传入的数据，并将用户对地图的修改传入地图数据结构体中。地图数据读出 内部模块 将地图数据进行编码，并传到最优路径搜索模块，进行搜索起点到终点的最优路径。A*算法搜索最优路径内部模块 调用 A*算法搜索起点到终点的最优路径，并将最终结果传入界面显示输出模块。Dijkstra 算法搜索最优路径内部模块 调用 Dijkstra 算法搜索起点到终点的最优路径，并将最终结果传入界面显示输出模块。Floyd 算法搜索最优路径内部模块 调用 Floyd 算法搜索起点到终点的最优路径，并将最终结果传入界面显示输出模块。南昌航空大学东软班 概要设计界面显示输出模块内部模块 读取地图数据，进行界面的绘制。并且接收最优路径搜索模块传入的信息，将最优路径动态的显示在界面上。界面信息输入处理模块内部模块 接收用户对起点、终点等数据的输入，并将其传递给最短路径算法模块。如果用户对地图有修改，则地图修改信息传给地图数据写入模块。2.3 模块动作时序界面信息处理 最优路径搜索 地图数据处理顶层包 : : 用户用户信息输入起点终点信息地图数据修改信息修改成功与否最优路径结果返回结果反馈算法种类选择图 2 模块时序图3 接口说明3.1 数据结构定义struct tagNode /保存地图中节点的信息的结构体long ID; /节点的编号long x,y;/节点的横纵坐标double g;/起点到该节点的路程权值double h;/该节点到终点的路程估计权值double f;/g和h的相加值long Neighbor10; /该节点的邻节点的编号 南昌航空大学东软班 概要设计;long shortest_pathnum; /最短路径上所经过节点的 ID 值3.2 函数3.2.1 模块间接口函数3.2.1.1 Map_read函数名 Map_read文件名 ./Map_read.cpp功能概要 地图数据读取记述形式 Int Map_read ( int f )参数 类型 变量名 I/O 说明int f I 文件描述符类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明Map 初始化处理函数，提供给地图信息存取模块调用。使用注意事项无3.2.1.2 A_star_algorithm函数名 A_star_algorithm文件名 ./A_star_algorithm.cpp功能概要 用 a*算法计算起点与终点之间的最短路径南昌航空大学东软班 概要设计记述形式 int A_star_algorithm(tagNode start , tagNode end)参数类型 变量名 I/O 说明tagNode start I 起点tagNode end I 终点类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用 a*算法计算点 start 到点 end 的最短路径。使用注意事项数据类型 tagNode 为自行定义的点数据结构体。3.2.1.3 Dijkstra_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 为自行定义的点数据结构体。南昌航空大学东软班 概要设计3.2.1.4 Floyd_algorithm函数名 Floyd_algorithm文件名 ./Floyd_algorithm.cpp功能概要 用 Floyd 算法计算起点与终点之间的最短路径记述形式 int Floyd_algorithm(tagNode start , tagNode end)参数类型 变量名 I/O 说明tagNode start I 起点tagNode end I 终点类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用 Floyd 算法计算点 start 到点 end 的最短路径。使用注意事项数据类型 tagNode 为自行定义的点数据结构体。3.2.1.5 Get_se_node函数名 Get_se_node文件名 ./Get_se_node.cpp功能概要 从界面中接收用户输入的起点与终点数据参数类型 变量名 I/O 说明tagNode start O 起点信息tagNode start O 终点信息类型 int 说明返回值值 MAINLCDSUCCESS 正常结束南昌航空大学东软班 概要设计MAINLCDFAILED 异常结束详细说明从界面中接收用户输入的起点与终点数据，并通过传引用调用放入传入的参数中。使用注意事项传参方式为传引用调用。3.2.2 模块内接口函数3.2.2.1 UI_display函数名 UI_display文件名 ./UI_display.cpp功能概要 界面显示记述形式 int UI_display(Map a)参数类型 变量名 I/O 说明Map a I 地图信息结构体类型 int 说明MAINLCDSUCCESS 正常结束返回值值MAINLCDFAILED 异常结束详细说明调用自定义的地图信息结构体，将地图信息显示在界面上。使用注意事项Map 为自定义的地图信息结构体类型。3.2.2.2 UI_update函数名 UI_update文件名 ./UI_update.cpp南昌航空大学东软班 概要设计功能概要 将计算出的最