确定最优路径Р最优路径就是路径中最符合某种需求的一条路径,比如最短路径,就是从起点到终点的权值和最小的Р边。对图求最优路径的方法即称为最优路径算法,通常用计算机编程实现。Р在公路运输中,为了使运输的时间和花费最少(花费可以是油耗和费用),需要找到起点和终点的最优路径。这条最优路径可以是路程最短的路径,也可以是油耗最省的路径,依据实际需求而定。在实际应用中,知道起点和终点,便可用最优路径算法计算出路径,这对车辆的行驶有很好的指导作用。使用计算机编程实现,更能提高效率。Р2.4 系统规划Р?该系统主要分为三部分,分别是基本的障碍物拟合及水平切线的求取、区域存储并构造无向图、设定权值然后寻找最优路径。Р2.4.1 基本的障碍物拟合及水平切线的求取Р?本部分主要包括多个障碍物的曲线拟合、求取每个障碍物的凸极值点和过凸极值点做水平切线。Р2.4.2 区域存储并构造无向图Р?本部分主要包括对整个地图的区域进行遍历与编号和无向图的构造Р2.4.3 设定权值及寻找最优路径Р?本部分主要包括起点与终点的设定,计算出一个或多个通路,然后根据权值寻找出最优的路径Р2.5 系统流程分析Р?通过调查和分析,本系统的业务流程主要是:用户通过在画板上点击相应的点来构造障碍物,当障碍物完成之后,点击‘画切线’按钮开始对地图中所有的障碍物进行凸极值点的计算,然后在凸极值点处画水平切线,将整个地图划分为多个区域;之后用户选择出起点和终点,然后输入起点和终点所在的区域;最后点击‘完成’按钮,程序开始计算所有可行的路径,并标记出最优的路径。Р在用户的操作过程中和系统运行的过程中,程序都要时刻地记下重要的数据,方便之后的计算。程序存储的数据主要有:用户点击的点的坐标、每个障碍物的边界经过的点的坐标、每个障碍物的凸极值点的坐标、过凸极值点做的水平切线的两个端点的坐标和用来存储无向图的邻接表等等。Р图2-1 系统流程图
全文预览
