Greedy Method

Introduction

• Greedy method is a strategy for solving problems, similar to divide and conquer and other strategies.
• It is used to solve optimization problems, which require either a minimum or maximum result.

Key Terms

• Optimization Problem: A problem that requires the minimum or maximum result.
• Feasible Solution: A solution that satisfies the conditions or constraints of the problem.
• Optimal Solution: A feasible solution that yields the best result (either minimum or maximum), and there can only be one optimal solution.

Example Problem

• Problem: Traveling from location A to location B within 12 hours.
• Possible Solutions: Walk, bike, car, train, flight.
• Constraint: Must complete the journey in 12 hours.
• Feasible Solutions: Train or flight (as they meet the time constraint).
• Optimization Goal: Minimize cost or time.
• Optimal Solution: The feasible solution with the minimum cost, e.g., traveling by train.

Greedy Method Approach

• Problems are solved in stages.
• In each stage, one input is considered.
• If the input is feasible, it is included in the solution.
• By including all feasible inputs, an optimal solution is reached.

General Method

• Start with input of size n and iterate through values.
• Select inputs from 1 to n.
• If an input x is feasible, include it in the solution.

Practical Examples

Example 1: Buying a Car

• Goal: Choose the best car in terms of features (usually implies maximum cost for best features).
• Greedy Method: Sort brands, select top models, and choose a well-known or latest release.
• Conclusion: Without checking all cars, you select based on a known method, getting a satisfactory result.

Example 2: Hiring Employees

• Goal: Hire the best person from 1000 applicants.
• Process: Conduct series of tests (written, technical, group discussion) to filter candidates and select the best.
• Outcome: The person selected is considered the best based on the adopted method.

Characteristics of Greedy Method

• Relies on known methods of selection and decision-making.
• Provides a quick solution without exhaustive search or examination.
• Often used in situations where time and resources are limited.

Conclusion

• Greedy method offers a reliable approach for solving optimization problems efficiently.
• Its application is best suited for problems where a quick solution is favorable.