inedSearch.ppt

1、Problem-solving and Search,Informed Search,Introduction,we have looked at different blind search strategies Uninformed search methods lack problem-specific knowledge inefficient in many cases But, if we know about the problem we are solving, we can be even cleverer Using problem-specific knowledge c

2、an dramatically improve the search speed informed search algorithms use problem specific heuristics(启发式信息),Review of different Search Strategies,Blind Search(Uninformed) Depth first search Breadth first search Iterative deepening search Informed Search Heuristic search(启发式搜索),General Graph Search Al

3、gorithm,Let fringe be a list containing the initial state Let closed be initially empty Loop if fringe is empty return failure Noderemove-first (fringe) if Node is a goal then return the path from initial state to Node else put Node in closed generate all successors of Node S for all nodes m in S if

4、 m is not in fringe or closed merge m into fringe End Loop,Cost as True Distance,Review of Uniform-Cost Search,in uniform cost search we enqueue nodes by path cost Let g(n) = cost of the path from the start node to the current node n. The algorithm sorts nodes by increasing value of g, and expands t

5、he lowest cost node of the fringe,Informed Search,Also called heuristic search Use problem specific knowledge (heuristic information) May be more efficient At the heart of such algorithms there is the concept of a heuristic function The heuristic will be used to select the order of node expansion.,H

6、euristics,Heuristic means “rule of thumb” Heuristics are criteria, methods or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal In heuristic search heuristics are used to identify the most promising search path,H

7、euristic Function,A heuristic function at a node n is an estimate of the optimum cost from the current node to a goal. It is denoted by h(n). h(n) = estimated cost of the cheapest path from node n to a goal node If n is goal then h(n)=0,Romania with step costs in km,hSLD=straight-line distance heuri

8、stic. hSLD can NOT be computed from the problem description itself,Best First Search,Uniform Cost Search is a special case of the best first search algorithm The algorithm maintains a priority queue of nodes to be explored. A cost function f(n) is applied to each node, which called evaluation functi

9、on(估价函数) The nodes are put in OPEN in the order of their f values Nodes with smaller f(n) values are expanded earlier,Best First Search (Tree Search),Let fringe be a priority queue containing the initial state Loop if fringe is empty return failure Noderemove-first (fringe) if Node is a goal then re

10、turn the path from initial state to Node else generate all successors of Node, and put the newly generated nodes into fringe according to their f values End Loop,different ways of defining the function f. This leads to different search algorithms.,Evaluation Function (Cost Function),different ways o

11、f defining the function f. This leads to different search algorithms f(n)=g(n)uniform cost algorithm f(n)=h(n)greedy algorithm f(n)=g(n)+h(n)A algorithm,Greedy Search,In greedy search, the idea is to expand the node with the smallest estimated cost to reach the goal. We use a heuristic function f(n)

12、 = h(n) h(n) estimates the distance remaining to a goal,Greedy search example,Greedy search example,f(n)=h(n),Greedy search example,Assume that we want to use greedy search to solve the problem of travelling from Arad to Bucharest. The initial state=Arad,Arad (366),Greedy search example,The first ex

13、pansion step produces: Sibiu, Timisoara and Zerind Greedy best-first will select Sibiu.,Arad,Sibiu(253),Timisoara (329),Zerind(374),Greedy search example,If Sibiu is expanded we get: Arad, Fagaras, Oradea and Rimnicu Vilcea Greedy best-first search will select: Fagaras,Arad,Sibiu,Arad (366),Fagaras

14、(176),Oradea (380),Rimnicu Vilcea (193),Greedy search example,If Fagaras is expanded we get: Sibiu and Bucharest Goal reached ! Yet not optimal (see Arad, Sibiu, Rimnicu Vilcea, Pitesti),Arad,Sibiu,Fagaras,Sibiu (253),Bucharest (0),Greedy search, evaluation,often perform very well They tend to find

15、good solutions quickly not always optimal ones.,Greedy search, evaluation,Completeness: NO Check on repeated states Minimizing h(n) can result in false starts, e.g. Iasi to Fagaras.,Greedy search, evaluation,Completeness: NO (cfr. DF-search) Time complexity? Cfr. Worst-case DF-search (with m is maxi

16、mum depth of search space) Good heuristic can give dramatic improvement.,Greedy search, evaluation,Completeness: NO (cfr. DF-search) Time complexity: Space complexity: Keeps all nodes in memory,Greedy search, evaluation,Completeness: NO (cfr. DF-search) Time complexity: Space complexity: Optimality?

