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

许可; 李未

首页> 中文期刊> 《软件学报》 >随机约束满足问题的回溯算法分析

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《软件学报》 |2000年第11期|1467-1471|共5页
作者
许可; 李未;
展开▼
作者单位

北京航空航天大学计算机科学与工程系;

北京;

100083;

北京航空航天大学计算机科学与工程系;

北京;

100083;

展开▼
原文格式 PDF
正文语种 chi
中图分类人工智能理论;
关键词
算法分析; 平均复杂性; 回溯算法; 约束满足;

相似文献

中文文献
外文文献
专利

1. 值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析 [J] . 徐伟 ,巩馥洲 . 计算机科学 . 2014,第004期
2. 随机k-SAT问题的回溯算法分析 [J] . 许可 ,李未 . 计算机学报 . 2000,第005期
3. 启发式回溯算法求解约束满足问题 [J] . 范如梦 ,赵春艳 ,李飞龙 . 计算机应用研究 . 2021,第005期
4. 基于禁忌搜索算法求解随机约束满足问题 [J] . 李飞龙 ,赵春艳 ,范如梦 . 计算机应用 . 2019,第012期
5. 基于动态状态树的回溯算法分析 [J] . 唐静 . 信息与电脑：理论版 . 2015,第013期
6. 扩展的随机约束满足问题生成模型研究 [C] . 张永刚 ,孙吉贵 ,高健 . 2005中国计算机大会 . 2005
7. 复杂网络上的非回溯随机游走与基于局部贝叶斯链路预测 [A] . 贾鸣明 . 2020

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

摘要

著录项

相似文献

相关主题

期刊订阅