《计算机应用研究》|Application Research of Computers

基于动态度的回溯算法求解大值域约束满足问题

Dynamic degree based backtracking algorithm to solve constraint satisfaction problems with large domains

免费全文下载 (已被下载 次)  
获取PDF全文
作者 张学才,赵春艳
机构 上海理工大学 理学院
统计 摘要被查看 次,已被下载
摘要 针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC(dynamic degree-Maintaining Arc Consistency)回溯算法和基于值域与动态度比值的dom/ddeg-MAC(dom/dynamic degree-Maintaining Arc Consistency)回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容(MAC)技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明:在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。
关键词 约束满足问题;动态度;回溯算法;维持弧相容
基金项目 国家自然科学基金资助项目(11301339)
国家自然科学基金国际(地区)合作与交流项目(11491240108)
本文URL http://www.arocmag.com/article/02-2022-05-010.html
收稿日期
修回日期
页码 -
中图分类号 TP301.5
文献标志码