17、 NO Same as DF-search,A search,Best-known form of best-first search. Idea: avoid expanding paths that are already expensive. Evaluation function: f(n) = g(n) + h(n) g(n) the cost (so far) to reach the node. h(n) estimated cost to get from the node to the goal. f(n) estimated total cost of path throu

18、gh n to goal.,A* search,A with an admissible(可纳的) heuristic is known as A*. A heuristic is admissible if it never overestimates the cost to reach the goal Are optimistic Formally: 1. h(n) = 0 so h(G)=0 for any goal G. e.g. hSLD(n) never overestimates the actual road distance,Romania example,A* searc

19、h example,Find Bucharest starting at Arad f(Arad) = c(?,Arad)+h(Arad)=0+366=366,A* search example,Expand Arrad and determine f(n) for each node f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393 f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447 f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449 Best choic

20、e is Sibiu,A* search example,Expand Sibiu and determine f(n) for each node f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646 f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415 f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671 f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413 Best choice

21、 is Rimnicu Vilcea,A* search example,Expand Rimnicu Vilcea and determine f(n) for each node f(Craiova)=c(Rimnicu Vilcea, Craiova)+h(Craiova)=360+160=526 f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417 f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553 Best choice is Fagaras,A* search

22、 example,Expand Fagaras and determine f(n) for each node f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591 f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450 Best choice is Pitesti !,A* search example,Expand Pitesti and determine f(n) for each node f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=

23、418+0=418 Best choice is Bucharest ! Optimal solution (only if h(n) is admissable),Optimality of A*(standard proof),Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. f(G2)=g(G2)g(

24、G)=f(G) since h(G2)=h(G)= 0 and G2 is suboptimal h(n) h*(n)since h is admissible g(n) + h*(n)=f(G) sine n is on a shortest path to an optimal goal G f(n)=g(n) + h(n) f(G) f(G2) from above A* will never select G2 for expansion,BUT graph search,Discards new paths to repeated state. Previous proof brea

25、ks down Solution: Add extra bookkeeping i.e. remove more expensive of two paths. Ensure that optimal path to any repeated state is always first followed. Extra requirement on h(n): consistency(一致性) (monotonicity单调性),A* Search ( Graphic Search),Consistency(一致性),A heuristic is consistent if for every

26、node n, every successor n of n generated by any action a, Then h(n) c(n,a,n) + h(n) If h is consistent, we have f(n) = g(n) + h(n) = g(n) + c(n,a,n) + h(n) g(n) + h(n) = f(n) i.e., f(n) is non-decreasing(非递减) along any path. Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal,Algorithm

27、A* Demo,f(n)=g(n)+h(n) g(n): the depth of n h(n): number of misplaced tiles,Goal state,Intial state,4,5,6,3,1+3,1+5,1+5,2+4,2+3,2+3,3+2,3+4,3+3,3+4,4+1,5+0,5+2,2,Algorithm A* Demo,Path planning in a grid map,A* search, evaluation,Completeness: YES Time complexity: (exponential with path length) Spac

28、e complexity:(all nodes are stored) Optimality: YES Cannot expand fi+1 until fi is finished. A* expands all nodes with f(n)C* Also optimally efficient,Two 8-puzzle Heuristics,f(n)=g(n)+h(n) h1(n): total tiles out of place h2(n): total Manhattan distance to goal position Manhattan distances: d(i，j)=|

29、xi-xj|+|yi-yj| Is this h2 (n) admissible? Use A* search, and draw up the search tree, write down the f(n) of expanded node.,Goal state,Intial state,YES,3,4,5,1+4,1+6,1+6,2+5,2+5,2+3,3+2,3+4,4+1,5+0,5+2,0+5,2,Dominance(占优),If h2(n) h1(n) for all n (both admissible) then h2 dominates h1 h2 is better f

30、or search Typical search costs (average number of nodes expanded): d=12 IDS = 3,644,035 nodes (ITERATIVE-DEEPENING-SEARCH) A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes,How to design heuristic function,Most important in A* The cost of an op

31、timal solution to a relaxed problem (松弛问题) is an admissible heuristic for the original problem A problem with fewer restrictions on the actions is called a relaxed problem,Simple Maze,Relaxation in Maze Move from (x,y) to (x,y) is illegal If |x-x| 1 Or |y-y| 1 Or (x,y) contains a wall Otherwise, its

