1 / 30
文档名称:

最优路径规划算法设计报告.doc

格式:doc   大小:636KB   页数:30页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

最优路径规划算法设计报告.doc

上传人:2786321826 2022/2/12 文件大小:636 KB

下载得到文件列表

最优路径规划算法设计报告.doc

相关文档

文档介绍

文档介绍:-
. z.
最优路径规划算法设计
问题概述
兵力机动模型的功能是支持实施机动的实体按照指定路线,由作战空间的一点向另外一点的位置移动,并带入实体在移动过程中发生变化的状态信息。
矩阵,即,,也就是说,如果两节点之间有一条弧,那么邻接矩阵中对应元素为1,否那么为0.
图〔a〕和图〔b〕的邻接表矩阵即为
在计算机中用二维数组表示,两节点之间有弧相应的元素为1.
必须指出的是:目前为止,一切最短路算法都只对不含负有向圈的网络有效。实际上,对于含负有向圈的网络,其最短路问题是NP-hard。因此,除非特别说明,一律假定网络不包含负有向圈。此外在实际问题中也会遇到无向网络上的最短路问题,这时原问题一般可以转化为有向网络中上的最短路问题。如果所有弧上的权全为非负数,只需将无向图的一条边代之以两条对称的有向弧即可。如果弧上的权
-
. z.
有负有正,一般来说问题要复杂得多,要具体问题具体分析。本文中所要解决的问题都取权值为正,无向图皆采取两条对称的有向弧问题。
,其中,与关联,称是图的一条道路,为路长,顶点和分别称为的起点和终点,而称为他的部顶点。
假设道路的边互不一样,那么称为迹。假设道路的顶点互不一样,那么称为轨。
称一条道路是闭的,如果它有正的长且起点和终点一样。起点和终点重合的轨叫做圈(cycle)。
假设图G 的两个顶点u, v间存在道路,那么称u和v连通(connected)。u, v间的最短轨的长叫做u, v间的距离。记作d(u,v)。假设图G 的任二顶点均连通,那么称G 是连通图。
显然有:
(i)图P 是一条轨的充要条件是P 是连通的,且有两个一度的顶点,其余顶点的度为2;
(ii)图C 是一个圈的充要条件是C 是各顶点的度均为2 的连通图
应用
以行军途中各目标为图G 的顶点,两目标之间的连线为图G 相应两顶点间的边,得图G 。对G 的每一边e,赋以一个实数w(e)—两目标之间的距离长度,称为e的权,得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路,它的权叫做间的距离,亦记作。
-
. z.
算法设计
Dijkstra算法
定义预览:
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,注意该算法要求图中不存在负权边。
算法描述
算法思想:
设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合〔用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将参加到集合S中,直到全部顶点都参加到S中,算法就完毕了〕,第二组为其余未确定最短路径的顶点集合〔用U表示〕,按最短路径长度的递增次序依次把第二组的顶点参加S中。在参加的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2〕算法步骤:
-
. z.
,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},假设v与U中顶点u有边,那么<u,v>正常有权值,假设u不是v的出边邻接点,那么<u,v>权值为∞。
,把k参加S中〔该选定的距离就是v到k的最短路径长度〕。
,修改U中各顶点的距离;假设从源点v到顶点u的距离〔经过顶点k〕比原来距离〔不经过顶点k〕短,那么修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

3〕算法实例
图1是5个节点的赋权无向图
图1 各节点之间的赋权无向图
1
10 100
2 30
5
5

最近更新

CE-158在PC-1500机的传输应用 2页

2025年工厂品保工作心得 22页

BW-1变稳飞机飞行品质试验研究 2页

BP神经网络优化槐花中芦丁的提取工艺 2页

2025年工作车位出租合同模板怎么写 12页

AYX-3型调压积时式采样器通过技术鉴定 2页

2025年工作总结 2025初中班主任年终工作总结范.. 24页

杭州官方版房屋买卖合同样本 5页

AP-脱脂剂用于猪皮、绵羊大油板皮脱脂的探索 2页

AGFA CR系统影像伪影及解决对策 2页

高性能混凝土运输及配送服务协议书(2025年度.. 9页

2025年岗位工作调动申请书(精选篇) 14页

801胶在低压电器线圈上的应用 2页

2025年山西考研网上报名什么时候截止 4页

东陂长汀品唇鳅的个体生物学初步研究 2页

660 MW机组FCB试验转速飞升异常分析及处理 2页

600MW锅炉节油燃烧器改造措施探讨 2页

水产加工废渣清运合同 9页

橡胶制品液碱运送协议 9页

2025年山东服装职业学院2025单招和综合评价招.. 2页

2025年山东开学交通安全第一课心得及启迪(最.. 16页

500A1200V可控硅元件管芯部分试制工艺 2页

2025年山东中小学生2025寒假放假时间 7页

2025年山东2025年下半年中小学教资面试报名时.. 6页

服装店转让正式合同书范本 6页

2024年《国有企业管理人员处分条例》测试题【.. 15页

浙教版小学四年级2022-2023学年劳动与技术教学.. 37页

2025年玉米烘干厂可行性报告模板 31页

驻村干部年度组织生活会个人对照检查材料 5页

医学伦理知情同意书 3页