动态规划问题的高效并行算法

在具有p(1≤p≤n)个处理机的CREW PRAM并型计算模型上,对一类动态规划问题给出了一处理机利用率为E(n)=0(1),并行加速比为S(n)=0(p)的并行算法(n表示问题的尺寸);计算了问题求解的最少费用,并同时给出了问题求解的方法。     

基于动态规划的序列比对的并行算法研究

针对序列比对算法进行了深入地研究,分析比较了两序列和多序列、局部和全局、渐进和迭代的序列比对算法.利用动态规划序列比对算法内在的并行性,提出了自适应的动态规划序列比对的并行策略.该策略在计算初期和计算末期采用较小的高度和宽度值使得大部分处理器参与计算,在计算中期采用较大的高度和宽度值降低处理器间的通信开销;运用上述自适应的动态规划序列比对的并行策略,提出了一种基于动态规划的序列比对的并行算法,将读入的比对序列负载均衡地分布至不同的计算结点.基于集群系统和MPI环境的实验数据及分析表明,该算法在给定进程数量的条件下,其执行时间随序列长度的增长而急剧上升;在给定序列长度的条件下,其执行时间随并行进程数量的增大而大幅减小;充分反映出该算法较好地发挥了序列比对问题的内在并行性,有效地降低了序列比对算法的时间复杂度.     

正项几何规划并行算法初探

讨论了一般的正项几何规划,针对正项几何规划的变形规划,利用分解定理提出了一种并行算法,这为大规模的正项几何规划问题寻求有效的并行算法提供了基础。     

一类二次规划问题的并行算法

计对一类特殊的二次规划问题给出了一个并行计算方法。该算法在每一步并行求解一个特殊的线性方程组以求得投影梯度。分析了每步迭代所需的计算工作量和速度增长倍数。     

计算加权Moore-Penrose逆A+M,N的一个改进的并行算法

利用PREPARTAFP和SARWATEDV[6] 的一些结果 ,给出一个计算加权Moore Penrose逆A MN 的改进的并行算法 ,改善了文献 [8]中提出的算法。在与PREPARTAFP和SARWATEDV文 [6 ]中相同的假设下证明了改进的并行算法的时间复杂性和处理机台数分别为 T =0 ((logn) 2 ) ,　 P =max m/n 2 nα/logn ,2r1 / 2 nα(logrlogn)时空积 (成本最优性 ) T× P小于T×P(T和P分别为 [8]中原有并行算法的时间复杂性和处理机台数 )。     

基于并行算法的大跨度斜拉桥动态响应分析

建立了大跨度斜拉桥的精细三维有限元模型,其单元数与节点数均超过百万,考虑大跨度斜拉桥的几何非线性影响,采用基于接触均衡的并行计算技术,解决了有限元模型规模庞大的问题.数值模拟了大跨度斜拉桥在恒栽作用下的成桥状态以及在轻轨车辆作用下的动态响应,并比较了不同分区方案对并行加速比的影响.数值模拟结果能够为大跨度斜拉桥设计提供参考依据.     

有限型多阶段决策问题的并行算法

讨论了在ＭＩＭＤ并行系统上，基于嘉量原理的摹矩阵连摹乘积求多阶段有向图最优路的并行算法，给出了选择顺推方式或逆推方式计算连摹乘的一个计算过程，提出了一个分派到各台处理机的任务基本均衡的ｐ－分划算法，并详细讨论了并行计算的实现，给出数值试验实例。     

基于分布式并行算法的动态交通流分配研究

基于分布式并行处理技术和面向对象的建模理论,为解决大规模城市道路交通流模拟问题,提出分布式并行模拟动态交通流分配思想,给出了CybeTraffic三维仿真系统中交通流模拟系统的数据结构描述、系统设计框架以及系统模拟结果.     

动态规划算法的时间效率改进

分析了影响动态规划算法时间复杂度的3个因素,分别从3个方面给出了改进动态规划算法时间复杂度的优化措施,从理论上分析了优化方法的有效性和正确性.与传统算法相比,优化后的算法时间复杂度有一定程度的提高,能够适用于数据规模更大的问题.     

双三次样条曲面插值的一种高效并行算法