32、 legal.,Relaxations Admissible,Why does this work? Any legal path in the full problem is still legal in the relaxation. Therefore, the optimal solution to the relaxation must be no longer than the optimal solution to the full problem.,Tile move from (x,y) to (x,y) is illegal If |x-x| 1 or |y-y| 1 Or

33、 (|x-x| 0 and |y-y| 0) Or (x,y) contains a tile Otherwise, its legal,Relaxation in 8-puzzle,h1(s): total tiles out of place If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution h2(s): total Manhattan distance If the rules are relaxed so th

34、at a tile can move to any adjacent square, then h2(n) gives the shortest solution,Two 8-puzzle Heuristics,h1(s): total tiles out of place h2(s): total Manhattan distance Note: h1(s) h2(s), so the latter leads to more efficient search Easy to compute and provides useful guidance,Memory-bounded heuris

35、tic search,Some solutions to A* space problems (maintain completeness and optimality) Iterative-deepening A* (IDA*) Here cutoff information is the f-cost (g+h) instead of depth Recursive best-first search(RBFS) Recursive algorithm that attempts to mimic standard best-first search with linear space.

36、(simple) Memory-bounded A* (S)MA*) Drop the worst-leaf node when memory is full,Recursive best-first search,function RECURSIVE-BEST-FIRST-SEARCH(problem) return a solution or failure return RFBS(problem,MAKE-NODE(INITIAL-STATEproblem),) function RFBS( problem, node, f_limit) return a solution or fai

37、lure and a new f-cost limit if GOAL-TESTproblem(STATEnode) then return node successors EXPAND(node, problem) if successors is empty then return failure, for each s in successors do f s max(g(s) + h(s), f node) repeat best the lowest f-value node in successors if f best f_limit then return failure, f

38、 best alternative the second lowest f-value among successors result, f best RBFS(problem, best, min(f_limit, alternative) if result failure then return result,Recursive best-first search,Keeps track of the f-value of the best-alternative path available. If current f-values exceeds this alternative f

39、-value than backtrack to alternative path. Upon backtracking change f-value to best f-value of its children. Re-expansion of this result is thus still possible.,Recursive best-first search, ex.,Path until Rumnicu Vilcea is already expanded Above node; f-limit for every recursive call is shown on top

40、. Below node: f(n) The path is followed until Pitesti which has a f-value worse than the f-limit.,Recursive best-first search, ex.,Unwind recursion and store best f-value for current best leaf Pitesti result, f best RBFS(problem, best, min(f_limit, alternative) best is now Fagaras. Call RBFS for new

41、 best best value is now 450,Recursive best-first search, ex.,Unwind recursion and store best f-value for current best leaf Fagaras result, f best RBFS(problem, best, min(f_limit, alternative) best is now Rimnicu Viclea (again). Call RBFS for new best Subtree is again expanded. Best alternative subtr

42、ee is now through Timisoara. Solution is found since because 447 417.,RBFS evaluation,RBFS is a bit more efficient than IDA* Still excessive node generation (mind changes) Like A*, optimal if h(n) is admissible Space complexity is O(bd). IDA* retains only one single number (the current f-cost limit)

43、 Time complexity difficult to characterize Depends on accuracy if h(n) and how often best path changes. IDA* en RBFS suffer from too little memory.,(simplified) memory-bounded A*,Use all available memory. I.e. expand best leafs until available memory is full When full, SMA* drops worst leaf node (hi

44、ghest f-value) Like RFBS backup forgotten node to its parent What if all leafs have the same f-value? Same node could be selected for expansion and deletion. SMA* solves this by expanding newest best leaf and deleting oldest worst leaf. SMA* is complete if solution is reachable, optimal if optimal s

45、olution is reachable.,Exercises: Moving block,Initial state Goal state Moving rule If a block moving into blank, cost=1 If a block cross over 1 block, cost=1 If a block cross over 2 block, cost=2 Evaluation function Heuristic h(n)=the number of B block on the left side of each W bock h value of initial state is 9 g(n)=cost of path from start to n Use A*, draw up a search tree with depth 4,Local Search,Local search methods work on complete state formulations. They keep only a small number of nodes in memory. Local search is useful for solving optimization problems: