Please enable JavaScript.
Coggle requires JavaScript to display documents.
Informed Search Strategies
Uses problem-specific knowledge beyond the
…
Informed Search Strategies
Uses problem-specific knowledge beyond the
definition of the problem itself. The informed search algorithm is more useful for large search space.
Heuristic Function h(n)
:heavy_check_mark: Heuristic is a function which is used in Informed Search, and it finds the most promising path
:heavy_check_mark: How to determine a good h(n) : need
Experience over the problem
:heavy_check_mark: Trade-off: Evaluation of h(n) has a cost though it provide saving to the search time
Greedy Best First Search
:memo: Always selects the path which appears best at that moment. It is the combination of depth-first search and breadth-first search algorithms
- Evaluates nodes by using just the heuristic
function; that is, f(n) = h(n)
- Optimal? No
- Complete? No, even in a finite state space
- The graph search version is complete in finite
spaces, but not in infinite ones
A* Search
- The most widely known form of best-first search -
pronounced “A-star search”
- Evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal
- Optimal? Yes
- Complete? Yes
- The algorithm is identical to UNIFORM-COST-SEARCH
except that A* uses g + h instead of g
Example: 8-Puzzle
- g(n) – actual distance from the initial state to
the node n
- h(n)- Number of tiles out of place in state n
when compared to goal state
- f(n) = g(n)+h(n)
:check: Admissible Heuristic
~ never overestimates the cost to reach the goal
:check: Consistency
~ h(n) ≤ c(n, a, n’) + h(n’)
:check: Optimality of A*
~ the tree-search version of A is optimal if h(n) is
admissible
~ the graph-search version is optimal if h(n) is consistent
:check: All consistent heuristics are admissible but the
converse is not true
Local Search
Algorithm
- Operate using a single current node (rather than multiple paths) and generally move only to neighbors
of that node.
- Typically, the paths followed by the search are not
retained
Hill Climbing
:ballot_box_with_check: Moves in the direction of increasing value (uphill)
:ballot_box_with_check: Terminates when reaches a peak where no neighbor
has a higher value
-
-
Stochastic Hill
Climbing
:heavy_check_mark:Choose next move randomly from among
uphill moves
:heavy_check_mark: Probability of selection may vary with the
steepness of uphill move