Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **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(b^{m}),
but a good heuristic can give dramatic improvement**

•
__Space?__** O(b^{m})
-- keeps all nodes in memory**

•
__Optimal?__** No**

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

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