欢迎访问发表云网!为您提供杂志订阅、期刊投稿咨询服务!

基于混合搜索的含逻辑“与”“或”的RM优化算法

吕荫润; 陈力; 王翀; 吴敬征; 王永吉 计算机科学国家重点实验室(中国科学院软件研究所); 北京100190; 中国科学院软件研究所基础软件国家工程研究中心; 北京100190; 中国科学院软件研究所互联网软件技术实验室; 北京100190; 中国科学院大学; 北京100190
约束优化问题   实时系统   单调速率   线性规划   搜索算法  

摘要:相对于标准约束优化问题,广义约束优化问题(或称析取优化问题)的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率(RM)优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法(LPHS),将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.

简介:《软件学报》(CN:11-2560/TP)是一本有较高学术价值的大型月刊,自创刊以来,选题新奇而不失报道广度,服务大众而不失理论高度。颇受业界和广大读者的关注和好评。

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

软件学报

北大期刊 下单

关注 19人评论|2人关注
服务与支持