论文部分内容阅读
通过研究搜索树的平均节点数，分析了回虎法求解随机ｋ－ＳＡＴ问题的平均复杂性，结果表明：找到实例所有的解或证明其无解所需的平均节九随变量数ｎ的增加而指数增长；随着ｒ的增大，求解将变得越来越容易，而且当ｒ趋近于无穷大时，以ｎ为指数。平均节点数的底数将无限地趋势于１。
随机k—SAT问题的回溯算法分析
【摘 要】
：
通过研究搜索树的平均节点数，分析了回虎法求解随机ｋ－ＳＡＴ问题的平均复杂性，结果表明：找到实例所有的解或证明其无解所需的平均节九随变量数ｎ的增加而指数增长；随着ｒ的增大，求解将变得越来
【出 处】
：
计算机学报
【发表日期】
：
2000年5期
【基金项目】
：
国家“九七三”项目!( G19990 3 2 70 1),教育部博士点基金
其他文献
Ｉｎｔｅｒｎｅｔ是一个大型１自治的分布式系统，其结点正日益成为数据库系统，Ｉｎｔｅｒｎｅｔ形成的新环境要求重新考虑现行分布式数据库技术的许多概念，文中对Ｉｎｅｒｎｅｔ上－－类重要的查询－－联合查询作了代娄分析，指出联合查询的