基于满足性判定的布尔网络环求解算法

作     者：郭文生 杨国武 李晓瑜 高敏 GUO Wen-sheng;YANG Guo-wu;LI Xiao-yu;GAO Min

作者机构：电子科技大学计算机科学与工程学院成都610054 加州大学洛杉矶分校电子工程学院美国加州洛杉矶ca90034 

基　　金：国家自然科学基金(61272175) 

出 版 物：《电子科技大学学报》 (Journal of University of Electronic Science and Technology of China)

年 卷 期：2015年第44卷第6期

页      码：881-886页

摘      要：环是布尔网络状态转换过程中的稳定态,在模式检测、基因调控网络和可达性分析等领域都有重要的意义。计算布尔网络状态转换中的所有环是一个NP完全问题。该文基于全解布尔满足性判定(SAT)算法,设计了一种求解所有小于等于指定步长环的算法。算法基于布尔网络的状态转换函数和状态环属性生成合取范式形式(CNF)的问题集,通过融合冲突子句学习(CDCL)、非时序回退、阻塞子句和变量分类等技术,降低算法的计算复杂度。实验结果表明,该算法能够高效地计算指定步长的环。对于无法计算所有环的复杂网络,指定步长计算环的方式将更有应用价值。

主 题 词：布尔网络 环 满足性判定 阻塞子句 

学科分类：0808[工学-自动化类] 0809[工学-计算机类] 08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1001-0548.2015.06.015

馆 藏 号：203490055...