PPT_Aritifical_Intelligence_Chapter3.pptx

PPT_Aritifical_Intelligence_Chapter3.pptx

1. Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 2 Chapter 3 Heuristic Search

2. Heuristic Functions The Heuristic Function is used for estimation of the distance to the goal. Hence the function h(n) can be used to decide which node should be picked from OPEN. These functions can not be expensive in computational terms because the whole idea is focused on to minimize the computational cost of the search algorithm. Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 3

3. Best First Search This algorithm is same as Depth First Search but a small change is there. A sorted OPEN list is maintained here due to which automatically the node with the best heuristic value comes to the head of the list. In the entire algorithm, only one line needs to be replaced : OPEN  append (NEW, tail(OPEN)) with OPEN  sort h (append (NEW, tail(OPEN))) If someone wants to include the heuristic value then he has to make required changes in the search node representation.

4. The given figure is an example that Shows there is a sense of direction in the Best First Search but there is a chance to hit a dead end also. It’s a city map where two dimensional grid has junctions located on it. Manhattan distance is used in this search as the estimate of the distance. Heuristic function doesn’t have idea of the entire roadmap, only a sense of direction is there. 5 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited Best First Search (contd.)

5. Completeness For finite domains we can say Best first Search is complete. Ordering of OPEN is the only place where we are making changes. The failure will be reported only when OPEN will be empty. Main thing is that Best First Search is a systematic approach because it will not give up until all nodes are covered. Time Complexity Also dependent on the accuracy of the heuristic function. Effective branching factor = Total-nodes-expanded / nodes-in-the-solution 6 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited Best First Search (contd.)

6. Space Complexity Search frontier is an indication of space requirement 7 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited

7. In this figure, we can see that Best First Search choosing a solution consists of Five moves. 8 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited Quality of Solution

8. Hill Climbing – Local Search Algorithm It’s a Change of termination criterion Local Search – Just by not storing OPEN Hill Climbing has actually burnt its bridges. 9 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited

9. It mainly focuses on the local neighbours of a particular node. That is why the space requirements are constant. It only moves to a better node and it also terminates if it can’t. So here we can say the time complexity is linear. In hill climbing the termination criterion is also different. When there is no better neighbour available then it stops. Here the problem is treated as an optimisation problem. However, we can say that it is not complete and also cannot find the global optimum for the solution. Hill Climbing – A Constant Space Algorithm 10 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited

10. Steepest Gradient Ascent Hill climbing for a maximization problem 11 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited

11. Ending at a Local Maximum 12 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited

12. Local Maxima – Blocks World Problem These are two Heuristic Functions : H1 : Adding 1 for every block, i.e., on the correct block or table ( h1 start = 2, h1 goal =6) subtract 1 for every block on a wrong table or block H2 : Adding n if the block will be on correct structure of n blocks(h2 start= –1, h2 goal = 10) subtract n if block is on the wrong structure of n blocks It’s a maximization problem Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 13

13. 4 Moves From the Start State From the figure Which Move is best as per h1? Here h1 thinks that movement of the h1 to the state q is best idea because block A is on Block E in that state. h1(S) = (–1) + 1 + 1 + 1 + (–1) + 1 = 2 h1(P) = (–1) + 1 + 1 + 1 + (–1) + 1 = 2 h1(Q) = 1 + 1 + 1 + 1 + (–1) + 1 = 4 h1(R) = (–1) + 1 + 1 + 1 + (–1) + 1 = 2 h1(T) = (–1) + 1 + 1 + 1 + (–1) + 1 = 2 where, h1(n) = valA + valB + valC + valD + valE + valF Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 14

14. The choice from the state Q actually are worse as comparison to Q From H1’s idea and perspective Q is the maximum h1(Q) = 1 + 1 + 1 + 1 + (–1) + 1 = 4 h1(P) = (–1) + 1 + 1 + 1 + (–1) + 1 = 2 h1(S) = (–1) + 1 + 1 + 1 + (–1) + 1 = 2 h1(U) = 1 + (–1) + 1 + 1 + (–1) + 1 = 2 h1(V) = 1 + (–1) + 1 + 1 + (–1) + 1 = 2 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 15

15. 4 Moves from Starting State Which move as per h2 is best ? h2(S) = (–3) + 2 + 1 + 0 + (–1) + 0 = –1 h2(G) = 4 + 2 + 1 + 0 + 3 + 0 = 10 h2(P) = 0 + 2 + 1 + 0 + (–1) + 0 = 2 h2(Q) = (–2) + 2 + 1 + 0 + (–1) + 0 = 0 h2(R) = (–3) + 2 + 1 + 0 + (–4) + 0 = – 4 h2(T) = (–3) + 2 + 1 + 0 + 0 + 0 = 0 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 16

16. H2 is more discriminative and also drives HC to the correct move h2(P) = 0 + 2 + 1 + 0 + (–1) + 0 = 2 h2(S) = (–3) + 2 + 1 + 0 + (–1) + 0 = –1 h2(Q) = (–2) + 2 + 1 + 0 + (–1) + 0 = 0 h2(W) = 0 + 2 + 1 + 0 + (–1) + 0 = 2 h2(X) = 0 + 2 + 1 + 0 + 3 + 0 = 6 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 17

17. Graph to show how terrain is defined by heuristic function Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 18

18. Solution Space Search The Space of candidate solution is also called as Solution space. By applying some perturbation to the particular candidate, the local search method creates the candidate’s neighbours. MoveGen Function = Neighbourhood function 2 to the power N candidates are there in SAT problem with N variables (each candidate is N bit strong) N = 7, neighbourhood function can change by one bit. For 01010, they are: 10010, 11110, 11000, 11011, 00110, 00000, 00011, 01100, 01110, and 01001. Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 19

19. Variable Neighbourhood Descent VariableNeighbourhoodDescent() 1 node  start 2 for i  1 to n 3 do moveGen  MoveGen(i) 4 node  HillClimbing(node, moveGen) 5 return node FIGURE shows Algorithm Variable Neighbourhood Descent This algorithm is assuming that the function MoveGen can be passed like a parameter. It is also assuming that N MoveGen functions are there that are sorted as per the density of the produced neighbourhood. The entire hope is: Climbing will be done with sparser neighbourhood functions. Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 20

20. Beam Search At each level, you have to look at more than one option. You should look at best b option for a beam with width b. Beam search with beam width = 2 Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 21

21. Beam Search For SAT Beam search width = 2 fails to solve SAT problem starting 1111. The solution should be reached din 3 steps when you are starting with value 3 because it’s hill climbing. The node that is marked with * leads to a perfect solution in 3 steps. H(n) = Number of clauses satisfied (b ∨ ~c) ^ (c ∨ ~d) ^ (~b) ^ (~a ∨ ~e) ^ (e ∨ ~c) ^ (~c ∨ ~d) Chapter 3 Copyright © 2013 by McGraw Hill Education (India) Private Limited 22