已阅读5页,还剩46页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
最短路问题及相关算法介绍 吕长虹华东师范大学数学系Email chlu Questionone 每天开车去上班 应该走那条使得达到公司的费用最低 时间最少呢 如何选择最优的路径呢 Questiontwo 在城市规划自己电网架设中 怎么设计才能使其耗费的资金最少 其实都涉及到一个相同的问题 最短路问题 最短路问路径不仅仅是一般地理意义上的距离最短 还可以延伸到其他度量 如时间 费用 线路容量等 相应的最短路问题就转化诶最快路径问题 最低费用问题 最短路径问题也是资源分配 线路设计及分析等优化问题的基础 图论中的最短路问题 shortestrouteproblem 是组合数学和图论中核心问题之一 是许多更深层次算法的基础 图的定义 图是一种由 顶点 组成的抽象网络 网络中的各顶点可以通过 边 实现彼此的连接 表示两顶点有关联 图一般用G来表示 其顶点集为V 边集为E 简述为G V E 右图就是图论中一个节点的图结构 一共有10个顶点 15条边 Petersen图 最短路问题就是在指定的网络中两个节点间寻找一条距离最小的路 网络就是用节点和边联结构成的图 如铁路网 公路网等 下图就是我们将一个实际区域结构 图结构化的结果 两种常见最短路问题 1 单源最短路问题 求某一个到其余个点的最短路问题 dijkstra算法2 多源最短路问题 求任意两点之间最短路问题 Floyd算法 Dijkstra算法更是被称为统治世界的十大算法之一 最短路算法一个经典应用 导航我们在百度地图上寻找驾车路径时 显然就是要寻找一条物理距离最短或者行驶时间最短的路线 那我们能否通过算法设计一个属于我们的导航呢 Dijkstra算法就可以帮助我们做到这一点 问题简述 现有在无向图G V E V为各顶点的集合 E边集合 W为每条路径的权值 满足权值大于零 需要求得从某个起始点v 到其余各点的最短路径 Dijkstra算法算法描述 Dijkstra算法描述 把图中顶点集合V分成两组第一组为已求出最短路径的顶点集合 用S表示 初始时S中只有一个源点 以后每求得一条到其余顶点的最短路径 就将加入到集合S中 直到全部顶点都加入到S中 算法就结束了 第二组为其余未确定最短路径的顶点集合 用U表示 按最短路径长度的递增次序依次把第二组的顶点加入S中 在加入的过程中 总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度 此外 每个顶点对应一个距离 S中的顶点的距离就是从v到此顶点的最短路径长度 U中的顶点的距离 是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度 Dijkstra算法步骤 算法的描述上看去相当复杂 我们给出下面例子来具体说明整个算法的运行流程 首先我们要有如下概念 假设P v km是从顶点v到km的一条最短路径 那对这条路径上任意其他一点ki 都有P上关于v ki的子路径为v到点ki的最短路径 即最短路径的子路径仍然是最短路径 最短路算法本质上上基于这种思想展开的 经典例子 Example 右图G 顶点集合V V1 V2 V3 V4 V5 V6 6个顶点 边集E V1V2 V1V3 V1V6 V2V3 V2V4 V3V4 V3V6 V4V5 V5V6 9条边 W 0 7 9 147 0 10 15 9 10 0 11 2 15 11 0 6 6 0 914 2 9 0 W wij 6 6为6阶方正 wij为ViVj边上权值 若无边相连 则为无穷 我们取源点为V1 即求V1到其余个点的最短距离 STEP1 开始阶段S V1 U V2 V3 V4 V5 V6 W wij 6 6为权值矩阵 向量D来记录每一步之后V1与其余各点之间的最短距离 初始阶段D 0 7 9 14 STEP2 将与V1距离最小的点V2放入S中 S V1 V2 U V3 V4 V5 V6 此时我们确定V1到V2之间的最短距离为7 计算V1与U中各点距离 必须最短路经过V2 再与向量D中比较取较小值作为新的D中取值 S13 W23 D12 10 7 17S14 W24 D12 15 7 22D13 min S13 D13 min 17 9 9 不变 D14 min S14 D14 min 22 22 变小 此时D 0 7 9 22 14 STEP3 将与V1距离最小的点V3放入S中 S V1 V2 V3 U V4 V5 V6 此时我们确定V1到V3之间的最短距离为9 计算V1与U中各点距离 必须最短路经过V3 再与向量D中比较取较小值作为新的D中取值 S14 W34 D13 11 9 20S16 W36 D13 2 9 11D14 min S14 D14 min 20 22 20 变小 D16 min S16 D16 min 11 14 11 变小 此时D 0 7 9 20 11 STEP4 将U中与V1距离最小的点V6放入S中 S V1 V2 V3 V6 U V4 V5 此时我们确定V1到V6之间的最短距离为11 计算V1与U中各点距离 必须最短路经过V6 再与向量D中比较取较小值作为新的D中取值 S15 W65 D1 11 9 20D15 min S15 D15 min 20 20 变小 此时D 0 7 9 20 20 11 STEP5 此时U中与V1距离最小的点为V4和V5放入S中 S V1 V2 V3 V4 V5 V6 U 此时我们确定V1到V4之间的最短距离为20 V1到V5之间的最短距离也为20 所有的点都在S中 算法终止 此时D 0 7 9 20 20 11 就是V1到其余各个点的最短距离向量 优点 缺点 优点 优点 缺点 缺点 这样利用Dijkstra算法设计一个属于我们自己的导航系统啦 但似乎在实际运行时效果并不理想 虽然算法本身就是最短路径 但路面交通变化复杂 由于路面施工导致道路封锁 同时还存在路堵 车祸等现象 导致算法输出的最优路径 实际上并不是我们想要的最优路径 路面道路封锁 路堵 车祸等现象 本质上可以理解为这条道路被封堵住了 即有一个障碍物出现在此处 阻碍我们继续前进了 这时候我们Dijkstra算法就失效了 有同学会问 去掉这条堵住的线段不就可以了 这样仍然可以用Dijkstra算法求解 事实上这是一种可行的思路 但如果这样操作每天我的导航系统就要花大量时间去进行线段删减 增加工作 系统维护成本增加 A 算法就是解决这类问题的一个有效算法 A 算法可以理解成Dijkstra算法 最佳优先搜索 最佳优先搜索简介 这个算法的运算流程跟Dijkstra的流程类似 只不过它考察的是选取点到终点的距离 并且这个距离的权值是评估出来的 这也就是启发式的思想 举例说明 如果说目标的终点在北面 那么越靠近北面的点权值就越小 那么算法在搜索过程中 所加入点集的点就会倾向于北面 因此不用搜索全图东南西北 更多的是搜索北面的点 速度来说会优于Dijkstra算法很多 A 算法描述 A 算法将两种算法结合起来 最为关键的就是它判断权值大小的函数f n 它定义f n g n h n 其中 g n 为起始点到任意节点n的权值 在路径搜索中 也就是说到n点需要付出的代价 换句话说 之前所叙述的Dijkstra算法 h n 表达的是从节点n到终点的估计权值 也就是前面所陈述的最佳优先搜索 从中可以看到 当h n 0的时候 这个算法就是Dijkstra算法 而当个g n 0的时候 这个算法就是最佳优先算法 h n 的值占比越大 这个A 算法的启发度越高 也就越不精确 但运算很快 相对的g n 的占比高时 这个算法更趋向于将全局的节点都加进点集进行对比 从而可以给出较优的解 但算法速度会变慢 算法过程 1 设定三个集合closelist openlist parentnode 其中 closelist中记录已经搜寻过的点 openlist中记录等待搜寻的点 parentnode则是用来记录搜寻的路径 最后回推找到结果路径 2 将起始点放入openlist 此时closelist与parentnode为空集 3 在openlist中选一个f n 值最小的点作为当前的节点 4 将其从openlist中移除 添加到closelist中 5 如果当前节点为终点 那么搜索结束 6 搜索当前节点的相邻节点 7 如果相邻节点不在openlist中 就将它添加到openlist中 并将当前点设为parentnode 8 如果当前节点已经在openlist中 那么重新计算g值 如果g值小于当前节点的g值 那么更新这个值并且更新parentnode 9 如果当前节点在closelist中或者无法通过 那么就不处理它 10 如果openlist没有终点或所在水平线两侧的相邻点 那么跳转到3步骤 如果有终点或所在水平线两侧的相邻点中的任何一个 则将其设为终点并结束完成当前任务规划 经典例子 我们需要从绿色格子搜寻路径到红色格子 我们假定横向 纵向移动的权值为10 对角线移动权值为14 格子的左上角是f n 左下角为g n 右下角为h n 的值 此处使用Manhattan方法估计h取值 计算从当前方格横向或纵向移动到达目标所经过的方格数 忽略对角移动 然后把总数乘以10 说明 对于障碍物存在的地方 我们认为无法通过 即不能经过任何和障碍有关的地方 甚至是单个点 所以对角线也无法走 初始搜索过程 1 起点A开始 openlist A 2 查看与起点A相邻的方格 忽略其中墙壁所占领的方格 把其中可走的方格也加入到openlist中 此时openlist A A1 A2 A3 A4 A5 A6 A7 A8 3 设置这些新加入点的父亲为A 4 更新openlist和closelist openlist A1 A2 A3 A4 A5 A6 A7 A8 closelist A 5 计算每个新加入openlist点的F G H值 并标注在相应位置 A A1 A2 A3 A4 A5 A6 A7 A8 下一步搜索的方格 1 从openlist中选择F值最小的 方格 节点A1 2 更新openlist和closelist openlist A2 A3 A4 A5 A6 A7 A8 closelist A A1 3 检查所有与它相邻的方格 忽略其中在closelist中或是不可走的方格 如果方格不在openlsit中 则把它们加入到openlist 对于A1点来说并没有新的点要加入到openlist 4 检查原先openlist中点A2 A3 A7 A8在通过A1到达的G值是否更小 显然没有 所以不做任何变化 A A1 A2 A3 A4 A5 A6 A7 A8 下一步搜索的方格 1 从openlist中选择F值最小的 方格 节点A2 A2和A8取值一样 随机选择一个都可以 2 更新openlist和closelist openlist A3 A4 A5 A6 A7 A8 closelist A A1 A2 3 检查所有与它相邻的方格 忽略其中在closelist中或是不可走的方格 如果方格不在openlsit中 则把它们加入到openlist openlist A3 A4 A5 A6 A7 A8 A9 A10 4 新加入点A9 A10的父亲节点设为A2 并计算相应F G H值 5 检查原先在openlist中的点A1 A3通过A2到达的G值是否更小 显然没有 所以对这两个点不做任何变化 A A1 A2 A3 A4 A5 A6 A7 A8 A10 A9 最后搜索的方格 不断重复这个过程 直到把终点也加入到了openlist中 最终结束时如右图所示 这样我们就获得了绕过障碍物到达目的地的最短路 这样我们的智能导航系统就设计完毕啦 此时我们设计的导航系统已经可以投入生产使用啦 跟进一步 假如我的障碍物也会移动怎么办 A 算法能够解决有固定障碍物的路径规划问题 并且能很快地给出解 但是当障碍物是移动的时候 我们又应该如何对算法进行改从而给出解呢 一个典型问题 AGV小车线路规划 智能码头 AGV AGV中文名 自动导引小车是自动化码头水平运输系统中用于搬运集装箱的搬运设备 其主要职责 就是在规定的时间窗口范围内完成堆场和岸桥之间实现集装箱的传送 智能码头 AGV 智能码头 AGV 整个码头同一时刻运行的AGV数量很多时候不只一辆 可能会有很多辆 那我们如何能在满足每辆AGV时间窗口限制的前提完成作业呢 智能码头 AGV 在A 算法中我们求解的约束是障碍物固定的情况 而在AGV线路规划中 我们求解的约束是障碍物不固定的情况 障碍物是会移动 但在每个时刻处于哪个位子我们是可以确定的 智能码头 AGV 问题转化 假设我们现在只考虑设计一台AGV的运行轨迹 其他AGV的运行轨迹是已知的 已知运行轨迹的AGV可以理解为随时间变化移动的障碍物 问题简化 虽然在实际过程中 AGV小车在哪个位子转弯是任意的 但我们做出如下几方面简化假设 1 AGV
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 青岛市2027年高三第二次联考高考物理试卷(含答案解析)
- 2026-2027学年四川省绵阳市高三适应性调研考试高考物理试题(含答案解析)
- 小镇青年返乡创业:智慧养老平台下沉市场的机遇与挑战
- 十五五规划前瞻:智能家居安防的国家战略与安全底座
- 深度复盘智能网联汽车网络安全:2026年渗透率与融资趋势
- 十五五银发经济机遇:智能备餐进度屏适老化交互设计研究
- 双碳约束下智能按摩锤:绿色材料应用能否成为家电巨头第二曲线
- 2026年商务礼品市场调研报告:行业礼品定制化创新与市场前景
- 2026年环保产业小微门店绿色技术发展与政策解读报告
- 2026年人工智能行业应用报告及市场潜力分析
- 2027年天津农商银行校园招聘笔试备考试题及答案解析
- 康复医学科常见功能障碍康复指南(2026版)
- 2026-2030训练健身器材市场盈利模式及经营管理风险分析研究报告
- 2026年湖北省荆州市公安招聘辅警考试题库含答案
- 安徽建工集团管理制度
- 图形的位似课时1(课件)2026-2027学年北师大版九年级数学上册
- 2026年制鞋业智能化生产转型案例分析:技术赋能与产业升级
- YDT 5102-2024 通信线路工程技术规范
- 银行员工禁止性行为课件
- 第3章-民族医药基础知识
- 除痛病历管理制度
评论
0/150
提交评论