人工智能05約束滿足問(wèn)題-wenkub.com
2025-02-17 12:28 本頁(yè)面
【正文】 220= seconds at 10 million nodes/sec 樹狀結(jié)構(gòu)的 CSPs Theorem: if the constraint graph has no loops, the CSP can be solved in O(n X2 X2 + T + T = O + 10 第五章 約束滿足問(wèn)題 Review: Last Chapter ? Bestfirst search Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy bestfirst search expands lowest h — inplete and not always optimal A* search expands lowest g+ h — plete and optimal — also optimally efficient (up to tiebreaks, for forward search) Admissible heuristics can be derived from exact solution of relaxed problems Review: Last Chapter Local search algorithms ? the path to the goal is irrelevant。 X3 X3 = F, T ≠ 0, F ≠ 0 約束超圖 Realworld CSPs Assignment problems（分配問(wèn)題） ., who teaches what class who reviews which papers Timetabling problems（時(shí)間表安排問(wèn)題） ., which class is offered when and where? Hardware configuration（硬件配置問(wèn)題） Transportation scheduling（交通調(diào)度） Factory scheduling（工廠調(diào)度） Floorplanning（平面布置） Notice that many realworld problems involve realvalued variables 列舉分配 指數(shù)時(shí)間 dn But plete can we be clever about exponential time algorithms? 形式化描述標(biāo)準(zhǔn)搜索 (incremental增量形式化 ) 從簡(jiǎn)單直白的方法開始，狀態(tài)被定義為已被賦值的變量 ? 初始狀態(tài) : 空的賦值 , { } ? 后繼函數(shù) : 給一個(gè)未賦值變量賦值使之不與當(dāng)前狀態(tài)沖突 → fail 如果沒有合法賦值 ? 目標(biāo)測(cè)試 : 檢驗(yàn)當(dāng)前賦值是否完全 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! d2) time 任何一個(gè)樹狀結(jié)構(gòu)的 CSP問(wèn)題可以在變量個(gè)數(shù)的線性時(shí)間內(nèi)求解 Compare to general CSPs, where worstcase time is O(dn) 這個(gè)性質(zhì)同樣適用于邏輯
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1