人工智能05約束滿(mǎn)足問(wèn)題(已改無(wú)錯(cuò)字)
2023-03-10 12:28:47 本頁(yè)面
【正文】 是可能需要經(jīng)過(guò)一些計(jì)算來(lái)確定這個(gè)值 結(jié)合以上啟發(fā)式來(lái)解決 1000 queens 是可行的 提高回溯效率 Generalpurpose methods can give huge gains in speed: 1. 哪一個(gè)變量應(yīng)該被下一個(gè)賦值 ? 2. 賦值應(yīng)該以什么樣的順序被嘗試 ? 3. 能更早察覺(jué)到不可避免的失敗嗎 ? 4. Can we take advantage of problem structure? Forward checking—前向檢驗(yàn) ? Idea: 保持記錄未賦值變量的剩余合法值 當(dāng)任一變量沒(méi)有合法值時(shí)結(jié)束搜索 前向檢驗(yàn) ? Idea: 保持記錄未賦值變量的剩余合法值 當(dāng)任一變量沒(méi)有合法值時(shí)結(jié)束搜索 前向檢驗(yàn) ? Idea: 保持記錄未賦值變量的剩余合法值 當(dāng)任一變量沒(méi)有合法值時(shí)結(jié)束搜索 前向檢驗(yàn) ? Idea: 保持記錄未賦值變量的剩余合法值 當(dāng)任一變量沒(méi)有合法值時(shí)結(jié)束搜索 Constraint propagation — 約束傳播 前向檢驗(yàn)將信息從已賦值變量傳播到未賦值變量，但是并不能提前檢測(cè)出所有矛盾 : NT and SA cannot both be blue! 約束傳播必須反復(fù)應(yīng)用直到不在有矛盾 Arc consistency — 弧相容 最簡(jiǎn)單的傳播形式是使每條弧相容 X → Y 是相容的，當(dāng)且僅當(dāng) 對(duì)變量 X中的任意值 x 都存在相容賦值 y Arc consistency — 弧相容 最簡(jiǎn)單的傳播形式是使每條弧相容 X → Y 是相容的，當(dāng)且僅當(dāng) 對(duì)變量 X中的任意值 x 都存在相容賦值 y Arc consistency — 弧相容 最簡(jiǎn)單的傳播形式是使每條弧相容 X → Y 是相容的，當(dāng)且僅當(dāng) 對(duì)變量 X中的任意值 x 都存在相容賦值 y 如果 X 失去了一個(gè)值 , X 的鄰居需要再次核對(duì) Arc consistency — 弧相容 最簡(jiǎn)單的傳播形式是使每條弧相容 X → Y 是相容的，當(dāng)且僅當(dāng) 對(duì)變量 X中的任意值 x 都存在相容賦值 y 如果 X 失去了一個(gè)值 , X 的鄰居需要再次核對(duì) 弧相容能比前向檢驗(yàn)更早發(fā)現(xiàn)矛盾 被運(yùn)行于搜索前的預(yù)處理，或者每一次賦值后 弧相容算法 AC3 O(n2d3) (but detecting all is NPhard) 提高回溯效率 Generalpurpose methods can give huge gains in speed: 1. 哪一個(gè)變量應(yīng)該被下一個(gè)賦值 ? 2. 賦值應(yīng)該以什么樣的順序被嘗試 ? 3. 能更早察覺(jué)到不可避免的失敗嗎 ? 4. Can we take advantage of problem structure? 本章大綱 ? CSP examples ? Backtracking search for CSPs ? Problem structure and problem deposition ? Local search for CSPs 問(wèn)題的結(jié)構(gòu) T島和大陸是 不連通的 約束圖中的 連通域 是可辨認(rèn)的 問(wèn)題的結(jié)構(gòu) 假設(shè)每個(gè)子問(wèn)題有總共 n個(gè)變量中的 c個(gè)變量 最差情況下的工作量為 O(n/c dc)，是 n的線(xiàn)性函數(shù) ., n=80, d=2, c=20 280= 4 billion years at 10 million nodes/sec 4 220= seconds at 10 million nodes/sec 樹(shù)狀結(jié)構(gòu)的 CSPs Theorem: if the constraint graph has no loops, the CSP can be solved in O(n d2) time
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1