共查询到20条相似文献,搜索用时 126 毫秒
1.
最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。 相似文献
2.
将动态规划算法用于两个生物序列的最短公共超序列的计算。计算过程分为两个算法,第一个算法计算两个序列的所有前缀的最短公共超序列的长度,并存放在一个矩阵中,第二个算法利用前面所得的矩阵,找到两个序列的最短公共超序列。 相似文献
3.
针对非线性两级整数规划的求解问题,给出了一种最优化求解方法,即将其上级规划转化为非线性连续型规划问题后,采用模拟退火算法求出最优解;其对应的下级规划问题采用模拟退火整数算法求解,通过算例的实际运算,取得了令人满意的结果,证明该最优化求解方法是可行且有效的。 相似文献
4.
岑文杰 《大众科学.科学研究与实践》2007,(2)
近年来,随着交通系统的建设和我国物流事业迅速发展。一个信息化、自动化、一体化的物理信息系统已是势在必行。它带给企业的不单单是便捷,还有巨大的经济利益。为了解决运输货物中最佳路径及方式的选择。 相似文献
5.
根据无人车动态实时避障的需求,提出一种基于人工势场法的局部避障路径规划算法,通过改进势场环境及势场力来解决传统势场法局部极小值和目标不可达的问题. 考虑车辆碰撞安全性,对侧向动态障碍物和同向动态障碍物工况进行分析,采用动态窗口法进行实时动态避障规划. 同时为保证规划路径的平滑性和可跟踪性,采用贝塞尔曲线对轨迹进行平滑处理. 最后,在CarSim和Matlab/Simulink 联合仿真平台下,对所提出的控制算法进行验证. 仿真结果表明了规划算法的避障有效性、安全性以及可跟踪性. 相似文献
6.
工序问题的动态规划算法 总被引:1,自引:0,他引:1
徐绪松 《武汉大学学报(自然科学版)》1994,(5):20-25
提出了一个求解工序问题的动态规划算法,该算法排序含n个工件集合的期望时间为O(n). 相似文献
7.
动态规划原理在高速公路网级养护决策中的应用 总被引:1,自引:0,他引:1
针对高速公路养护管理特点,利用动态规划原理和路况状态转移概率计算模型,建立了高速公路网级决策动态优化模型,成为高速公路管理系统的核心。并对用于网级决策模型的动态规划方法在理论上作了较为详细的研究,细化了决策优化步骤。 相似文献
8.
针对移动机器人全局动态路径规划效率较低的问题,提出一种基于安全A*算法与双速度模型动态窗口法的全局动态路径规划融合算法.首先,通过安全A*算法得到全局最优路径节点,将其作为临时目标节点,为动态规划提供全局信息,避免出现局部最优.然后,采用时间序列Bottom-Up算法减少路径节点数,从而减少迭代次数、计算代价和储存代价,提高算法效率.最后,采用双速度模型对动态窗口法进行改进,通过避障重规划机制,解决全局动态路径规划时移动机器人绕远甚至绕圈的问题,并通过MATLAB平台进行仿真实验.仿真结果表明:文中算法的规划效率可提高46.18%,保证了路径的安全性和移动机器人速度的平稳性,文中算法的路径质量和规划效率更佳. 相似文献
9.
考虑一类较一般的最优指派问题 :欲把m项工作指派n个人去完成 (m≥n) ,要求每项工作只能由一个人来做 ,第i个人可以同时做bi 项工作 ,其中bi 是待求未知数 ,满足di ≤bi≤ei(ei,di 为第i个人所需工作数的上下限 )及∑ni=1bi =m为已知常数 (i=1,2 ,… ,n) ,第i个人做第j项工作所用的时间为cij≥ 0 (i =1,2 ,… ,n ;j=1,2 ,… ,m) .本文给出了求解上述最优指派问题 (使总耗用时间最小 )的动态规划算法 . 相似文献
10.
限制搜索区域的距离最短路径规划算法 总被引:13,自引:0,他引:13
提出一种时间复杂度为O(n)的限制搜索区域距离最短路径规划算法(n为路网节点数).算法设计的基础是,经典Dijkstra算法搜索时的无方向性及实际城市道路网络特有的空间分布特性.算法实现采用邻接表数据结构和限制搜索区域的搜索机制,即利用实际城市道路网络的空间分布特性,合理限制算法的搜索区域.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的应用实例,实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在3 s以内. 相似文献
11.
动态未知环境中的优化路径规划算法 总被引:3,自引:1,他引:3
提出一种在未知动态环境中进行启发式优化搜索的实时路径规划算法.该算法采用并行搜索策略,在机器人当前位置点到终点的连线方向上作角度增减两个方向的并行搜索.仿真试验证明该算法是实时而有效的. 相似文献
12.
提出了一种适用于动态环境下移动机器人路径规划的新方法.用栅格法对环境进行建模,从目标栅格点出发,各栅格中心点到目标栅格中心点的距离信息以每个时间步一个栅格的速度不断向外传播.经过足够多时间步的传播后,通过逐步寻找信息的传播来源,即可获得机器人的最短路径.仿真结果表明,该方法非常简单且高效,能快速规划出动态环境下移动机器人的最优路径. 相似文献
13.
为了解决清洁机器人完全覆盖路径规划中最大覆盖率和最小重复率的要求,在清洁机器人犁田式全局路径规划算法的基础上,提出了BP神经网络方法作为清洁机器人的局部路径规划.运用基于深度优先遍历的改进型BP神经网络算法.解决清洁机器人的清扫死区问题.仿真的结果表明所提出的BP神经网络方法和改进型BP神经网络算法能够解决清洁机器人在家庭内的完全覆盖路径规划问题. 相似文献
14.
一种构建平面离散点集凸包的算法研究 总被引:7,自引:0,他引:7
俞梅 《上海应用技术学院学报:自然科学版》2003,3(2):118-120
本文提出一种矢量运算方法确定平面离散点集凸包,其原理是在构建凸包前,通过矢量计算判别出位于凸包多边形内部的点,预先将其删去,保留凸包多边形外部边缘的点,从而减少了构建凸包的离散点数目,提高运算速度。新算法达到O(n1ogn)时间复杂度下限,简单且易于实现。 相似文献
15.
Mobile anchors are widely used for localization in WSNs.However,special properties over 3D terrains limit the implementation of them.In this paper,a novel 3D localization algorithm is proposed,called 3DT-PP,which utilizes path planning of mobile anchors over complex 3D terrains,and simulations based upon the model of mountain surface network are conducted.The simulation results show that the algorithm decreases the position error by about 91%,8.7% and lowers calculation overhead by about 75%,1.3%,than the typical state-of-the-art localization algorithm (i.e.,‘ MDS-MAP’,‘ Landscape-3D’).Thus,our algorithm is more potential in practical WSNs which are the characteristic of limited energy and 3D deployment. 相似文献
16.
利用网络的特性,采用遍历搜索方法对最短路径问题做出一个敏感性分析,适合于解决在一些实际系统模型中利用网络图进行规划时,需要对一些环节进行调整,却又能不破坏原最优计划的问题. 相似文献
17.
基于蚁群算法的移动机器人路径规划研究与应用 总被引:4,自引:0,他引:4
文章对传统蚁群算法收敛较慢的问题进行了改进,参考人工势场法的思想,构建并加入了权重可调的引力概率函数作为启发因子,使新的算法在较快的收敛速度下仍能得到全局较优解;在新算法的基础上构建了移动机器人动态路径规划模型,通过计算机仿真和智能试验车的实际行走表明,即使在障碍物非常复杂的场地环境,用该算法也能迅速规划出较优的全局路径。 相似文献
18.
本文从爆破网络等时线定义及等时线在爆破工程中的应用出发,提出了一种新的基于凸多边形的爆破等时线凸多边形三角插入算法,算法首先分层算法找出所有的由炮孔组成凸多边形,然后将内层的凸多边形运用三角形插入算法逐次插入到外层凸多边形,从而找出炮孔的等时线,最后采用贪心算法修正少数等时线交叉点。结果表明,此算法生成速度快,解决了爆破网络等时线出现交叉点的情况,具有实际的工程应用价值。 相似文献
19.
自由飘浮空间机器人笛卡尔避奇异运动规划 总被引:1,自引:0,他引:1
为了解决自由飘浮空间机器人笛卡尔运动规划过程中由动力学奇异而导致的关节速度无限大或无法计算的问题,提出了一种基于奇异值分解的高精度避奇异运动规划算法.在传统阻尼最小方差的基础上,利用奇异值分解将阻尼系数从固定量转化为随广义雅可比矩阵动态自适应变化的变量,算法保证了空间机器人通过奇异点时各关节的角速度变化曲线连续且平稳.算例验证了算法的有效性,结果表明该算法在非奇异位置不会引入跟踪误差,相比传统阻尼最小二乘法累计跟踪误差大约降低15%. 相似文献
20.
动态环境中 ,移动机器人的动态路径规划是一个较难解决的课题 .提出了一种基于遗传算法的移动机器人的路径规划方法 .该方法采用实数编码和有明确物理意义的适应度函数 ,可以加快实时的运算速度和提高运算精度 .同时 ,该方法充分挖掘了可应用遗传算法解决移动机器人动态路径规划的潜力 .计算机仿真表明 ,仿真该控制方法具有良好的动态路径规划能力 相似文献