Greedy Algorithm

Description:

• In all the current node, expand the node that has the lowest heuristic
• Worst case: it can be a badly-guided DFS
• Used for finding:
  • Minimum Spanning Tree
  • Dijkstra’s Shortest Path Algorithm
  • Travelling Salesman Problem
  • Huffman Coding

Few examples:

• Coin Changing Problem
• Interval Scheduling Problem
• Interval Partitioning Problem
• Minimize Lateness Problem