C-盲目搜索-人工智能(AI)

1、1,盲目（无信息）搜索Blind (Uninformed) Search （系统化的对可能的选择进行探索）R currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal: be in Bucharest Formulate problem: states: various cities actions: drive between cities Find solution: sequence of cities, e. g., Arad, Sibiu, Fagaras, Bucharest,5,Example:

2、 route-finding problem,6,Single-state problem formulation,A problem is defined by four items:,initial state e.g., “at Arad”,goal test, can be explicit, e.g., x = “at Bucharest” implicit, e.g., No Dirt(x),path cost (additive) e.g., sum of distances, number of a actions executed, etc. c(x,a,y) is the

3、step cost, assumed to be 0,successor function S(x) = set of action-state pairs e.g., S(Arad) = ,A solution is a sequence of actions leading from the initial state to a goal state,7,Tree search example,Sibiu,Arad,Fagaras,Oradea,Rimnicu,Timisoara,Zerind,Arad,8,搜索树Search Tree,Search tree,注意一些状态可能会被多次访问

4、,State graph,9,搜索节点状态 Search Nodes States,10,Search Nodes States,若状态允许重复访问，则即使状态空间有限，搜索树也将会是无限的,11,一个节点的数据结构Data Structure of a Node,一个节点N的深度从根节点到N的路径长度 （根节点的深度为0）,12,节点扩展Node expansion,搜索树的一个节点N的扩展包括： 1）评估状态（N）的后继函数 2）根据后继函数返回值，每一个状态生成一个子节点 节点生成 节点扩展 node generation node expansion,N,13,搜索策略Search S

5、trategy,边缘(fringe) 指所有还未扩展的节点 边缘用一个优先队列实现 INSERT(node,FRINGE) REMOVE(FRINGE) 队列FRINGE中节点的排列顺序决定了搜索策略,14,搜索算法Search Algorithm #1,SEARCH#1 If GOAL?(initial-state) then return initial-state INSERT(initial-node,FRINGE) Repeat: If empty(FRINGE) then return failure N REMOVE(FRINGE) s STATE(N) For every st

6、ate s in SUCCESSORS(s) Create a new node N as a child of N If GOAL?(s) then return path or goal state INSERT(N,FRINGE),Expansion of N,#2,15,搜索算法性能评价Performance Measures,完备性 Completeness一个搜索问题只要有解，搜索算法就一定能找到解的路径，则称该搜索算法是完备的 那么当问题无解的时候，将会怎样呢? 最优性 Optimality只要问题有解，搜索算法就一定能找到路径耗散最小的解，则称该搜索算法是最优的 复杂度 Com

7、plexity复杂度是评价算法所需要的时间及占用的内存空间大小,16,盲目 vs. 启发式策略Blind vs. Heuristic Strategies,盲目或(无信息) 策略没有利用状态的有关描述信息来确定FRINGE队列的排序，而只根据搜索树中节点的位置来进行搜索 启发式或(有信息) 策略利用状态的有关描述信息来确定FRINGE队列的排序（最有“希望”的节点被放在FRINGE队列的开始）,17,Example,对于盲目策略，N1和N2只是两个节点（在搜索树上的某个位置)，仅此而已,18,Example,而启发式策略 会计算节点状态与目标状态相比较，不在位的数码牌个数，认为N2比N1更有希

8、望（达到目标）,19,说明,一些搜索问题，比如(n2-1)-puzzle ，是NP-hard问题 这类问题的计算量至少为指数层次 ，没有人能够将这类问题的计算量降低到方次层次 只能是针对具体的问题实例尽可能高效的去求得问题的解答 这就是搜索策略的目标,20,盲目策略Blind Strategies,广度优先 Breadth-first 双向搜索 Bidirectional 深度优先 Depth-first 深度限制 Depth-limited 迭代深入 Iterative deepening 代价一致 Uniform-Cost(广度优先的一种变化),21,广度优先策略Breadth-First

9、 Strategy,新生成的节点放到FRING E队列的最后,FRINGE = (1),22,新生成的节点放到FRING E队列的最后,FRINGE = (2, 3),广度优先策略Breadth-First Strategy,23,新生成的节点放到FRING E队列的最后,FRINGE = (3, 4, 5),广度优先策略Breadth-First Strategy,24,新生成的节点放到FRING E队列的最后,FRINGE = (4, 5, 6, 7),广度优先策略Breadth-First Strategy,25,一些重要参数Important Parameters,1）所有状态中的最大

10、后继函数个数 搜索树的分支因子 b branching factor b of the search tree 2）初始状态与目标状态之间路径的最短长度( 耗散) 搜索树中最浅的目标节点的深度d depth d of the shallowest goal node in the search tree,26,评价Evaluation,b: 分支因子 d: 最浅目标节点的深度 广度优先搜索: 完备 Complete 最优 若每一步的耗散为1 生成的节点个数：?,27,评价Evaluation,b: 分支因子 d: 最浅目标节点的深度 广度优先搜索: 完备 Complete 最优 若每一步的耗散

