首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
从3个方面改进了不确定规划(non—deterministic planning,简称NOP)中的观测约简:一是如何找最小观测集合(minimal observation set,简称MOS),二是如何在观测代价不均等时找最优观测集合(iptimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cover,简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2^mm^2)且不低于Ω(2^m-1)的算法,其中m是观测的个数.通过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.  相似文献   

2.
用擂台赛法则构造多目标Pareto最优解集的方法   总被引:14,自引:0,他引:14  
郑金华  蒋浩  邝达  史忠植 《软件学报》2007,18(6):1287-1297
针对多目标进化的特点,提出了用擂台赛法则(arena's principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0m/N<1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN2)和O(Nlog(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.  相似文献   

3.
RNA二级结构预测中动态规划的优化和有效并行   总被引:6,自引:0,他引:6  
谭光明  冯圣中  孙凝晖 《软件学报》2006,17(7):1501-1509
基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.  相似文献   

4.
Pawlak教授提出的粗糙集理论是解决集合边界不确定的重要手段,他构建了边界不确定集合的两条精确边界,但没有给出用已有知识基来精确或近似地构建目标概念(集合)X的方法.在前期的研究中提出了寻找目标概念X的近似集方法,但并没有给出最优的近似集.首先,回顾了集合间的相似度概念和粗糙集的近似集Rλ(X)的构建方法,提出并证明了Rλ(X)所满足的运算性质.其次,找到了Rλ(X)比上近似集R(X)和下近似集R(X)更近似于目标概念Xλ成立的区间.最后,提出了R0.5(X)作为目标概念的最优近似集所满足的条件.  相似文献   

5.
背包问题的最优并行算法   总被引:10,自引:2,他引:10  
利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1-ε个并行处理机单元,0≤ε≤1,O(2n/2)个存储单元,在O(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.  相似文献   

6.
并集问题的一个随机算法   总被引:1,自引:0,他引:1  
张立宇  朱洪  张丕兴 《软件学报》2000,11(12):1587-1593
随机算法由于其简洁和高效的特点正在计算中占据越来越重要的位置.但有时随机算法的优良性能并不要求用完全独立的随机变量作为它的输入.仅用成对独立的随机变量作为输入,得到了一个关于估计并集的基的问题的随机算法.这一方法可以减少随机算法中使用的随机位.对于固定的精确度ε和确信度δ,此算法需要O(t1/2)的随机位,比标准的随机算法所使用的随机位数O(tlogtM)要少得多.而算法的执行时间并没有显著地增加O(t2logM).  相似文献   

7.
加权3-Set Packing 的改进算法   总被引:1,自引:0,他引:1  
Packing 问题构成了一类重要的NP 难问题.对于加权3-Set Packing 问题,把问题转化成加权3-Set Packing Augmentation 问题进行求解,即主要讨论如何从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing. 通过对问题结构的分析,结合Color-Coding 技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing 结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k).  相似文献   

8.
李肯立  赵欢  李仁发  李庆华 《软件学报》2007,18(6):1319-1327
将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.  相似文献   

9.
模糊聚类计算的最佳算法   总被引:14,自引:0,他引:14  
马军  邵陆 《软件学报》2001,12(4):578-581
给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n2).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n3logn)计算时间相比,新算法至少降低了O(n相似文献   

10.
确定任意多边形凸凹顶点的算法   总被引:21,自引:0,他引:21  
周培德 《软件学报》1995,6(5):276-279
本文提出一种确定任意多边形凸凹顶点的算法.该算法的时间复杂性为O(n2logn)次乘法和O(n2)次比较.  相似文献   

11.
强循环规划的观察信息约简   总被引:1,自引:0,他引:1       下载免费PDF全文
在现实的规划领域中,观察信息的获得需要花费一定的代价,然而对于一个规划解来说,一些观察信息在执行规划解的过程中是不会被用到的,所以如何把这些不必要的观察信息去除从而节省实际过程中的成本是非常有必要的。针对强循环规划的观察信息展开研究,提出了一个对强循环规划观察信息进行约简的算法,该算法能够找出在完全可观察条件下强循环规划的最小观察变量集合,通过使用最小观察变量集合,可以进一步提高执行强循环规划解的效率。  相似文献   

12.
在不确定规划中,可通过观察周围的信息来区分多个状态,但周围的观察信息较多,因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的,存在一定的局限性。在对观察信息约简研究中,为提高搜索效率,设计一种高效的不确定规划中观察信息约筒算法。该算法将规划问题转化为求解O—l矩阵的覆盖问题,使用数据结构十字链表来表示O-1矩阵,通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明,该算法不仅能够找最小观察变量集,而且运行速度超过同类算法。  相似文献   

13.
部分可观察强规划中约减观察变量的研究   总被引:5,自引:1,他引:4  
给出了一种约减观察变量方法——假设所有的状态变量都不是观察变量,在此基础上逐步增加必要的观察变量,从而最终得到一个必要的观察变量集合.在添加必要的观察变量过程中,该方法不要求得到所有变量的相关信息,从而具有更好的通用性.根据是否存在单个观察变量能够区分域中任意两个状态的问题,分别给出了两种约减观察变量方法:当存在一个观察变量可以区分规划域中任意两个状态时,算法可以得到一个最小的观察变量集合;当不存在这样一个观察变量时,算法可以得到一个尽可能小的观察变量集合,但不能保证该集合最小.  相似文献   

14.
机器人路径规划方法综述   总被引:31,自引:0,他引:31  
张颖  吴成东  原宝龙 《控制工程》2003,10(Z1):152-155
路径规划技术是机器人控制技术研究中的一个重要问题,目前为止,其研究方法主要有两大类传统方法和智能方法.综述了有关机器人路径规划技术的研究方法,介绍了自由空间法等传统方法,同时讨论了基于遗传算法、模糊控制和神经网络等智能方法的路径规划技术,并展望了机器人路径规划技术的未来与发展趋势.  相似文献   

15.
This paper shows how action theories, expressed in an extended version of the language     , can be naturally encoded using Prioritized Default Theory . We also show how prioritized default theory can be extended to express preferences between rules . This extension provides a natural framework to introduce different types of preferences in action theories— preferences between actions and preferences between final states . In particular, we demonstrate how these preferences can be expressed within extended prioritized default theory. We also discuss how this framework can be implemented in terms of answer set programming.  相似文献   

16.
The study aims to extend the Uncapacitated Fuzzy Single Item Lot Sizing Problem (known as F-USILSP) model and extend it for inventory planning. The F-USILSP model is a good choice when there is no statistical data collection, but where there is verbal or qualitative information from experts with experience. Previously, the mixed integer linear programming (MILP) relied on the crisp assumption which hinders the use of the F-USILSP. In this paper, a Possibility Approach is adapted to convert the F-USILSP to a mathematically solvable equivalent crisp USILSP (EC-USILSP). The EC-USILSP model is tested with a case. The organization under study is a petrochemical company power plant with trapezoidal fuzzy demand and triangular fuzzy unit price. The overall results show that the EC-USILSP is more practical and exhibits more flexibility when there is a need to add more realistic situations.  相似文献   

17.
传统的数学模型方法是解决复杂卫星任务规划问题的一种途径,但其抽象性给建模人员带来很大难度。PDDL(Planning Domain Definition Language)可以针对卫星任务规划问题建立清晰有效的模型,并能把模型的知识转化成计算机易于接受的形式。用PDDL描述对地观测卫星的任务规划问题,分析了卫星执行任务时涉及的约束、相关活动和所需的资源,建立任务规划模型的域文件(domain file)和问题(problem file)文件,并针对所建模型提出求解模型的算法流程,最后通过一个算例验证模型和算法是有效地。  相似文献   

18.
A sensor-based fuzzy algorithm is proposed to navigate a mobile robot in a 2-dimensional unknown environment filled with stationary polygonal obstacles. When the robot is at the starting point, vertices of the obstacles that are visible from the robot are scanned by the sensors and the one with the highest priority is chosen. Here, priority is an output fuzzy variable whose value is determined by fuzzy rules. The robot is then navigated from the starting point to the chosen vertex along the line segment connecting these two points. Taking the chosen vertex as the new starting point, the next navigation decision is made. The navigation process will be repeated until the goal point is reached.In implementation of fuzzy rules, the ranges of fuzzy variables are parameters to be determined. In order to evaluate the effect of different range parameters on the navigation algorithm, the total traveling distance of the robot is defined as the performance index first. Then a learning mechanism, which is similar to the simulated annealing method in the neural network theory, is presented to find the optimal range parameters which minimize the performance index. Several simulation examples are included for illustration.  相似文献   

19.
传统方法在进行机器人在线步态规划时,由于受到大量外部复杂因素的干扰,造成步态规划偏差较大,无法准确跟踪期望步态;为此,提出一种基于变量集控制(variable set control,VSC)的仿人机器人在线步态规划方法;将步态规划问题转化为反应机器人步态状态的变量集的规划问题,根据对相关变量的规划和计算,能够获取机器人关节空间运动的状态序列;根据变量集中的零力矩点、机器人的重心、髋部中心和步态规划之间的关系,能够获取机器人在线步态规划中关键变量集的规划和计算结果;仿真实验表明,利用该方法能够克服传统方法的缺陷,实现了对机器人在线步态规划的准确控制。  相似文献   

20.
Level Set方法求解机器人路径规划的探讨   总被引:1,自引:0,他引:1       下载免费PDF全文
移动机器人路径规划是机器人学的一个最基本也是最复杂的问题,路径规划的主要方法有势能方法、单元分解方法、神经网络(NN)等。水平集(level set)方法已经广泛应用于图像处理和计算机图形学领域,因为其具有能够处理拓扑改变、数值稳定性好和独立于参数化的优势。为了探讨Level set方法在求解机器人路径规划中的应用,在介绍水平集法的基本思想和相关技术,以及路径规划的求解方法等的基础上,引入路径规划问题的隐式主动轮廊模型,即水平集模型,并采用快速推进方法(FMM)求解此模型方程,进而给出了路径规划模型的计算结果及其可视化界面,并且与经典势能法的计算结果进行了比较。理论和计算结果证明,Level set方法求解机器人路径规划是可行和有效的,从而为机器人路径规划研究提供了新的思路和方法。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号