人工智能原理人工智能原理 (38).pdf

《人工智能原理人工智能原理 (38).pdf》由会员分享，可在线阅读，更多相关《人工智能原理人工智能原理 (38).pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Principles of Artificial Intelligence1The Structure of ProblemsPrinciples of Artificial Intelligence2Contents 6.5.1 Decomposing Problem 6.5.2 Independent Sub-problems 6.5.3 Tree-structured Problems 6.5.4 Reduce Constraint Graphs to Tree StructuresPrinciples of Artificial Intelligence:Searching:CSP3

2、The structure of problem as represented by constraint graph can be used to find solutions.由约束图所表征的问题结构，可以用于寻找解。The complexity of solving a CSP is strongly related to the structure of its constraint graph.求解一个CSP问题的复杂性，与约束图的结构密切相关。The problem in the real world can be decomposed into many sub-problems

3、.现实世界的问题可以被分解为许多子问题。Decomposing Problem 问题分解6.5.The Structure of ProblemsExample:Coloring Tasmania and coloring the mainland are independent sub-problems.对塔斯曼尼亚着色与澳洲大陆着色是相互独立的子问题。Divide and Conquer!Principles of Artificial Intelligence:Searching:CSP4 They are identifiable as connected components of

4、constraint graph.独立子问题可被标识为约束图的联接组件。Suppose a graph of n variables can be broken into sub-problems of only cvariables:each worst-case solution cost is O(n/c)dc),linear in n.设n个变量的图可分解为仅有c个变量的子问题：每个最坏解的代价是O(n/c)dc),n的线性关系。Without the decomposition,the total work is O(dn).如果不分解，则总的运行是O(dn)。E.g.,assumi

5、ng n=80,d=2,c=20,search 10 million nodes/sec.例如，假如 n=80，d=2，c=20，每秒搜索1千万个节点 Original problem:dn=280=4 billion years;4 sub-problems:(n/c)dc=(80/20)220=0.4 seconds.原始问题：dn=280=40亿年；4个子问题：(n/c)dc=(80/20)220=0.4秒。Independent Sub-problems独立子问题6.5.The Structure of ProblemsPrinciples of Artificial Intellig

6、ence:Searching:CSP5 Any tree-structured CSP can be solved in time linear in the number of variables.任何树结构的CSP都可以用变量数中的时间线性加以解决。The method to solve a tree-structured CSP:first pick any variable to be root of tree,and choose an ordering(called a topological sort).求解树结构CSP的方法：先挑选任意变量作为树的根，然后再选择一个排列（称为拓

7、扑排序）。Tree-structured Problems 树结构问题6.5.The Structure of ProblemsThe constraint graph of a tree-structured CSP树结构CSP的约束图A linear ordering of the variables consistent with the tree with A as the root一种以A为根与该树的变量一致的线性排列For a tree-structured CSP,it can be solved in O(n d2)time.对于一个树结构的CSP，可以在O(nd2)时间内得到

8、解。Principles of Artificial Intelligence:Searching:CSP6Algorithm to Solve Tree-structured CSPs 求解树结构CSPs的算法6.5.The Structure of Problemsfunction TREE-CSP-SOLVER(csp)returns a solution,or failureinputs:csp,a CSP with components X,D,Cn number of variables in Xassignment an empty assignmentroot any vari

9、able in XX TOPOLOGICAL-SORT(X,root)for j=n down to 2 doMAKE-ARC-CONSISTENT(PARENT(Xj),Xj)if it cannot be made consistent then return failurefor i=1 to n doassignmentXi any consistent value from Diif there is no consistent value then return failurereturn assignmentPrinciples of Artificial Intelligenc

10、e:Searching:CSP7Remove SA移除SA 1stapproach:cutset conditioning 第1种途径：割集调节 It can reduce a general CSP to a tree-structured one,and is quite efficient if a small cutset can be found.可以将一个通用CSP问题简化为一个树结构CSP，并且若能够找到一个小割集则相当有效。Conditioning:Instantiate a variable,prune its neighbors domains.调节：对一个变量进行实例化，

11、剪去它的相邻范畴。Reduce Constraint Graphs to Tree Structures 简化约束图为树结构6.5.The Structure of ProblemsIf cutset has size c,then run time is O(dc(n c)d2).若割集的尺寸为c，则运行时间是O(dc(n c)d2)。Principles of Artificial Intelligence:Searching:CSP8 2ndapproach:tree decomposition 第2途种径：树分解 This techniques transform CSP into a

12、 tree of sub-problems and are efficient if the tree width of the constraint graph is small.这种技法将CSP转换成一棵子问题树，并且当该约束图的树宽较小时很有效。Reduce Constraint Graphs to Tree Structures 简化约束图为树结构6.5.The Structure of ProblemsDecomposition分解If a graph has tree width w,then run time is O(ndw+1).若一个图的树宽为w，则运行时间是O(ndw+1)。