优化简单表缩减算法求解因子分解编码实例
作者:
作者单位:

作者简介:

王震(1998-),男,硕士,主要研究领域为约束规划.
李占山(1966-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为机器学习,约束推理.
李哲(1990-),男,博士,主要研究领域为约束规划,并行计算.

通讯作者:

李占山,E-mail:zslizsli@163.com

中图分类号:

TP18

基金项目:

国家自然科学基金(61802056);吉林省自然科学基金(20180101043JC);吉林省发展和改革委员会产业技术研究与开发项目(2019C053-9);中国科学院太空应用重点实验室开放基金(LSU-KFJJ-2019-08)


Optimizing Simple Tabular Reduction Algorithm for Factor-decomposition Encoding Instances
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61802056); Natural Science Foundation of Jilin Province (2018010 1043JC); Industrial Technology Research and Development Project of Jilin Development and Reform Commission (2019C053-9); Open Research Fund of Key Laboratory of Space Utilization, Chinese Academy of Sciences (LSU-KFJJ-2019-08)

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

    表约束在约束程序(constraint programming,简称CP)中被广泛研究.目前,求解表约束问题效率最高的算法是CT (compact-table)和STRbit (simple tabular reduction bit).它们在搜索过程中维持广义弧相容(generalized arc consistency,简称GAC).完全成对相容(full pairwise consistency,简称fPWC)是一种强于GAC的相容性关系,目前,实现fPWC效率最高的算法是PW-CT,但是它无法直接在通用的求解器上实现.因子分解编码(factor-decomposition encoding,简称FDE)是实现fPWC的一种编码方式,通常和简单表缩减(STR)算法一起来使用.当前效率最高的STR算法使用了bitset的数据结构,用这些算法来求解FDE实例可能会造成内存溢出.提出了STRFDE算法——一种使用bitset结构来求解FDE实例的方法.它结合了CT和STRbit的优势,在保证求解效率的同时,使占用的内存尽可能小.实验结果表明,在许多存在非平凡相交的实例上,该算法是有竞争力的.

    Abstract:

    Table constraints are widely studied in constraint programming (CP). At present, the most efficient algorithms for solving table constraint problems are compact-table (CT) and simple tabular reduction bit (STRbit), which maintain generalized arc consistency (GAC) during the search process. Full pairwise consistency (fPWC) is a consistency that is stronger than GAC. The most efficient algorithm for maintaining fPWC is PW-CT which is difficult to implement in general solver. Factor-decomposition encoding (FDE) is an encoding method that implements fPWC and is usually used together with STR. The current STR algorithms that use bitset may cause memory overflow issues to solve FDE instances. This study proposes STRFDE, a new algorithm using bitset for solving FDE instances. It combines the advantages of CT and STRbit that makes the memory as little as possible while ensuring the efficiency of solving. Experimental results show that the proposed algorithm is competitive over a variety of instances with non-trivial intersections.

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

王震,李哲,李占山.优化简单表缩减算法求解因子分解编码实例.软件学报,2021,32(11):3530-3540

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

京公网安备 11040202500063号