主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
许可,李未.随机约束满足问题的回溯算法分析.软件学报,2000,11(11):1467-1471
随机约束满足问题的回溯算法分析
An Average Time Analysis of Backtracking on Random Constraint Satisfa ction Problems
投稿时间:1999-03-16  修订日期:1999-09-13
DOI:
中文关键词:  算法分析  平均复杂性  回溯算法  约束满足
英文关键词:analysis of algorithm  average complexi ty  backtracking algorithm  constraint satisfaction
基金项目:国家重点基础研究发展规划资助项目(G1999032701);教育部博 士点基金资助项目(1999000613)
作者单位
许可 北京航空航天大学计算机科学与工程系北京,100083 
李未 北京航空航天大学计算机科学与工程系北京,100083 
摘要点击次数: 2865
全文下载次数: 3066
中文摘要:
      提出一种新的随机CSP(constraint sa tisfaction problem)模型,并且通过研究搜索树的平均节点数,分析了回溯算法求解该模型 的平均复杂性.结果表明,这种模型能够生成难解的CSP实例,找到所有的解或证明无解所需的 平均节点数即随变量数的增加而指数增长.因此,该模型可以用来研究难解实例的性质和CSP 算法的性能等问题,从而有助于设计出更为高效的算法.
英文摘要:
      A new random CSP (constraint satisfaction pro blem) model is proposed in this paper. By analyzing the expected number of nodes in a search tree, the average running time used by the backtracking algorithm o n random constraint satisfaction problems is studied. The results show that the model can generate hard CSP instances, and the expected number of nodes required for finding all solutions or proving that no solution exists becomes exponentia lly large as the number of variables grows. Therefore, the model can be used to analyze the nature of hard instances and evaluate the performance of CSP algorit hms, and hence it helps the researchers to design more efficient algorithms.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利