EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Machine Learning Tutorial What is a Greedy Algorithm?
Secondary Sidebar
Machine Learning Tutorial
  • Algorithms
    • Machine Learning Algorithms
    • Apriori Algorithm in Machine Learning
    • Types of Machine Learning Algorithms
    • Bayes Theorem
    • AdaBoost Algorithm
    • Classification Algorithms
    • Clustering Algorithm
    • Gradient Boosting Algorithm
    • Mean Shift Algorithm
    • Hierarchical Clustering Algorithm
    • Hierarchical Clustering Agglomerative
    • What is a Greedy Algorithm?
    • What is Genetic Algorithm?
    • Random Forest Algorithm
    • Nearest Neighbors Algorithm
    • Weak Law of Large Numbers
    • Ray Tracing Algorithm
    • SVM Algorithm
    • Naive Bayes Algorithm
    • Neural Network Algorithms
    • Boosting Algorithm
    • XGBoost Algorithm
    • Pattern Searching
    • Loss Functions in Machine Learning
    • Decision Tree in Machine Learning
    • Hyperparameter Machine Learning
    • Unsupervised Machine Learning
    • K- Means Clustering Algorithm
    • KNN Algorithm
    • Monty Hall Problem
  • Basic
    • Introduction To Machine Learning
    • What is Machine Learning?
    • Uses of Machine Learning
    • Applications of Machine Learning
    • Naive Bayes in Machine Learning
    • Dataset Labelling
    • DataSet Example
    • Deep Learning Techniques
    • Dataset ZFS
    • Careers in Machine Learning
    • What is Machine Cycle?
    • Machine Learning Feature
    • Machine Learning Programming Languages
    • What is Kernel in Machine Learning
    • Machine Learning Tools
    • Machine Learning Models
    • Machine Learning Platform
    • Machine Learning Libraries
    • Machine Learning Life Cycle
    • Machine Learning System
    • Machine Learning Datasets
    • Machine Learning Certifications
    • Machine Learning Python vs R
    • Optimization for Machine Learning
    • Types of Machine Learning
    • Machine Learning Methods
    • Machine Learning Software
    • Machine Learning Techniques
    • Machine Learning Feature Selection
    • Ensemble Methods in Machine Learning
    • Support Vector Machine in Machine Learning
    • Decision Making Techniques
    • Restricted Boltzmann Machine
    • Regularization Machine Learning
    • What is Regression?
    • What is Linear Regression?
    • Dataset for Linear Regression
    • Decision tree limitations
    • What is Decision Tree?
    • What is Random Forest
  • Supervised
    • What is Supervised Learning
    • Supervised Machine Learning
    • Supervised Machine Learning Algorithms
    • Perceptron Learning Algorithm
    • Simple Linear Regression
    • Polynomial Regression
    • Multivariate Regression
    • Regression in Machine Learning
    • Hierarchical Clustering Analysis
    • Linear Regression Analysis
    • Support Vector Regression
    • Multiple Linear Regression
    • Linear Algebra in Machine Learning
    • Statistics for Machine Learning
    • What is Regression Analysis?
    • Clustering Methods
    • Backward Elimination
    • Ensemble Techniques
    • Bagging and Boosting
    • Linear Regression Modeling
    • What is Reinforcement Learning
  • Classification
    • Kernel Methods in Machine Learning
    • Clustering in Machine Learning
    • Machine Learning Architecture
    • Automation Anywhere Architecture
    • Machine Learning C++ Library
    • Machine Learning Frameworks
    • Data Preprocessing in Machine Learning
    • Data Science Machine Learning
    • Classification of Neural Network
    • Neural Network Machine Learning
    • What is Convolutional Neural Network?
    • Single Layer Neural Network
    • Kernel Methods
    • Forward and Backward Chaining
    • Forward Chaining
    • Backward Chaining
  • Deep Learning
    • What Is Deep learning
    • Overviews Deep Learning
    • Application of Deep Learning
    • Careers in Deep Learnings
    • Deep Learning Frameworks
    • Deep Learning Model
    • Deep Learning Algorithms
    • Deep Learning Technique
    • Deep Learning Networks
    • Deep Learning Libraries
    • Deep Learning Toolbox
    • Types of Neural Networks
    • Convolutional Neural Networks
    • Create Decision Tree
    • Deep Learning for NLP
    • Caffe Deep Learning
    • Deep Learning with TensorFlow
  • RPA
    • What is RPA
    • What is Robotics?
    • Benefits of RPA
    • RPA Applications
    • Types of Robots
    • RPA Tools
    • Line Follower Robot
    • What is Blue Prism?
    • RPA vs BPM
  • Interview Questions
    • Deep Learning Interview Questions And Answer
    • Machine Learning Cheat Sheet

Related Courses

Machine Learning Training

Deep Learning Training

Artificial Intelligence Training

What is a Greedy Algorithm?

By Priya PedamkarPriya Pedamkar

What is a Greedy Algorithm

Introduction to Greedy Algorithm