11、为1 生成的节点个数：,1 + b + b2 + + bd = ?,28,评价Evaluation,b: 分支因子 d: 最浅目标节点的深度 广度优先搜索: 完备 Complete 最优 若每一步的耗散为1 生成的节点个数：,1 + b + b2 + + bd = (bd+1-1)/(b-1) = O(bd),29,评价Evaluation,b: 分支因子 d: 最浅目标节点的深度 广度优先搜索: 完备 Complete 最优 若每一步的耗散为1 生成的节点个数： 时间和空间的复杂度均为 O(bd),1 + b + b2 + + bd = (bd+1-1)/(b-1) = O(bd),30,大

12、O 符号Big O Notation,称 g(n) = O(f(n)，若存在两个正常数a 和 N，并满足下式： 对于所有 n N: g(n) af(n),31,时间与空间的要求,假设: b = 10; 1,000,000 nodes/sec; 100bytes/node,32,时间与空间的要求,假设: b = 10; 1,000,000 nodes/sec; 100bytes/node,33,说明,若一个问题无解，广度优先搜索可能会永远不停的搜索（如果状态空间是无限的或者状态允许重复访问）,34,双向搜索策略Bidirectional Strategy,2个边缘队列: FRINGE1 和 FR

13、INGE2,时间和空间复杂度为 O(bd/2) O(bd) 如果两边的搜索树都有着相同的分支因子 b,问题：如果两个方向搜索树的分支因子不相同的话，会怎样呢？,35,深度优先策略Depth-First Strategy,新生成的节点放在FRINGE队列的最前,1,36,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,37,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,38,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,39,新生成的节点放在F

14、RINGE队列的最前,1,深度优先策略Depth-First Strategy,40,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,41,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,42,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,43,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,44,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,

15、45,新生成的节点放在FRINGE队列的最前,1,深度优先策略Depth-First Strategy,46,评价Evaluation,b: 分支因子 d: 最浅目标节点的深度 m: 状态空间中任何路径的最大长度（叶节点的最大深度） 深度优先搜索： 完备? 最优?,47,b: 分支因子 d: 最浅目标节点的深度 m: 一个叶节点的最大深度 深度优先搜索： 对于有限的搜索树是完备的 不是最优 生成的节点数量 (最坏的情形下): 1 + b + b2 + + bm = O(bm) 时间复杂度 O(bm) 空间复杂度 O(bm) 或 O(m) 提醒: 广度优先要求O(bd)的时间和空间,评价Eval

16、uation,48,深度限制搜索Depth-Limited Search,深度截止于k的深度有限搜索（ k以下深度的节点不再扩展） 3种可能的结果： 有解 失败 (无解) 截止 （截止范围内无解）,49,迭代深入搜索Iterative Deepening Search,结合了广度优先和深度优先搜索两者的优点 主要思想:,IDS For k = 0, 1, 2, do: 执行深度截止为k的深度优先搜索 (即，仅生成深度 k的节点),Totally horrifying !,50,迭代的深入,51,迭代的深入,52,迭代的深入,53,性能,迭代深入搜索: 完备 最优 如果每一步的耗散=1 时间复杂

17、度: (d+1)(1) + db + (d-1)b2 + + (1) bd = O(bd) 空间复杂度: O(bd) or O(d),54,具体计算,db + (d-1)b2 + + (1) bd = bd + 2bd-1 + 3bd-2 + + db = (1 + 2b-1 + 3b-2 + + db-d)bd (Si=1, ib(1-i)bd = bd (b/(b-1)2,55,d = 5 and b = 2,120/63 2,生成的节点个数 (广度优先 & 迭代深入),56,d = 5 and b = 10,123,456/111,111 1.111,生成的节点个数 (广度优先 & 迭代

18、深入),57,不同搜索策略的比较,广度优先是完备和最优的，但空间复杂度高 深度优先空间的效率很高，但既不是完备的也不是最优的 迭代深入是完备和最优的，其空间复杂度与深度优先一样，时间复杂度则几乎与广度优先相同,58,状态重复访问,59,避免状态重复访问,需要进行状态的比较 广度优先搜索: 把所生成的节点相应的状态都保存在VISITED 如果一个新生成的节点的状态已经在VISITED中，则抛弃该节点,60,深度优先搜索: 解决方法 1: 把当前路径中的节点相应的状态保存在VISITED 如果一个新生成的节点的状态已经在VISITED中，则抛弃该节点 仅为了避免死循环 Solution 2: 把所

19、有生成的节点的相应状态保存在VISITED 如果一个新生成的节点的状态已经在VISITED中，则抛弃该节点 空间复杂度与广度优先相同！,避免状态重复访问,61,代价一致搜索Uniform-Cost Search,Each arc has some cost c 0 The cost of the path to each fringe node N is g(N) = costs of arcs The goal is to generate a solution path of minimal cost The nodes N in the queue FRINGE are sorted in increasing g(N) Need to modify search algorithm,62,Search Algorithm #2,SEARCH#2 INSERT(initial-node,FRINGE) Repeat: If empty(FRINGE) then return failure N REMOVE(FRINGE) s STATE(N) If GOAL?(s) then return