该文在对双三次样条曲面插值问题的并行方案的优选、任务分配的优化以及Ｔｒａｎｓｐｕｔｅｒ并行结构上并行通讯的策略进行深入研究的基础上，给出了一种高效的ＭＩＭＤ并行算法，这种算法模式也适用于Ｂ样条和非均匀有理Ｂ样条等曲面插值问题，因而适用范围广，具有代表性。该算法的优点是各处理机负载平衡度高、通讯量小，其效率几乎接近１，大大高于现有解三对角方程组的并行直接法的效率（如分块ＬＤＬ＾Ｔ分解，ＤＤＭ方法的效     

资源分配问题的动态规划嘉量解法

本文给出用嘉量运算求解动态规划中资源分配问题的方法,它与传统的 B_e(?)man原理的递推公式算法相比,具有方法简明,计算量小,使用方便等优点。资源分配问题,就是把供应量有限的一种或若干种资源(资金,机器设备,原材料,劳动力等)分配给若干个使用部门,使得使用效果达到最优(目标函数值达到最大或最小)。处理这类问题动态规划中的 B_e(?)man 原理及其递推公式,被认为是一种最有效的方法。本文将运用嘉量原理。将此类问题化成所给半域上的嘉量运算.它具有简明,方便等优点。     

工序问题的动态规划算法

提出了一个求解工序问题的动态规划算法，该算法排序含ｎ个工件集合的期望时间为Ｏ（ｎ）．     

一类最优指派问题的动态规划算法

考虑一类较一般的最优指派问题 :欲把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) .本文给出了求解上述最优指派问题 (使总耗用时间最小 )的动态规划算法 .     

圆饼装填问题的并行算法

圆饼装填是一个将多个芯片设计组合到一个圆饼上，构造费用通过几个设计分担而减少的过程。本文在ＳＩＭＤ－ＣＲＥＷ并行计算模型下，通过修改Ｐｒｅｐａｒａｔａ并行排序算法及其用到的Ｖａｌｉａｎｔ并行归并算法，给出了分配２个设计到一个包的基本圆饼装填问题ＢＷＰＰ的并行算法，在Ｏ（ｎ＾１．５）台处理机上，算法的时间复杂性是Ｏ。     

利用动态规划求解资源分配问题

动态规划是解决多阶段决策过程最优化问题的一种数学方法,资源分配问题解决将一种或几种资源分配给若干用户或投资于几家企业,以获得最大的效益,它可以是多阶段决策过程,也可以是静态规划问题,都能构造动态规划模型求解。本文针对资源分配问题设计了动态规划求解算法,数值结果表明该算法是可行有效的。     

动态障碍物环境下移动机器人路径规划

以机器人基本避障碍策略与启发式动态规划法相结合的方法，研究了在障碍物轨迹已知的动态环境中机器人的路径规划问题，根据机器人与单个障碍物可能的碰撞情况，分别提出了几种避障碍,伙子目标和相应的速度。根据这些策略，在机器人当前视窗内，将形成一个策略树，采用启发式动态规划算法，依据时间和路径费用最小原则，找出一个最优策略集，即最优子目标集，这种规划方法大大缩小于机器人子目标搜索空间。     

WZ分解的一种新的并行算法

本文对n阶非奇异实稠密矩阵A的WZ分解提出了一种新的并行算法。用n~2台处理机,我们可以在3n-2步内求得矩阵A的WZ分解。该算法与文献[1]中的方法相结合,可得并行求解线性方程组的另一种有效算法。文中所提及的算法均适用于SIMD型并行计算机。     

电力网调度时间表问题的动态规划算法

为保持电力系统的平稳供电,安排每一电厂(站)所有机组的检修时间是极为重要.作为系统工程的应用,本文给出这一时间表问题的数学模型及动态规划算法.     

资源分配问题的动态规划求解方法

一种或几种资源分配给若干用户,或投资于几家企业,以获得最大的效益.文章适当引入阶段、状态变量、决策等将资源分配问题视为多阶段决策过程,应用动态规划方法并且在计算机上通过MATLAB编程方便地求解资源分配问题.     

基于动态规划的流量异常检测

本文是基于最优动态规划(DP)的时间规范化流量异常检测.将需要匹配的两组数据即样本数据和实际数据通过动态规划来计算其时间归一化距离,从而达到异常检测的效果,且本来采用的是动态规划匹配的对称形式.通过实验数据的分析,基于动态规划对称形式的流量异常检测准确率较高.