Heuristics / Informed Search Strategies

HEURISTICS / INFORMED SEARCH STRATEGIES:

Heuristic / Informed

It uses additional information about nodes (heuristics) that have not yet been explored to decide which nodes to examine next

·                Use problem specific knowledge

·                Can find solutions more efficiently than search strategies that do not use domain specific knowledge.

·                find solutions even when there is limited time available

General approach of informed search:

·           Best-first search: node is selected for expansion based on an evaluation function f(n)

Idea: evaluation function measures distance to the goal.

*                                                   Choose node which appears best

•                            Best First Search algorithms differs in the evaluation function

– Evaluation function incorporate the problem specific knowledge in the form of h(n)

– h(n) , heuristic function , a component of f(n), Estimated cost of cheapest path to the

goal node

•                             h(n) = 0, if n is the goal node

Implementation:

·                             fringe is queue sorted in decreasing order of desirability.

·                                  Special cases: greedy search, A* search

GREEDY BEST-FIRST SEARCH

•                    Expands the node that is closest to the goal

•                    Consider route finding problem in Romania

–  Use of hSLD, Straight Line Distance Heuristic

–  Evaluation function f(n) = h(n) (heuristic), estimate of cost from n to goal

Definition:

A best first search that uses to select next node to expand is called greedy search.

Ex:

Given,

Solution:

From the given graph and estimated cost the goal state is estimated as B from A. Apply the evaluation function h(n) to find a path from A to B.

From F goal state B is reached. Therefore the path from A to B using greedy search is A-S-F-B

= 450(i.e.) (140+99+211).or the problem of finding route from Arad to Burcharest...

GREEDY SEARCH, EVALUATION:

·                                Completeness: NO (cfr. DF-search)

-Check on repeated states

-Minimizing h(n) can result in false starts, e.g. Iasi to Fagaras.

Properties of greedy best-first search:

•        Complete? No – can get stuck in loops, e.g., Iasi        Neamt  - Iasi - Neamt -

•                      Time? O(b^m), but a good heuristic can give dramatic improvement

•                      Space? O(b^m) -- keeps all nodes in memory

•                      Optimal? No