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

• 作者: 李晓瑜 杨国武 郭文生 高敏
• 来源期刊: 电子科技大学学报
• 学科: 工学
• 关键词: 布尔网络 环 满足性判定 阻塞子句
• 年，卷（期）: 2015,（6）
• 所属期刊栏目: 计算机工程与应用
• 页码范围: 881-886
• 页数: 6页
• 分类号: TP301.6
• 字数: 5438字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0548.2015.06.015

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭文生	电子科技大学计算机科学与工程学院	30	197	8.0	12.0
2	杨国武	电子科技大学计算机科学与工程学院	22	84	4.0	8.0
3	李晓瑜	电子科技大学计算机科学与工程学院	19	150	5.0	12.0
4	高敏	加州大学洛杉矶分校电子工程学院	1	0	0.0	0.0