二元约束满足问题求解的结点开销模型

• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 约束满足 求解开销 相变 求解启发式
• 年，卷（期）: 1998,（12）
• 页码范围: 43-47
• 页数: 5页
• 分类号: TP18
• 语种: 中文

摘要

提出了在二元约束满足问题中以搜索结点个数为衡量标准的求解开销模型,该模型被应用于随机二元约束满足问题的求解开销相变分析中,并且比较了模型所导出的理论开销和实际中的搜索结点个数、约束检查次数、求解时间3种衡量标准的开销之间的相似性.在模型的基础上,探讨了求解启发式减少求解开销的作用,给出了一个新的变量选择启发式.