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
• h(n) = 0, if n is the goal node
· 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
A best first search that uses to select next node to expand is called greedy search.
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
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.