- 1、本文档共34页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
. .. .. .
最优路径规划算法设计
一、问题概述
兵力机动模型的功能是支持实施机动的实体按照指定路线 ,由作战空间的
一点向另外一点的位置移动 ,并带入实体在移动过程中发生变化的状态信息 。
兵力机动模型包括行军模型 、战斗转移模型 、机动能力评估模型 。 涉及的
关键算法包括最优路径规划 、行军长径计算 、行军时间计算 、行军所需油料计
算、行军方案评估与优选等 。
最优路径问题又称最短路问题 。是网络优化中的基本问题 ,如 TSP 问题等。
下面先举例说明该问题 。
最短路问题 (SPP-shortest path problem )
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地 。从甲地
到乙地的公路网纵横交错 ,因此有多种行车路线 ,这名司机应选择哪条线路呢 ?
假设货柜车的运行速度是恒定的 ,那么这一问题相当于需要找到一条从甲地到
乙地的最短路 。
旅行商问题 (TSP-traveling salesman problem )
一名推销员准备前往若干城市推销产品 。如何为他 (她)设计一条最短的
旅行路线 (从驻地出发 ,经过每个城市恰好一次 ,最后返回驻地 ?)
最短路问题是组合优化中的经典问题 ,它是通过数学方法寻找离散时间的
最优编排 、分组、次序、或筛选等 ,这类问题可用数学模型描述为
min f (x)
s.t. g(x) 0
.下载可编辑 .
. .. .. .
x D .
其中, f (x) 为目标函数 , g( x) 为约束函数 , x 为决策变量 , D 表示有限个点组
成的集合 。
一个组合最优化问题可用三个参数
( D, F , f ) 表示,其中 D 表示决策变量的
定义域 , F 表示可行解区域 F { x | x
D, g( x)
0} , F 中的任何一个元素称为
该问题的可行解 , f 表示目标函数 ,满足 f (x* )
min{ f (x) | x
F } 的可行解 x*
称为该问题的最优解 。 组合最优化的特点是可行解集合为有限点集
。由直观可
知,只要将 D 中有限个点逐一判别是否满足
g(x) 0 的约束并比较目标值的大
小,就可以得到该问题的最优解 。
以上述 TSP 问题为例 ,具体阐述组合优化问题 :
此模型研究对称 TSP 问题 ,一个商人欲到 n 个城市推销产品 ,两个城市 i 和 j
之间的距离 dij d ji ,用数学模型描述为
min
dij
xij
i
j
n
s.t.
xij
1
i
1,2, , n ,
j
1
s.t.
n
xij
1
j
1,2,
,n ,
i
1
i , j s
xij | s |
1,2
| s |
n
2, s {1,2,
, n},
xij
{ 0,1}, i, j
1,2,
, n, i
j
约束条件决策变量 x
1
表示商人行走的路线包含从城市
i 到 j 的路,而 x 0
ij
ij
表示商人没有选择走这条路
; i
j 的约束可以减少变量的个数
,使得模型中共
有 n (n 1) 个决策变量 。
每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时
.下载可编辑 .
. .. .. .
间为代价的 ,在 TSP 问题中,用 n 个城市的一个排列表示商人按这个排列序推
销并返回起点 。 若固定一个城市为起终点 ,则需要 (n 1)! 个枚举 。以计算机 1s
可以完成 24个城市所有路径枚举为单位 ,则 25 个城市的计算时间为 :以第 1个
城市为起点 ,第 2 个到达城市有可能是第 2 个、第 3 个、 、第 25 个城市 。 决
定前两个城市的顺序后 ,余下是 23 个城市的所有排列 ,枚举这 23 个城市的排列
需要 1s ,所以, 25 个城市的枚举需要 24 s 。 类似地归纳 ,城市数与计算时间
的关系如表 1 所示 。
表 1 枚举时城市数与计算时间的关系
城市数
24
25
26
27
28
29
30
31
计算时间
1 s
24 s
10 min
4.3h
4.9 天
136.5 天
10.8 年
325 年
通过表 1 可以看出 ,随着城市数的增加 ,计算时间增加非常之快 ,当城市
数增加到 30 时,计算时间约为 10.8 年,实际计算中已无法承受 。在城市数较多
时,枚举已不可取 ,我们可以采用一些别的方法缩短计算时间 。
TSP问题是 NP 难问题,其可能的路径数目与城市数目 n 是成指数型增长的 ,
所以一般很难求出其最优解 ,因而一般是找出其有效的近似求解算法 。遗传算
法可以用来解决一些较为复杂的系统问题 ,显然旅行商问题是需要编码运算的 ,
而遗传算法本身的特征正好为解决这一问题提供了很好的途径 。
NP
您可能关注的文档
- 曲边梯形的面积教学设计.docx
- 曲飞高校固定资产管理系统项目解决方案.docx
- 更换工作岗位申请书.docx
- 更换液压支架立柱的安全技术措施方案.docx
- 更换铝合金窗工程施工设计方案.docx
- 更换预付费式电能表工程承包协议样本.docx
- 曹田坑水库帷幕灌浆工程施工设计方案.docx
- 曹胡村沟头防护工程施工设计.docx
- 曾家小学各类安全预案.docx
- 最全河道清淤工程施工组织设计方案.docx
- 2023年09月浙江省平湖市医疗卫生单位公开招聘25名编外用工笔试历年难易错点考题荟萃附带答案详解.docx
- 2023年09月浙江省温岭市殡仪馆公开招考2名编制外工作人员笔试历年高频考点试题含答案带详解.docx
- 2023年09月广西职业技术学院招考聘用52人笔试历年高频考点试题含答案带详解.docx
- 2023年09月山东烟台海阳市人民医院招考聘用编外派遣制工作人员17人笔试历年高频考点试题含答案带详解.docx
- 2023年09月重庆市彭水自治县下半年公开遴选公务员笔试历年难易错点考题荟萃附带答案详解.docx
- 2023年黑龙江大庆市大同区医疗人才引进21人笔试历年高频考点试题含答案带详解.docx
- 2023人音版音乐六年级上册教学计划、教学设计及教学总结.docx
- 2013年云南省生物学业考.doc
- 2013年四川省自贡市生物学业考.doc
- 2012年山东省临沂市生物学业考.doc
1亿VIP精品文档
相关文档
最近下载
- dotNet及C#程序设计&第四次形考作业 循环控制语句(占形成性考核成绩15%).docx VIP
- 吉林中部500kV电网完善工程环境影响报告书全本.pdf
- 《Altium Designer 10 实用教程》配套教学课件.ppt
- 中学生青春期恋爱教育主题班会PPT课件.pptx
- JSP开发技术&形成性综合大作业(占形考成绩40%).docx VIP
- Se inclinassi a prender moglie 我要把妻子赏赐给你(G) - 未知.pdf
- 工作方案模板**镇整治违法建设宣传活动工作方案.docx VIP
- 清代学术概论--梁启超.pdf
- 网络信息安全应知应会知识库.docx
- 茶叶的品质与审评培训教程.pptx
文档评论(0)