Home | | Artificial Intelligence | Heuristics / Informed Search Strategies

Chapter: Artificial Intelligence

Heuristics / Informed Search Strategies

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

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(bm), but a good heuristic can give dramatic improvement

 

•                      Space? O(bm) -- keeps all nodes in memory

 

•                      Optimal? No

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Artificial Intelligence : Heuristics / Informed Search Strategies |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.