非二元约束满足问题求解  

Solving Non-Binary Constraint Satisfaction Problem

作　　者：孙吉贵[1,2,3] 景沈艳[1,2,3] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [3]复旦大学智能信息处理开放实验室,上海200433

出　　处：《计算机学报》2003年第12期1746-1752,共7页Chinese Journal of Computers

基　　金：国家自然科学基金 (60 0 730 39;60 2 730 80 );吉林省科技发展计划(2 0 0 2 0 30 6);吉林大学创新基金资助

摘　　要：在约束满足问题 (CSP)的研究中 ,大部分工作集中在二元约束 ,但处理实际问题时 ,常常会遇到非二元约束的情况 .该文在概要地讨论了两类求解非二元约束问题方法的基础上 ,研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法 ,并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法 ,以典型例子给出了实现系统的运行结果 .Most of the research on constraint satisfaction problems (CSPs) concentrates on binary constraints, however, non-binary constraints appear quite frequently when modeling real problems. In this paper, on the basis of summarizing two kinds of approaches on solving non-binary CSPs, we study a non-binary CSP method which combines constraint propagation with GAC backtracking algorithm, and implement it in our Constraint Solving Platform “MingYue (1.0 version)”. For some typical examples, we also give experimental results.

关 键 词：非二元约束满足问题 对偶图法 隐藏变量法 启发式搜索算法 

分 类 号：O224[理学—运筹学与控制论]