e約束滿足人工智能(ai)(編輯修改稿)
2025-06-15 13:45 本頁面
【文章內(nèi)容簡介】 限 CSP : 一些或所有的變量的值域是無限的 ., 實(shí)數(shù)線性規(guī)劃 : ? 本課程只討論有限 CSP ??ni , ni , 1 1 i , 2 2 i , 0nj , nj , 1 1 j , 2 2 j , 0f o r i = 1 , 2 , . . . , p : a x + a x + . . . + a x af o r j = 1 , 2 , . . . , q : b x + b x + . . . + b x bCSP 描述為搜索問題 ? n個(gè)變量 X1, ..., Xn ? 合法賦值 : {Xi1 ? vi1, ..., Xik ? vik}, 0? k ? n, 即取值 vi1, ..., vik滿足所有與變量 Xi1, ..., Xik有關(guān)的約束 ? 完全賦值 : k由 0到 n， 每個(gè)變量都得到了賦值 [變量值域大小為 d, 則有 O(dn) 種完全賦值 ] ? 狀態(tài) : 合法賦值 ? 初始狀態(tài) : 空賦值 {}, 即 k = 0， 也就是還沒有變量得到賦值 ? 狀態(tài)的后繼 : {Xi1?vi1, ..., Xik?vik} ? {Xi1?vi1, ..., Xik?vik, Xik+1?vik+1} ? 目標(biāo)測(cè)試 : k = n， 即 n個(gè)變量都得到了賦值 ? 4 變量 X1, ..., X4 ? 令節(jié)點(diǎn) N的合法賦值為 : A = {X1 ? v1, X3 ? v3} ? 以為變量 X4取值為例 ? 令 X4 的值域?yàn)? {v4,1, v4,2, v4,3} ? A的后繼為以下賦值中的合法賦值 : {X1 ? v1, X3 ? v3 , X4 ? v4,1 } {X1 ? v1, X3 ? v3 , X4 ? v4,2 } {X1 ? v1, X3 ? v3 , X4 ? v4,3 } 回溯搜索 Backtracking Search 本質(zhì)即使用遞歸的簡化深度優(yōu)先算法 回溯搜索 (3 變量 ) 賦值 Assignment = {} 賦值 Assignment = {(X1,v11)} X1 v11 回溯搜索 (3 變量 ) 賦值 Assignment = {(X1,v11), (X3,v31)} X1 v11 v31 X3 回溯搜索 (3 變量 ) 賦值 Assignment = {(X1,v11), (X3,v31)} X1 v11 v31 X3 X2 假設(shè)沒有一個(gè) X2的取值能構(gòu)成合法賦值 于是，搜索算法 回溯 到前一個(gè)變量(X3)并嘗試另外的賦值 回溯搜索 (3 變量 ) 賦值 Assignment = {(X1,v11), (X3,v32)} X1 v11 X3 v32 v31 X2 回溯搜索 (3 變量 ) 賦值 Assignment = {(X1,v11), (X3,v32)} X1 v11 X3 v32 X2 假設(shè)仍然沒有一個(gè) X2的取值能構(gòu)成合法賦值 搜索算法回溯到前一個(gè)變量(X3)并嘗試另外的賦值。但假設(shè) X3只有兩個(gè)可能的取值。于是算法回溯到 X1 v31 X2 回溯搜索 (3 變量 ) 賦值 Assignment = {(X1,v12)} X1 v11 X3 v32 X2 v31 X2 v12 回溯搜索 (3 變量 ) Assignment = {(X1,v12), (X2,v21)} X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 回溯搜索 (3 變量 ) Assignment = {(X1,v12), (X2,v21)} X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 算法不需要考慮與其他子樹中 次序一樣的變量 回溯搜索 (3 變量 ) Assignment = {(X1,v12), (X2,v21), (X3,v32)} X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 v32 X3 回溯搜索 (3 變量 ) Assignment = {(X1,v12), (X2,v21), (X3,v32)} X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 v32 X3 算法不需要考慮那些在其它 子樹中次序一樣的 X3賦值 回溯搜索 (3 變量 ) Assignment = {(X1,v12), (X2,v21), (X3,v32)} X1 v11 X3 v32 X2 v31 X2 v12 v21 X2 v32 X3 由于只有三個(gè)變量，因此 賦值已完全 回溯搜索 (3 變量 ) 回溯算法 Backtracking Algorithm CSPBACKTRACKING(A) 1. If assignment A is plete then return A 2. X ? select a variable not in A 3. D ? select an ordering on the domain of X 4. For each value v in D do a. Add (X?v) to A b. If A is valid then i. result ? CSPBACKTRACKING(A) ii. If result ? failure then return result 5. Return failure Call CSPBACKTRACKING({}) [該遞歸算法會(huì)保存太多的數(shù)據(jù)到內(nèi)存中，用迭代改進(jìn)將會(huì)節(jié)省許多內(nèi)存， 感興趣的同學(xué)可以進(jìn)一步思考。 ] 地圖著色問題 Map Coloring {} WA=red WA=green WA=blue WA=red NT=green WA=red NT=blue WA=red NT=green Q=red WA=red NT=green Q=blue WA NT SA Q NSW V T CSP回溯效率的關(guān)鍵問題 CSPBACKTRACKING(A) 1. If assignment A is plete then return A 2. X ? select a variable not in A 3. D ? select an ordering on the domain of X 4. For each value v in D do a. Add (X?v) to A b. If a is valid then i. result ? CSPBACKTRACKING(A) ii. If result ? failure then return result 5. Return failure 1) 下一個(gè)將選擇哪一個(gè)變量來賦值 ? The current assignment may not lead to any solution, but the algorithm still does know it. Selecting the right variable to which to assign a value may help discover the contradiction more quickly 2) 變量 X的（多個(gè)）值應(yīng)該按一個(gè)什么樣的次序進(jìn)行賦值 ? The current assignment may be part of a solution. Selecting the right value to assign to X may help d
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1