Greedy solution (non-complete) to find the shortest path to a target node
Algorithm:
Priority is computed using the evaluation function: f(n) = h where h is an heuristic (local cost to visit a node)
Algorithm paradigm of making the locally optimal choice at each stage using a heuristic function
A locally optimal function does not necesseraly mean to not have a global context for taking a decision
Never reconsider a choice (main difference with dynamic programming)
Solution found may not be the most optimal one
Often, the global context is spread into a priority queue
Identify an optimal subproblem or substructure in the problem and determine how to reach it
Focus on what you have now (don’t think about what comes next)
We may want to apply the traversal technique to have a global context for the identification part (a map of letters/positions etc.)
Greedy technique