人工智能05約束滿足問題-文庫吧在線文庫
【正文】 ution of relaxed problems Review: Last Chapter Local search algorithms ? the path to the goal is irrelevant。 220= seconds at 10 million nodes/sec 樹狀結構的 CSPs Theorem: if the constraint graph has no loops, the CSP can be solved in O(n X2 X2 + T + T = O + 10 X3 X3 = F, T ≠ 0, F ≠ 0 約束超圖 Realworld CSPs Assignment problems（分配問題） ., who teaches what class who reviews which papers Timetabling problems（時間表安排問題） ., which class is offered when and where? Hardware configuration（硬件配置問題） Transportation scheduling（交通調度） Factory scheduling（工廠調度） Floorplanning（平面布置） Notice that many realworld problems involve realvalued variables 列舉分配 指數(shù)時間 dn But plete can we be clever about exponential time algorithms? 形式化描述標準搜索 (incremental增量形式化 ) 從簡單直白的方法開始，狀態(tài)被定義為已被賦值的變量 ? 初始狀態(tài) : 空的賦值 , { } ? 后繼函數(shù) : 給一個未賦值變量賦值使之不與當前狀態(tài)沖突 → fail 如果沒有合法賦值 ? 目標測試 : 檢驗當前賦值是否完全 1. This is the same for all CSPs! 2. Every solution appears at depth n with n variables → use depthfirst search 3. Path is irrelevant, so can also use pletestate formulation（完全狀態(tài)形式化） 4. b = (n l )d at depth l, hence n! dc)，是 n的線性函數(shù) ., n=80, d=2, c=20 280= 4 billion years at 10 million nodes/sec 4 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 depo
物理相關推薦
鄂ICP備17016276號-1