QUICK QUESTION:
Suppose you are traveling from A to Z. You just realized that you have already biked for 10
miles.Now that you are
at N, you decided to take a little break.
There are THREE ways to go to your destination. The signpost
says:
5 miles to P ( from P it is 29 miles to Z)
2 miles to R ( from R it is 30 miles to Z)
7 miles to S ( from S it is 26 miles to Z)
What would you like to do?
What would Greedy Search suggest you to do?
We will get back to the answer in a little bit.
Approach:
There are various algorithms to find
routeproblems.
UNINFORMED SEARCH
Breadth Search First
 Depth Search First
 Uniformcost search methos


INFORMED SEARCH
 Best Search Method
 Greedy Search
 A* search
Other popular search techniques:
Simulated Annealing
Hill Climbing
WHY BOTHER?
ISSUES:
Inherently difficult problem: Traveling SalesMan Problem
unable to find the solution within practical time and
space limits
 the goal is to find good solution instead of the BEST
solution within reasonable time and space.
 use current information to predict what path is closer
to the goal and follow it,although it does not guarantee to find the best
path.
Greedy Search is one of the informed Search methods.
 chooses the best frontier node to expand next
How exactly is it achieved?
The applet above allows you to explore the algorithm.
 We know the start node, and goal node
 Choose the node that is near to the goal node
While doing so, we can estimate the distance to goal,
and this estimate is called the HEURISTIC FUNCTION, called h(n),
estimated cost of path from node to the goal.
 So when h(n) = 0, n is a goal node.
ISSUES:
Coming up with a good heuristic is a challenging
task
the better the heuristic function, the better the resulting
search method will be
Okay lets get into the nitty gritty:
Goal here is to expand the frontier node that minimizes
h(n)
 Basically this algorithm works with GREED, hence the
name.
Just grab any opportunity as soon as you can whenever
you get
With this in mind, algorithm chooses the path for exploration
based upon the strategy of pick the one with minimal heuristic value, minimum
f(n) = h(n) value.
With this heuristics function, Greedy Search uses the
estimated cost from a node to the goal to determine it desirability.
Usually, heuristics improves averagecase performance
Time to get back to the question:
Demonstrate with the nodes: picking the next node and
expanding
....
Java demonstration
for simplicity, say, the cost function from one node to another node is 1.
For the route finding problem, a good heuristic
would be straight line distance to the goal, as the crow flies.
Usually, Greedy algorithms perform very well.
Caveats:
tend to find good solutions quickly, although not always
optimal ones
 they could get into a loop, so they are not complete
 they are not admissible; sometimes heuristics may underestimate
 if there are too many nodes, the search could be exponential
what can be done to better the search process?
To better the search process, we can have states with weights, and use this information to make the search process efficient. Actually A* search uses this techique. Greedy search is used for small problems to have quick answers.
Examples:
Some examples could be solving a 8puzzle
where the heuristics is the Manhattan distance. Also, a robot going from
point A to point B while testing in the lab could use this algorithm to
determine how resonably it is working. another interesting problem would
be in the use of nQueens problem ( and the challenge here is to put those queens in the chess board such that one is not a threat to another)