map coloring 约束满足问题：地图着色 _约束

人智导（四）：约束满足问题
约束满足问题()
CSP问题的定义
约束满足问题的定义：
约束满足问题：地图着色(map )
如图
问题的解是满足约束的变量赋值，如：
【map coloring约束满足问题：地图着色】{ W A = r e d , N T = g r e e n , Q = ? r e d , N S W = g r e e n , V = r e d , S A = b l u e , T = g r e e n } \{WA=red,~NT=green,~Q=-red,~NSW=green,~V=red,~SA=blue,~T=green\} {WA=red,NT=green,Q=?red,NSW=green,V=red,SA=blue,T=green} 约束满足问题：八皇后问题
约束规则：同一行或同一列、或统一斜线上不能有两个或以上的
形式化描述：
约束满足中的变量与约束目标测试：检查是否满足所有约束条件 CSP问题的解决
标准搜索方法解决CSP问题
CSP问题的解：必须是一个满足约束的完全赋值，若有n个变量，n也就是解的路径深度回溯搜索算法
思路：
Function BACKTRACKING-SEARCH (csp) returns solution or failurereturn RECURSIVE-BACKTRACKING({},csp)Function RECURSIVE-BACKTRACKING(assignment, csp) returns solution or failureif assignment is complete then return assignmentvar <--- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment, csp)for each value in ORDER-DOMAIN-VALUES(var assignment, csp) doif value is consistent with assignment given CONSTRAINTS[csp] thenadd{var = value} to assignmentresult <--- RECURSIVE-BACKTRACKING(assignment, csp)if result != failure then return resultremove {var = value} from assignmentreturn failure
深度优先搜索+有序变量赋值+违反约束即失败
启发式：优先选择合法取值最少变量（最受约束变量）
标准问题求解与完全状态问题对比

文章插图
CSP解决完全状态问题：如何发现满足约束的完全赋值完全状态问题
局部搜索：问题的完整状态(-state)形式表示
如下图：
初始状态违反了约束，采用局部搜索来消除违反的约束
算法：最小冲突算法Min-

Function MIN-CONFLICTS(csp, max_steps) returns a solution or failureinputs:cspmax_steps //最大尝试次数current <--- an initial complete assignment for cspfor i=1 to max_steps doif current is a solution for csp then return currentvar <--- a randomly chosen conflicted variable from csp.VARIABLESvalue <--- the value v for var that minimizes CONFLICTS(var, v, current, csp)set var = value in currentreturn failure

最小冲突算法：每一步搜索为一个变量赋予新值，启发式是新值必须与其他变量相冲突的数目最小化。
爬山或模拟退火等局部搜素可以被应用于目标优化。
总结
局部搜索问题