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.
There are various algorithms to find route-problems.
-Breadth Search First
- Depth Search First
- Uniform-cost search methos
- Best Search Method
- Greedy Search
- A* search
Other popular search techniques:
-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.
Coming up with a good heuristic is a challenging
-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
- 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
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.
-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.
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)