基于分割的超树分解方法

J4 ›› 2013, Vol. 51 ›› Issue (02): 257-266.

基于分割的超树分解方法

王涛¹, 王瑞芹^2,3, 李占山^2,3, |陈超^2,3

1. 长春工业大学计算机科学与工程学院, 长春 130012；
2. 吉林大学符号计算与知识工程教育部重点实验室, 长春 130012;
3. 吉林大学计算机科学与技术学院, 长春 130012

收稿日期:2012-05-02 出版日期:2013-03-26 发布日期:2013-03-27
通讯作者: 李占山 E-mail:zslizsli@163.com

SeparationBased Hypertree Decomposition

WANG Tao¹, WANG Ruiqin^2,3, LI Zhanshan^2,3, CHEN Chao^2,3

1. School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University, Changchun 130012, China;
3. College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2012-05-02 Online:2013-03-26 Published:2013-03-27
Contact: LI Zhanshan E-mail:zslizsli@163.com

摘要/Abstract

摘要：

基于det-k-decomp算法, 通过引入同构的概念和对separator选择空间的进一步限制, 提出一类新的超树分解：分割的超树分解, 并提出一种具有较小超树宽度的超树分解方法: 基于分割的超树分解——sht-k-decomp, 该算法能有效提高约束满足问题的求解效率. 实验结果表明, sht-k-decomp算法多数情况下效率高于det-k-decomp算法.

关键词: 人工智能；超树分解；约束满足问题

Abstract:

Based on det-k-decomp algorithm, along with the noting isomorphic component and reducing the search space for an appropriate separator, the authors presented a new class of hypertree decomposition: separated hypertree decomposition and presented a new tractable hypertree decomposition algorithm——sht-k-decomp, which can improve the efficiency of constrain satisfaction problem solving effectively. The experimental results on most instances show that our method outperforms det-k-decomp.

Key words: artificial intelligence, hypertree decomposition, constraint satisfaction problems

中图分类号:

TP18

王涛, 王瑞芹, 李占山, 陈超. 基于分割的超树分解方法[J]. J4, 2013, 51(02): 257-266.

WANG Chao, WANG Rui-Qin, LI Tie-Shan, CHEN Chao. SeparationBased Hypertree Decomposition[J]. J4, 2013, 51(02): 257-266.

[1]	王立君, 富倩. 一种凹形区域和简单宽边界区域间的拓扑关系表示模型[J]. J4, 2013, 51(03): 487-490.
[2]	王雁苓, 孙利, 郭新辰, 吕学实. 应用字典数据建模[J]. J4, 2013, 51(02): 273-278.
[3]	李健, 欧阳继红, 王国伟, 陈岗. 一个带单洞区域和一个简单区域间的拓扑关系表示[J]. J4, 2012, 50(06): 1209-1213.
[4]	吴晓洲, 万里明, 韩霄松, 梁艳春, 吴春国. 基于隐马尔可夫模型的转录因子文本挖掘算法[J]. J4, 2012, 50(02): 320-322.
[5]	孙凤芳, 朱晓冬, 刘元宁, 张晓旭, 张巍, 李为韬, 李鑫. 一种Personality_OCC情感建模的新方法[J]. J4, 2012, 50(01): 106-110.
[6]	王海洋, 王江, 李红利, 陈颖源, 王延权. 基于Terminal滑模的HindmarshRose神经元放电同步控制[J]. J4, 2011, 49(06): 1087-1094.
[7]	钟毅, 刘桂霞, 郑明, 沈威, 赖丽娜, 周春光. 基于AP算法支持向量机的设计与应用[J]. J4, 2011, 49(05): 906-910.
[8]	葛金辉. 有时间窗的车辆路径问题及改进[J]. J4, 2011, 49(01): 105-111.
[9]	杜会盈, 李占山, 李宏博, 沈海娇. 图分割在Singleton弧相容算法中的应用[J]. J4, 2010, 48(06): 981-986.
[10]	王俊勇, 张长海, 刘元宁, 朱晓冬, 何飞. 基于ROI归一化的ICA/PCA虹膜识别方法[J]. J4, 2010, 48(05): 793-798.
[11]	池淑珍, 周春光, 张长胜, 杨草原. 一种受限于给定最大延误上界的单目标启发式算法[J]. J4, 2010, 48(05): 805-810.
[12]	王红梅, 李宏博, 李占山. 无环配置问题研究[J]. J4, 2010, 48(03): 444-448.
[13]	李永丽, 刘衍珩, 肖见涛, 李向涛, 关伟洲. 基于支持向量机的增量学习算法[J]. J4, 2010, 48(03): 464-467.
[14]	李妮娅, 刘大有, 张健. 面向制造业的产品配置器与PDM集成设计方法[J]. J4, 2010, 48(1): 73-78.
[15]	孙英娟, 黄岚, 翟延东, 蒲东兵, 周春光. 一种基于分类目标的启发式离散化算法[J]. J4, 2009, 47(6): 1251-1254.