人工智能05約束滿足問(wèn)題(完整版)
【正文】 sition ? Local search for CSPs Constraint satisfaction problems (CSPs) Standard search problem: state is a “black box“ – any old data structure that supports goal test, eval, successor 任何可以由目標(biāo)測(cè)試、評(píng)價(jià)函數(shù)、后繼函數(shù)訪問(wèn)的數(shù)據(jù)結(jié)構(gòu) CSP: state is defined by variables Xi with values from domain（值域） Di goal test is a set of constraints specifying allowable binations of values for subsets of variables 每個(gè)約束包括一些變量的子集，并指定這些子集的值之間允許進(jìn)行的合并 Simple example of a formal representation language（形式化表示方法） Allows useful generalpurpose（通用的，而不是問(wèn)題特定的 ）algorithms with more power than standard search algorithms Example: MapColoring 變量 WA, NT, Q, NSW, V, SA, T 值域 Di = {red,green,blue} 約束 : adjacent regions must have different colors ., WA ≠ NT, or (if the language allows this), or (WA,NT) ∈ {(red,green),(red,blue),(green,red), (green,blue), … } Example: MapColoring Solutions are assignments satisfying all constraints, ., {WA=red, NT =green, Q=red, NSW =green, V =red, SA=blue, T=green} Constraint graph（約束圖） Binary CSP: 每個(gè)約束與 2個(gè)變量有關(guān) 約束圖 : 節(jié)點(diǎn)是變量 , 邊是約束 Generalpurpose CSP algorithms（通用 CSP算法） use the graph structure to speed up search. ., Tasmania is an independent subproblem! CSP的種類 離散變量 ? finite domains 有限值域 : n 個(gè)變量 , 值域大小 d → O(dn) 完全賦值 ., Boolean CSPs/布爾 CSP問(wèn)題 (NPplete) ? infinite domains 無(wú)限值域 (integers, strings, etc.) ., job scheduling, variables are start/end days for each job 不能通過(guò)枚舉來(lái)描述值域，只能用 約束語(yǔ)言 , ., 線性約束可解 , 非線性約束不可解 連續(xù)值域的變量 ., 哈勃望遠(yuǎn)鏡觀測(cè)的開始、結(jié)束時(shí)間 線性規(guī)劃問(wèn)題 linear constraints solvable in polynomial time by linear programming(LP) methods 約束的種類 ? Unary（一元） 約束只限制單個(gè)變量的取值 , ., SA ≠ green ? Binary（二元）約束 與兩個(gè)變量有關(guān) , ., SA ≠ WA ? Higherorder （高階）約束 involve 3 o
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1