A greedy Algorithm is a special type of algorithm that is used to solve optimization problems by deriving the maximum or minimum values for the particular instance. This algorithm selects the optimum result feasible for the present scenario independent of subsequent results. The greedy algorithm is often implemented for condition-specific scenarios. This Algorithm is used to solve optimization problems, maximization problems, and minimization problems. And It provides feasible or optimized solutions. Some of the problem scenarios where it can be the best fit such as Huffman coding, Minimal spanning tree graph using Prim’s or Kruskal’s algorithm, and finding the shortest path between two vertices of a graph.

What is a Greedy Algorithm?

It is an algorithmic strategy used to make the best optional choice at a very small stage while eventually outputting a globally optimum solution. This algorithm picks the best solution feasible at that moment without regard to any consequences. The greedy method says that problem should be solved in stages wherein each one input is considered given that this input is feasible. As this approach only focuses on an immediate result with no regard for the bigger picture, it is considered greedy.

Defining the Core Concept

Till now, we know what it is and why is it named so. The below pointers will make you understand the greedy algorithm in a better way. By now, it has been very clear that the greedy algorithm only works when there is a problem; nevertheless, this approach is only applicable if we have a condition or constraint to that problem.

Types of Problems

  1. Minimization Problem: Getting a solution to a problem is easy, given that all the conditions are met. However, when this problem demands a minimum result, it is then called a Minimization Problem.
  2. Maximization Problem: A problem that demands the maximum result is known as the maximization problem.
  3. Optimization Problem: A problem is called an optimization problem when it requires either minimum or maximum results.

Types of Solutions

  1. Feasible Solution: Now, when a problem arises, we have many plausible solutions to this problem. Yet, taking into consideration the condition set on that problem, we choose solutions that satisfy the given condition. Such solutions that help us get results meeting the given condition is called a Feasible Solution.
  2. Optimal Solution: A solution is called optimal when it is already feasible and achieves the objective of the problem; the best result. This objective could either be the minimum or maximum result. The point here to be noticed is that any problem will only have one optimal solution.

The following example will make you understand the greedy method easily. Say one wants to buy the best car available in the market. One of the methods to choose this car is by analyzing all the cars in the market. Now, this being time-consuming, to make it easy, one selects a car from those specific brands which they are interested in investing in. Categorizing this further, one would again choose the desired models looking at its features. Therefore, the approach used here is greedy as this solution was the optimal solution for you while considering all the factors were favorable to you.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Core Components of Greedy Algorithm

Now when we have a better understanding of this mechanism, let’s explore the core components of a greedy algorithm that sets it apart from other processes:

  • Candidate set: An answer is created from this set.
  • Selection function: It selects the best candidate to be included in the solution.
  • Feasibility function: This section calculates if a candidate can be used to contribute to the solution.
  • An objective function: It assigns a value to a complete or a partial solution.
  • A solution function: This is used to indicate if a proper solution has been met.

Where does the Greedy Algorithm work the best?

It can be applied to the below-mentioned problems.

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,650 ratings)
  • The Greedy approach can be used to find the minimal spanning tree graph using Prim’s or Kruskal’s algorithm.
  • Finding the shortest path between two vertices is yet another problem that can be solved using a greedy algorithm. Applying Dijkstra’s algorithm along with the greedy algorithm will give you an optimal solution.
  • Huffman Coding

Advantages

The biggest advantage that the Greedy algorithm has over others is that it is easy to implement and very efficient in most cases.

Disadvantages

It basically builds a solution part by part and choosing the next part in such a way that it yields the best solution to the present problem at hand immediately. As a result, there is no regard or worry about the consequences of the current decision taken. Never reconsidering the choices taken previously, it fails to produce an optimal solution, though it gives a near-optimal solution. Knapsack Problem and Travelling Salesman Problem are examples of problems where it fails to produce an optimal solution.

  • Knapsack Problem: Most commonly known by the name rucksack problem, it is an everyday problem faced by many people. Say we have a set of items and each has a different weigh and value (profit) to filled into a container or should be collected in such a way that the total weight is less than or equal to that of the container while the total profit is maximized.

Conclusion

It is best applicable when one needs a solution in real-time and approximate answers are “good enough”. Clearly, it minimizes time while making sure that an optimal solution is produced; hence it is more applicable to use in a situation where less time is required. Post-reading this article, one might have a fair idea about greedy algorithms. In addition, this post explains why it is regarded as the best framework that answers nearly all programming challenges along with helping you to decide the most optimal solution at a given point in time.

However, on the rough side, for applying the theory of greedy algorithms, one must work harder to know the correct issues. Although it’s a scientific concept that has logic, it also has an essence of creativity.

Recommended Articles

This has been a guide to What is a Greedy Algorithm. Here we discussed the Core Concept, components, Advantage, and Disadvantage of the Greedy Algorithm. You can also go through our other suggested articles to learn more –

  1. Algorithm in Programming
  2. What is Perl?
  3. Introduction To Algorithm
  4. What is Agile Sprint?
Popular Course in this category
Machine Learning Training (20 Courses, 29+ Projects)
  19 Online Courses |  29 Hands-on Projects |  178+ Hours |  Verifiable Certificate of Completion
4.7
Price

View Course

Related Courses

Deep Learning Training (18 Courses, 24+ Projects)4.9
Artificial Intelligence AI Training (5 Courses, 2 Project)4.8
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more