CS) Informative
Maps on PDA-phones Chui Pui Ling Page 18 from a non-goal state. While just finding a path is not enough, informed search strategy is introduced. Informed strategy uses problem-specific knowledge beyond the definition of the problem itself which can find solutions more efficiently. An evaluate function f(n) is usually applied in the searching process to select the node to be explored. f(n) = g(n) + h(n)
n represents the current node, g(n) is the path cost so far from the Start node to the current node n h(n) is the estimated cost of the shortest path from n to Goal node
2.3.3. Hill-Climbing Search Hill-climbing search or greedy local search tries to expand the node that is closest to the goal each time. So, it evaluates nodes by only considering the heuristic function f(n) = h(n) and typically ignore g(n). By doing so, the local best node would always be chosen.
Nonetheless, hill-climbing often gets stuck for the following reasons (Figure 10 [14])
- Local maxima: a local maximum is a peak that is higher than its neighboring states but lower than the global maximum. It will mistake the local maximum as the global one.
- Ridges:ridges result in a sequence of local maxima that is very difficult for greedy alforithms to navigate.
- Plateaux:a plateau is an area of the state space landscape where the evaluation function is flat. It can be a flat local maximum or a shoulder. Thus, the optimality is not guarantee.
CS) Informative Maps on PDA-phones
Chui Pui Ling Page 19
Share with your friends: 
