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

最近更新

AutoCAD在德国多轴箱设计中的应用 2页

杭州合伙创业合同范本 6页

仿轮作蔬菜无土栽培系统研究 6页

沙漠治理砂石料调配合同 9页

2025年山东高职单招和综合评价招生报名时间20.. 4页

气象局卫生间装修合同标准 9页

木材供应商与家具厂购销合同范本 7页

2025年山东各地中考成绩官方公布时间 5页

2025年属龙缺金钱姓女孩取名 7页

2025年属龙的人在什么方位可以发财 11页

3S技术在太湖蓝藻空间分布研究中的应用 2页

教育培训机构装修修复合同 9页

高级人力资源管理师论文范文 4页

2×50MW热电联产机组的节能改造 2页

财务管理毕业论文题目50(参考) 5页

行政管理岗位绩效考核指标 5页

实验室改造项目合同 9页

浅析个人所得税问题及其改进建议-上海商学院毕.. 4页

本科人力资源管理专业论文 4页

日用化学论文选题 4页

新形势下企业选人问题应对策略研究 6页

教学实践报告硕士体育(3) 5页

我国企业集团公司内部审计人力资源管理探讨 5页

强化物流管理,提升企业核心竞争力 4页

第一讲为何要创业 60页

工商管理论文题目汇总(五范文) 4页

工作—家庭平衡型人力资源管理对工作绩效影响.. 4页

对推进应急管理系统干部能力提升的几点思考 5页

学生版 四川师范大学文件本科生毕业论文基本学.. 4页

如何打破传统管理制度的束缚创新企业管理模式.. 4页