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

作者：陈卫东图符号控制数np难度回溯法分枝定界法

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

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