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

Artificial Intelligence : Heuristics / Informed Search Strategies |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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