求图符号控制数的完全算法研究

• 作者: 陈卫东
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 图 符号控制数 NP难度 回溯法 分枝定界法 A*算法
• 年，卷（期）: 2004,（24）
• 所属期刊栏目: 学术探讨
• 页码范围: 45-47,53
• 页数: 4页
• 分类号: TP301
• 字数: 5216字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2004.24.014

摘要

确定图的符号控制数是NP-难度的问题.针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A*算法.计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生成的结点数目还不到其状态空间树中结点总数目的千分之五.对这两个算法也进行了比较.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈卫东	华南师范大学计算机系	14	71	4.0	8.0