结合Separator的约束满足问题树分解方法

吉林大学学报(理学版)

结合Separator的约束满足问题树分解方法

吕巍, 张舒娟

吉林大学计算机科学与技术学院, 长春 130012

收稿日期:2015-04-21 出版日期:2016-03-26 发布日期:2016-03-23
通讯作者: 张舒娟 E-mail:zhangshujuan2009@yeah.net

Tree Decomposition Method Combined with Separator in Constraint Satisfaction Problems

LV Wei, ZHANG Shujuan

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2015-04-21 Online:2016-03-26 Published:2016-03-23
Contact: ZHANG Shujuan E-mail:zhangshujuan2009@yeah.net

摘要/Abstract

摘要：

基于树分解的回溯搜索算法, 结合separator分解算子提出一种新的搜索算法BTD⁺-MAC. 该算法在搜索时, 优先选择separator中的变量进行相容性检查和实例化, 由于树宽度的减小能提高约束传播的效率, 进而提高问题求解效率. 对几组benchmark问题进行测试, 测试结果表明, 该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.

关键词: 人工智能, 约束满足问题, 树分解, 回溯搜索, 启发式方法

Abstract:

Based on the tree decomposition backtracking search algorithm, combined with the separator decomposition operator, we proposed a new search algorithm BTD⁺-MAC. The algorithm first selected the variables in separator to carry on the consistency checks and instantiation during search, so the efficiency of constraint propagation could be improved by reducing the width of the tree and further improved the efficiency of solving problems. We tested several sets of benchmark problems. The results show that the algorithm is more efficient than the MAC3rm and BTD-MAC algorithm in solving the problem.

Key words: artificial intelligence, constraint satisfaction problem, tree decomposition, backtracking search, heuristic method

中图分类号:

TP18

吕巍, 张舒娟. 结合Separator的约束满足问题树分解方法[J]. 吉林大学学报(理学版), 2016, 54(02): 291-296.

LV Wei, ZHANG Shujuan. Tree Decomposition Method Combined with Separator in Constraint Satisfaction Problems[J]. Journal of Jilin University Science Edition, 2016, 54(02): 291-296.

[1]	费敏学, 黄东岩, 卢祎琳, 乔建磊. 集成多种改进方法的增强灰狼优化算法[J]. 吉林大学学报(理学版), 2025, 63(3): 829-0834.
[2]	李健, 王海瑞, 王增辉, 付海涛, 于维霖. 改进SHO优化神经网络模型[J]. 吉林大学学报(理学版), 2025, 63(3): 835-0844.
[3]	关路, 李健, 苏海涛, 祝天业, 于维霖. THGS-PID水肥一体化控制系统[J]. 吉林大学学报(理学版), 2025, 63(2): 567-0572.
[4]	董飒, 欧阳若川, 徐海啸, 刘杰, 刘大有, 李婷婷, 王鑫禄. 引入激活扩散的类分布关系近邻分类器[J]. 吉林大学学报(理学版), 2024, 62(4): 915-922.
[5]	张博, 向旭, 贾俊龙, 张学洪, 李春奇, 彭君. 基于LightGBM的天然气管道周围滑坡灾害预测方法[J]. 吉林大学学报(理学版), 2023, 61(2): 338-346.
[6]	吴致远, 齐红, 姜宇, 崔楚朋, 杨宗敏, 薛欣慧. 特征图自适应知识蒸馏模型[J]. 吉林大学学报(理学版), 2022, 60(4): 881-888.
[7]	蔡毛毛, 李占山, 董学阳. 一种笛卡尔积压缩的负表约束上表缩减算法[J]. 吉林大学学报(理学版), 2019, 57(3): 591-597.
[8]	杜江珊, 李占山. 基于减少检索的负表约束优化算法[J]. 吉林大学学报(理学版), 2018, 56(2): 335-339.
[9]	刘颖, 贺聪, 张清芳. 基于核相关分析算法的情感识别模型[J]. 吉林大学学报(理学版), 2017, 55(06): 1539-1544.
[10]	王多民, 刘淑芬. 一种使用log函数的新型修正激活单元LogReLU[J]. 吉林大学学报(理学版), 2017, 55(03): 617-622.
[11]	黄蔚, 付兴宇, 李占山. Knapsacks约束的弧相容改进算法[J]. 吉林大学学报(理学版), 2017, 55(01): 95-102.
[12]	王江涛. 基于背景差分和粒子滤波的运动目标跟踪算法[J]. 吉林大学学报(理学版), 2015, 53(05): 999-1005.
[13]	许苍竹, 郝爽, 李博宇, 刘明慧. 基于MAC的动态回溯算法优化[J]. 吉林大学学报(理学版), 2015, 53(02): 285-290.
[14]	于合龙, 刘浩洋, 苏恒强, 王增辉. 基于图像Canny边缘检测和Hough变换算法的高温结构[J]. 吉林大学学报(理学版), 2014, 52(03): 519-524.
[15]	王永虎, 管庆吉, 李劲松, 齐妙. 基于滤波的单幅图像去雾方法[J]. 吉林大学学报(理学版), 2014, 52(03): 525-530.