我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:516棋牌游戏 > 工程障碍物 >

矢量图中绕过障碍物的最短路径算法研究

归档日期:07-01       文本归类:工程障碍物      文章编辑:爱尚语录

  《自动化技术与应用》 年第 22 卷第 1 期 2003 计算机应用 Co mputer Applications 矢量图中绕过障碍物的最短路径算法研究 Algorithms For The Shorte st Path Ro unding Obstacle s In Vector Grap hic s 华中科技大学 陈传波 唐 浩 Chen Chuanbo , Tang Hao 摘 要 :通过比较几种常见的有障碍物时求最短路径的算法 ,在线探索算法的基础上提出了一种改良的求障碍物群中两点间最短路 径的近似算法 。 关键词 : 最短路径 探索线 绕障偏移量 Abstract : This paper compares several Algorithms for shortest path rounding obstacles and basing on the Line-searching algorithm , brings forward an im2 proved algorithm which can find the approximative shortest path. Kewords : The shortest path Serching- line Offset for obstacle rounding 1 引言 2 障碍物群中最短路径问题的定义 中图分类号 : TP11 文献标识码 : A 文章编号 : 100327241 (2003) 0120034203 运输管理以及工程设计的许多方面 ,如各种工艺路线的安 排 ,电网及管道线网的铺设 ,电子地图的寻路等问题 ,都与图的 最短路径问题密切相关 。在某些工程应用中 ,如设计电路图或 布线图时 ,常常碰到这样的情况 : 电路元件和已布好的连接线成 最小 。 为了布线障碍 。为了避免新的连接线穿越元器件 ,就必须按一 定的策略使得某些已作好的连接线作出规避 , 同时求出障碍群 中两点间的最短路径 ,按这条路径为新作的连接线布线 。 最短路径问题是 VLSI 设计和几何信息系统中的基本问题 , 是一种计算机图形搜索算法 , 即在出发点和目标点之间找出总 代价最低的路径 。路径寻优算法一方面要完成探索最低代价的 路径 ,另一方面要做到尽可能快 ,尽可能少占用内存 ,即尽可能 34 降低算法的时间复杂度和空间复杂度 。通常求最短路径是在一 个连通图中进行 ,各个节点由有向或无向的连线连接 ,而障碍物 群中最短路径指的是图中两点通过一条折线或曲线相连 , 不与 任一障碍物发生碰撞 ,且这条折线或曲线 几种经典算法 (Line- searching) 算法 。 现有的算法分为两类 : 走迷宫 (Maze- running) 算法和线搜索 Lee 算法为第一个走迷宫算法 , 它是广度优先搜索法的一 个应用 ,迷宫算法基于单元格点搜索 , 在时间和空间上是低效 的 ,因此人们提出了线搜索算法 。 线搜索算法的基本思想是构造一个代表障碍和结点位置的 图 , 通过在图中寻找最短路径得到原格点中的最短路径 [1 ] 。此 Technique s of Automation &Applications 计算机应用 Co mputer Applications 《自动化技术与应用》 2003 年第 22 卷第 1 期 类算法有以下特点 : (1) 构造的图比原单元格点图稀疏 ; (2) 构造的图具有代表性 ,图中的路径与原网格中的路径是 寸灵活调整探索起点及探索方向 。 4 改进的线探索算法 由于走迷宫法是基于网格的布线算法 ,采用这种算法要对 实际布线图作一定简化 ,以使得图形坐标数据位于网格上 。且 数据存储空间和路径搜索时间随线间距离的减少以平方关系而 增加 ,当布线图比较复杂 ,元器件特别多时 ,连接线宽度和线间 距离越来越少 ,走迷宫算法就显得有些力不从心了 。本文主要 对线探索算法进行了改进 ,下面详细叙述 。 等价的 ; (3) 对源结点和目标结点 ,构造的图中存在与原网格中的最 短路径对应的路径 ; (4) 构造图的复杂度决定了算法的复杂度 。 311 李氏迷宫算法的基本思想 312 线探索布线算法 李氏迷宫算法首先将布线区域分成单位网格 ,然后沿着网 格走线 ,且每个网格在一个方向上只允许布一条线 ,并在此基础 上搜索路径 。使用矩阵网格后 ,布线实际上是沿着曼哈坦路径 实现的 。在布线算法中 , 由于通常意义上的两点 ( x1 ,y1 ) , ( x2 , y2) 之间的欧几里德距离 sqrt ( ( x1 - x2) 3 ( x1 - x2) + ( y1 - y2) 3 (x1 ,y1) , ( x2 ,y2) 之间的曼哈坦距离 dm 定义为 dm = + x1 - x2 + + y1 - Y2 ,它实际上就是以两点为对角的矩形半周长 。 (y1 - y2) ) 计算涉及大量的浮点运算 , 计算速度慢 , 所以一般采 用曼哈埋距离来计算两点间连线间距 。在直角坐标系中两点 值得注意的是 ,采用这种算法之后 ,两点间的最短路径将不 唯一 。李氏算法就是在上述网格中实现的 ,它的基本思想可以 描述为波的传播过程的模拟 。在一个存在障碍的湖面上 ,若需 寻找连接 A ,B 两点的最小路径 , 可以在 A 点投下一枚石子 , 然 后观察所引起的水波传播情况 。假定 “水波” 传播时能量无损 失 ,当遇到障碍时 ,波产生反射 ,最先到达的目标点波前所经过 的路径必定是一条最短距离 。而且只要两点间有通路存在 ,则 自 A 点扩散出去的波一定能传播到 B 点 。 线探索布线算法本质上是一种无网格布线算法 ,在线探索 法中 ,不用存储各网点信息 ,只须存储外形尺寸 ,存储各连接线 宽度及端点坐标 。但在具体实现上 ,为了提高搜索效率 ,往往外 形尺寸一致 、 连线宽度一致 ,并将连线端点坐标网格化 ,线探索 是否依赖于网格 ,关键在于坐标是否网格化 。在基于网格的线 探索中 ,探索线端点及回溯处理时的步长都以网格为单位计算 。 在无网格线探索方案中 ,坐标以最小设计精度为单位 ,探索线端 点则根据障碍的几何尺寸及探索线与障碍之间的允许最小间隙 而计算 ,回溯处理以线间最小距离为步长 ,并结合障碍的几何尺 411 几个基本概念 (2) 探索线) 绕障偏移量 : (4) 登陆点 (5) 分离点 (1) 临界最短路径 : 连接两点的绕过中间障碍物的最短折线 ,其某些区段是所 要绕过的障碍物的边界 。 是一条以当前点为起点 ,有预定终点和一定宽度的水平 、 垂 直或斜向射线 。探索线的宽度即用来连接待连点对的连线宽 度 。探索过程实质上是一个检查计算过程 ,就是按照从起点至 预定终点的方向 ,逐一检查前面或两侧是否有元器件或已布连 线等障碍物阻碍探索线直通预定终点的过程 [2 ] 。 为了绕过障碍 ,最短路径不应与图元相交 ,由于临界最短路 径可能经过了障碍物的边界 ,因此必须加上一定的偏移量 ,称为 绕障偏离量 。相对每一障碍 ,可有正负两个绕障偏移量 。其中 , 负偏移量小于 0 ,正偏移量大于 0 。 当前点可见的障碍物上最近的顶点 。 绕过障碍物时探索线 示意图 如图所示 ,当运动物体 M 沿探索线 a 前进 ,如果碰到障碍 Technique s of Automation &Applications 35 《自动化技术与应用》 年第 22 卷第 1 期 2003 计算机应用 Co mputer Applications 物 O ,则 O 的顶点必定分布在 a 的两侧 , 且部分边是 M 可见的 (图中的实线边) , 部分是不可见的 ( 虚线边 ) , 把 M 可见的障碍 得到临界最短路径 S - v1 - v2 - v3 - E2 ( 图中红线 ) ,该路径的某 些区段是元器件的边界 。 物的顶点分成两组 ,矢量 a 左侧的顶点归入 L 组 ,右侧的归入 R 组 。另设 VL 和 VR 分别是 L 和 R 组中离 a 最远的两个顶点 。如 果 VL 比 VR 离 a 更远 , 则令 C = R , 否则令 C = L 。VC 就是登陆 点 。M 绕过障碍物时首先向登陆点靠近 。 找到登陆点后 ,接着就是如何绕过障碍物 O 。先把 S 与登 陆点 VC 连接 ,再把 VC 与 E 连接起来 。视 VC 为当前点 ,记做 P , 如果 PE 不与障碍物相交 ,表明已绕过了障碍物 , 称此 P 点为 M 绕过障碍物 O 的分离点 。否则把当前点从 P 出发顺着 ( 当 P 在 SE 的左侧) 或逆着 ( 当 P 在 SE 的右侧 ) O 的边界移到下一个顶 图2 两点间的最短路径 下一步 ,在边界最短路径的每一段 ,加上每个障碍物的相应 绕障偏移量 ,使得最短路径不与元器件相交 ,得到最终的近似最 短绕障路径 S - v1′ v2′ v3′ E2 ( 图中蓝线) 。 - 点上 。 绕过一个障碍物后 ,如果后面还有障碍物 ,就把当前点作为 新的起点重复上述过程 ,直到绕过所有障碍物到达终点 E 。 D 不能直达中止点 E , 中间存在障碍物 O′则求出以 D 为出发 , 412 基本思想 最短路径 。 物相交 。 5 结论 笔者将本算法的思想应用到电路布线图的绘制和 GIS 道路 搜索应用中 ,都取得了较好的效果 。由于本算法的探索线是从 起点指向终点的射线 ,且求出的最短路径是在临界最短路径的 基础上加上绕障偏移量得到的结果 , 绕障偏移量的计算也存在 一定误差 ,因此最终得到的两点间绕过障碍物的最短路径是近 似最短路径 [3 ] 。 (1) 在临界状态上 ,先不考虑线宽的影响 ,求出临界状态的 (2) 以第一步求出的临界最短路径为基准 , 考虑线宽等因 素 ,加上绕障碍偏移量 ,得出最终的最短路径 ,该路径不与障碍 413 算法步骤 36 首先将给定的起始点和中止点连起来 , 得到线段 SE , 从 S 指向 E 的射线 SE 为探索线 ,沿探索线探索前方是否有障碍物 。 找出与 SE 相交的第一个障碍物集合 O ,如果 O 不存在 ,则 SE 即 为所求的解 ,否则在 O 上找到登陆点 ,绕过 O 。如果 O 的分离点 6 参考文献 径 [J ]1 计算机学报 ,1999 ,5 与图形学学报 ,1998 ,5 算机工程 ,1999 ,3 [1 ] 周智 ,等 1 用 O ( tlogt ) 的连接图求有障碍时的最短路 [2 ] 杨凶 1 无网格线探索布线 障碍物群中近似最短路径的搜索算法 [J ] 计 点 ,E 为目标点时 O′ 上的登陆点 VC′ 。然后用与上述同样的方法 求出 D 到 VC′ 的通路和 VC′ E 的通路 。 到 如图所示 ,a ,b ,c ,d 表示障碍物 。S 与 E1 之间没有障碍物 , 最短路径为 SE1 ;S 与 E2 间存在障碍物 ,首先沿探索线 探索 , 发现前方有障碍物 b ,则绕过障碍物 b ,分离点为 v1 ,然后以 v1 为 新的起点 ,连接 v1 ,E2 ,得探索线 方向探索 , 绕 过障碍物 d ,分离点为 v2 ,最后绕过障碍物 c ,到达终点 E2 。此时 作者简介 :陈传波 ,教授 ,博导 ,华中科技大学计算机学院 。 Technique s of Automation &Applications

本文链接:http://designmyth.com/gongchengzhangaiwu/94.html