人工智能05約束滿足問題-資料下載頁
2025-02-19 12:28本頁面
【正文】 任何一個樹狀結構的 CSP問題可以在變量個數(shù)的線性時間內求解 Compare to general CSPs, where worstcase time is O(dn) 這個性質同樣適用于邏輯與概率推理 : 一個重要的例子：語法約束與推理復雜度之間的關系 Algorithm for樹狀結構的 CSPs 1. 任選一個節(jié)點作為樹的根節(jié)點，從跟節(jié)點到葉節(jié)點按順序排列，每個節(jié)點的父節(jié)點都在它的前面 2. 令 j從 n到 2, 在弧 (Parent(Xj),Xj)上應用弧相容算法，從 Xj的值域中刪除必要的值 j從 1到 n, 賦給變量 Xj 與變量 Parent(Xj ) 相容的值 Complexity: O(n d2) 近似樹狀結構 調整 : 刪除一個變量，修建其鄰居的值域 割集調整 : 刪除一組變量（環(huán)割集）使剩下的約束圖為一顆樹 環(huán)割集大小 c → 運行時間 O(dc(n c)d2), 當 c很小時比直接回溯有巨大的節(jié)省 尋找最小的環(huán)割集是一個 NP難題，但存在有效的近似算法 本章大綱 ? CSP examples ? Backtracking search for CSPs ? Problem structure and problem deposition ? Local search for CSPs CSPs的迭代算法 爬山算法、模擬退火算法是處理完全狀態(tài)的形式化問題（所有變 量已被賦值）的典型算法 應用到 CSPs: 允許狀態(tài)有未滿足的約束條件 操作者 再次分配 變量值 變量選擇 : 隨機選擇任意有沖突的變量 選擇新值的時候采用 minconflicts（最小沖突） 啟發(fā)式 : choose value that violates the fewest constraints 選擇會造成與其它變量的沖突最小的值 ., 爬山算法 中 h(n) = total number of violated constraints Example: 4Queens 狀態(tài) : 4 queens in 4 columns (44= 256 states) 行動 : move queen in column 目標測試 : no attacks 評價 : h(n) = number of attacks 最小沖突的性能 在 n皇后問題上，給定隨機的初始狀態(tài)，最小沖突算法的運行時間大體上獨立于問題大小，具有很高的性能 (., n = 10,000,000) 對隨機生成的 CSP以上結論一般成立，除了一個狹窄的范圍比 Example: 3SAT problems 每個約束涉及到 3個變量 Speedup1: 模擬退火算法 Idea: 用一些 ”壞的 ”移動來避開局部極大值 但 逐步減小 其頻率 If 新狀態(tài)比現(xiàn)有狀態(tài)好，移動到新狀態(tài) Else 否則以某個小于 1的概率接受該移動 此概率隨溫度“ T”降低而下降 Speedup2: minmax optimization Speedup2: minmax optimization Summary CSPs 是一類特殊的問題 : 狀態(tài)被定義為一組固定的變量值 目標測試被變量取值間的約束所定義 回溯 = 深度優(yōu)先搜索的一種形式，對每個節(jié)點的單一變量賦值 ? 變量排序和取值選擇啟發(fā)式大大提升搜索效率 ? 前向檢驗能夠在矛盾之前提前阻止賦值 ? 約束傳播 (., 弧相容 ) 做了一些附件的工作去約束取值和發(fā)現(xiàn)矛盾 ? The CSP representation allows analysis of problem structure ? 樹狀的 CSPs 能夠在線性時間內解決 ? 迭代最小沖突算法在實踐中經常是很有效的 作業(yè) ， ， 演講完畢，謝謝觀看！
物理相關推薦
鄂ICP備17016276號-1