一种有效的分层加权库编译方法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61133011, 61170092, 60973088, 60873149); 吉林大学研究生创新基金(20111060)


Efficient Compilation Approach on Stratified Weighted Bases
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    提议对加权库进行分层,一方面符合人类的思维习惯,另一方面能够提高推理效率.首先说明现有的针对非分层加权库的编译方法也适用于编译分层加权库,但是,由于存在较多冗余信息而效率不高.提出一种新的编译方法,能够在编译过程中去除冗余信息,并提出两种优化技术提高时间效率.该方法与现有方法相同,当软约束权值改变时无需重新编译.选择 ROBDD 为目标语言,使用随机问题对该方法进行测试.结果表明:对于非分层加权库,该方法的空间效率高于已存在方法;对于分层加权库,该方法的时间和空间效率均高于已存在方法,且当层数越多时,该方法的效率越高.

    Abstract:

    To be in accordance with the thinking habits of human and improve the efficiency of reasoning, thisstudy argues to stratify weighted bases. The study shows that the existing compilation approach to non-stratifiedweighted bases can also be applied to COMPILE stratified weighted bases; however, its time and space costs arerelatively high because of redundant information in the compilation results. The paper proposes a novel compilationapproach, which can remove the redundant information in the process of compilation, and presents two optimizationtechniques to further improve the time efficiency. As with the existing approach, re-compiling a stratified weightedbase is not required whenever the weights associated with soft constraints change with time. The approach is testedby compiling random instances into ROBDD-normal bases, and the preliminary experimental results show that thetime and space costs of this approach are lower than the existing approach for most instances.

    参考文献
    相似文献
    引证文献
引用本文

赖永,刘大有.一种有效的分层加权库编译方法.软件学报,2012,23(10):2550-2563

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-08-30
  • 最后修改日期:2012-01-17
  • 录用日期:
  • 在线发布日期: 2012-09-30
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号