【正文】 the goal state itself is the solution ? keep a single current state, try to improve it Hillclimbing search depending on initial state, can get stuck in local maxima Simulated annealing search escape local maxima by allowing some “bad” moves but gradually decrease their frequency Local beam search Keep track of k states rather than just one Geic algorithms 本章大綱 ? CSP examples ? Backtracking search for CSPs ? Problem structure and problem deposition ? 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(d