随机约束满足问题的回溯算法分析

• 作者: 李未 许可
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 算法分析 平均复杂性 回溯算法 约束满足
• 年，卷（期）: 2000,（11）
• 页码范围: 1467-1471
• 页数: 5页
• 分类号: TP18
• 字数: 3842字
• 语种: 中文

摘要

提出一种新的随机CSP(constraint sa tisfaction problem)模型,并且通过研究搜索树的平均节点数,分析了回溯算法求解该模型的平均复杂性.结果表明,这种模型能够生成难解的CSP实例,找到所有的解或证明无解所需的平均节点数即随变量数的增加而指数增长.因此,该模型可以用来研究难解实例的性质和CSP 算法的性能等问题,从而有助于设计出更为高效的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许可	北京航空航天大学计算机科学与工程系	20	186	6.0	13.0
2	李未	北京航空航天大学计算机科学与工程系	23	113	7.0	10.0