# HSM

Published on March 19, 2009

Author: ankush85

Source: authorstream.com

Heuristic Search Methods : Heuristic Search Methods Methods that use a heuristic function to provide specific knowledge about the problem: Heuristic Functions Hill climbing Beam search Hill climbing (2) Greedy search Heuristic Functions : 2 Heuristic Functions To further improve the quality of the previous methods, we need to include problem-specific knowledge on the problem. How to do this in such a way that the algorithms remain generally applicable ??? Examples (1): : 3 Examples (1): Imagine the problem of finding a route on a road map and that the NET below is the road map: Examples (2): 8-puzzle : 4 Examples (2): 8-puzzle f1(T) = the number correctly placed tiles on the board: Most often, ‘distance to goal’ heuristics are more useful ! Examples (3):Manhattan distance : 5 Examples (3):Manhattan distance f3(T) = the sum of ( the horizontal + vertical distance that each tile is away from its final destination): gives a better estimate of distance from the goal node = 1 + 4 + 2 + 3 = 10 Examples (4):Chess: : 6 Examples (4):Chess: F(T) = (Value count of black pieces) - (Value count of white pieces) f Hill climbing : Hill climbing A basic heuristic search method: depth-first + heuristic Hill climbing_1 : 8 Hill climbing_1 Perform depth-first, BUT: instead of left-to-right selection, FIRST select the child with the best heuristic value Example: using the straight-line distance: 8.9 10.4 10.4 6.9 6.7 3.0 Hill climbing_1 algorithm: : 9 Hill climbing_1 algorithm: 1. QUEUE <-- path only containing the root; 2. WHILE QUEUE is not empty AND goal is not reached DO remove the first path from the QUEUE; create new paths (to all children); reject the new paths with loops; sort new paths (HEURISTIC) ; add the new paths to front of QUEUE; 3. IF goal reached THEN success; ELSE failure; Beam search : Beam search Narrowing the width of the breadth-first search Beam search (1): : 11 Beam search (1): Assume a pre-fixed WIDTH (example : 2 ) Perform breadth-first, BUT: Only keep the WIDTH best new nodes depending on heuristic at each new level. Beam search (2): : 12 Beam search (2): Optimi-zation: ignore leafs that are not goal nodes (see C) Beam search algorithm: : 13 Beam search algorithm: See exercises! Properties: Completeness: Hill climbing: YES (backtracking), Beam search: NO Speed/Memory: Hill climbing: same as Depth-first (in worst case) Beam search: QUEUE always has length WIDTH, so memory usage is constant = WIDTH, time is of the order of WIDTH*m*b or WIDTH*d*b if no solution is found Hill climbing_2 : 14 Hill climbing_2 == Beam search with a width of 1. Inspiring Example: climbing a hill in the fog. Heuristic function: check the change in altitude in 4 directions: the strongest increase is the direction in which to move next. Is identical to Hill climbing_1, except for dropping the backtracking. Produces a number of classical problems: Problems with Hill climbing_2: : 15 Problems with Hill climbing_2: Comments: : 16 Comments: Foothills are local minima: hill climbing_2 can’t detect the difference. Plateaus don’t allow you to progress in any direction. Foothills and plateaus require random jumps to be combined with the hill climbing algorithm. Ridges neither: the directions you have fixed in advance all move downwards for this surface. Ridges require new rules, more directly targeted to the goal, to be introduced (new directions to move) . Local search : 17 Local search Hill climbing_2 is an example of local search. In local search, we only keep track of 1 path and use it to compute a new path in the next step. QUEUE is always of the form: ( p) Another example: MINIMAL COST search: If p is the current path: the next path extends p by adding the node with the smallest cost from the endpoint of p Greedy search : Greedy search Always expand the heuristically best nodes first. Greedy search, orHeuristic best-first search: : 19 Greedy search, orHeuristic best-first search: At each step, select the node with the best (in this case: lowest) heuristic value. Greedy search algorithm: : 20 Greedy search algorithm: 1. QUEUE <-- path only containing the root; 2. WHILE QUEUE is not empty AND goal is not reached DO remove the first path from the QUEUE; create new paths (to all children); reject the new paths with loops; add the new paths and sort the entire QUEUE; 3. IF goal reached THEN success; ELSE failure;

