约束满足问题 CSP _生活百科

CSP(约束满足问题)【约束满足问题 CSP】CSP-Constraint Satisfaction Problem
基本介绍中文名：约束满足问题
外文名：CSP
全称：Constraint SatisfactionProblem
例如：图中结点的值
关键字：人工智慧
基本信息CSP（约束满足问题）：由一个变数集合和一个约束集合组成。问题的一个状态是由对一些或全部变数的一个赋值定义的完全赋值：每个变数都参与的赋值。问题的解是满足所有约束的完全赋值，或更进一步，使目标函式最大化。CSP={V,D,C}变数：V={V1,…,VN}例如：图中结点的值域：每个变数能取的d个值的集例如：D={R,G,B}约束：C={C1,…,CK}每个约束由一组变数与一列该组变数允许取的值组成例如：[(V2,V3),{(R,B),(R,G),(B,R),(B,G),(G,R),(G,B)}]通常隐式地定义约束，即，定义一个函式来测试一组变数是否满足该约束例如：对每条边(i,j)，有Vi?VjCSP的解：每个变数有一个满足所有相关约束的值特点：状态的分解代表：一组变数及其值利用状态的结构和通用启发方式通过确定违反约束的变数与值组合可取消大部分搜寻空间其他信息约束满足问题(CSP-Constraint Satisfaction Problem)是人工智慧研究领域的一个重要分支,现实生活中的很多问题,都可以用约束满足问题来建模,如视觉(Vision),调度中的资源分配(Resource allocation),时序推理(Temporal reasoning)等.约束满足问题通常都是NP-hard问题,在其众多求解算法中,基于回溯的搜寻算法(BT-backtracking algorithm)是一个完备的核心算法.该算法在选择实例化变数时,採用深度优先策略,若相容性检查失败则启动回溯机制,并通过引入展望(look-ahead)和回顾(look-back)两种模式,显着地提高了搜寻效率[1].基于冲突的向后跳转[2]和动态的回溯算法[3]等是回顾模式类的搜寻算法;基于相容性技术的算法是展望模式类的搜寻算法.而弧相容(AC-arc consistency)则是众多相容性算法中一个高效的相容性技术[4],如算法AC3[5],AC4[6],AC2001[7]等.由于弧相容维护(MAC-maintaining arc consistency)，具有高效的求解效率和低额空间代价的特点,所以MAC是求解约束满足问题的一个主流搜寻技术.