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 route-problems.

UNINFORMED SEARCH

-Breadth Search First
- Depth Search First
- Uniform-cost 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?

- 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 average-case 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 8-puzzle 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 n-Queens problem ( and the challenge here is to put those queens in the chess board such that one is not a threat to another)