03. 04. 2009
0 views

06. 03. 2009
0 views

27. 03. 2009
0 views

20. 11. 2009
0 views

22. 11. 2009
0 views

14. 07. 2009
0 views

18. 03. 2009
0 views

08. 04. 2009
0 views

06. 03. 2009
0 views

20. 04. 2009
0 views

03. 06. 2013
0 views

03. 06. 2013
0 views

16. 10. 2012
0 views

25. 09. 2012
0 views

25. 09. 2012
0 views

03. 01. 2012
0 views

24. 11. 2009
0 views

22. 11. 2009
0 views

22. 11. 2009
0 views

16. 05. 2009
0 views

19. 04. 2009
0 views

16. 05. 2009
0 views

10. 07. 2009
0 views

01. 07. 2009
0 views

21. 07. 2009
0 views

21. 07. 2009
0 views

01. 07. 2009
0 views

05. 03. 2009
0 views

13. 06. 2009
0 views

11. 05. 2009
0 views

05. 03. 2009
0 views

06. 03. 2009
0 views

25. 08. 2009
0 views

19. 06. 2009
0 views

24. 06. 2009
0 views

02. 10. 2008
0 views

25. 04. 2009
0 views

28. 04. 2009
0 views

17. 06. 2009
0 views

25. 04. 2009
0 views

25. 06. 2009
0 views

19. 06. 2009
0 views

18. 03. 2009
0 views

27. 04. 2009
0 views

23. 03. 2009
0 views

23. 05. 2009
0 views

23. 05. 2009
0 views

24. 06. 2009
0 views

24. 05. 2009
0 views

03. 04. 2009
0 views

08. 04. 2009
0 views

23. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

29. 04. 2009
0 views

24. 05. 2009
0 views

06. 03. 2009
0 views

11. 04. 2009
0 views

08. 03. 2009
0 views

13. 03. 2009
0 views

04. 09. 2009
0 views

20. 11. 2009
0 views

22. 11. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

21. 04. 2009
0 views

25. 05. 2009
0 views

06. 03. 2009
0 views

05. 03. 2009
0 views

14. 07. 2009
0 views

14. 07. 2009
0 views

05. 03. 2009
0 views

09. 05. 2009
0 views

05. 03. 2009
0 views

05. 03. 2009
0 views

05. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

09. 03. 2009
0 views

09. 03. 2009
0 views

13. 03. 2009
0 views

25. 03. 2009
0 views

08. 04. 2009
0 views

10. 04. 2009
0 views

10. 04. 2009
0 views

13. 04. 2009
0 views

15. 04. 2009
0 views

17. 04. 2009
0 views

23. 04. 2009
0 views

21. 04. 2009
0 views

21. 04. 2009
0 views

21. 04. 2009
0 views

23. 04. 2009
0 views

25. 04. 2009
0 views

25. 04. 2009
0 views

29. 04. 2009
0 views

29. 04. 2009
0 views

26. 04. 2009
0 views

26. 04. 2009
0 views

27. 04. 2009
0 views

05. 05. 2009
0 views

14. 05. 2009
0 views

16. 05. 2009
0 views

15. 05. 2009
0 views

15. 05. 2009
0 views

23. 04. 2009
0 views

23. 05. 2009
0 views

23. 05. 2009
0 views

24. 05. 2009
0 views

28. 05. 2009
0 views

04. 06. 2009
0 views

19. 06. 2009
0 views

19. 06. 2009
0 views

07. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

15. 06. 2009
0 views

26. 06. 2009
0 views

27. 06. 2009
0 views

01. 07. 2009
0 views

06. 07. 2009
0 views

05. 07. 2009
0 views

05. 07. 2009
0 views

10. 07. 2009
0 views

01. 08. 2009
0 views

26. 04. 2009
0 views

21. 08. 2009
0 views

25. 08. 2009
0 views

27. 08. 2009
0 views

27. 08. 2009
0 views

27. 08. 2009
0 views

04. 09. 2009
0 views

04. 09. 2009
0 views

27. 06. 2009
0 views