人工智能05約束滿足問題(文件)
【正文】 nts, ., {WA=red, NT =green, Q=red, NSW =green, V =red, SA=blue, T=green} Constraint graph（約束圖） Binary CSP: 每個約束與 2個變量有關 約束圖 : 節(jié)點是變量 , 邊是約束 Generalpurpose CSP algorithms（通用 CSP算法） use the graph structure to speed up search. ., Tasmania is an independent subproblem! CSP的種類 離散變量 ? finite domains 有限值域 : n 個變量 , 值域大小 d → O(dn) 完全賦值 ., Boolean CSPs/布爾 CSP問題 (NPplete) ? infinite domains 無限值域 (integers, strings, etc.) ., job scheduling, variables are start/end days for each job 不能通過枚舉來描述值域，只能用 約束語言 , ., 線性約束可解 , 非線性約束不可解 連續(xù)值域的變量 ., 哈勃望遠鏡觀測的開始、結(jié)束時間 線性規(guī)劃問題 linear constraints solvable in polynomial time by linear programming(LP) methods 約束的種類 ? Unary（一元） 約束只限制單個變量的取值 , ., SA ≠ green ? Binary（二元）約束 與兩個變量有關 , ., SA ≠ WA ? Higherorder （高階）約束 involve 3 or more variables, ., cryptarithmetic（密碼算數(shù)） column constraints ? 偏好約束 (soft constraints), ., red is better than green often representable by a cost for each variable assignment（個體變量賦值的耗散） →約束優(yōu)化問題 Example: 密碼算數(shù) 變量 : F T U W R O X1 X2 X3 值域 : {0,1,2,3,4,5,6,7,8,9} 約束 : alldiff (F,T,U,W,R,O) O + O = R + 10 dn leaves !!!! Backtracking search回溯搜索 變量賦值具有可交換性 , 也就是說 [ WA = red then NT = green ] same as [ NT = green then WA = red ] 在搜索樹的每個節(jié)點上只考慮單個變量的可能賦值 b = d and there are dn leaves Depthfirst search for CSPs with singlevariable assignments is called backtracking search 回溯搜索是處理 CSP問題最基礎的無信息搜索算法 Can solve nqueens for n ≈ 25 回溯搜索 Backtracking example Backtracking example Backtracking example Backtracking example 提高回溯效率 Generalpurpose methods can give huge gains in speed: 1. 哪一個變量應該被下一個賦值 ? 2. 賦值應該以什么樣的順序被嘗試 ? 3. 能更早察覺到不可避免的失敗嗎 ? 4. Can we t
物理相關推薦
鄂ICP備17016276號-1