How can greedy algorithms help you solve optimization problems?

I think of greedy algorithms as the thrill-seekers of problem-solving. it's like exploring a maze - at each junction, we grab the path that seems to be the best, aiming for quick wins without a second thought. It's like navigating through uncharted territory, taking risks at every turn. Locally optimal choices drive these algorithms, optimizing for immediate gains, it's almost humane. While they might not guarantee the perfect solution, they bring a sense of adventure to problem-solving.

A greedy algorithm is a strategy for solving problems by making the "best" choice at each step, even if it doesn't guarantee the absolute best outcome in the end. Imagine climbing a mountain: a greedy approach would pick the steepest path at each point, reaching the top quickly, but not necessarily taking the most efficient route. Locally optimal choices: They optimize each step, aiming for the best immediate gain. No backtracking: Once a choice is made, they stick with it, even if it leads to suboptimal results later. Think of it as a quick and dirty approach, prioritizing speed over guaranteed perfection. It's a valuable tool in the programmer's toolbox, but not always the ultimate solution!

Nghe tên thuật toán tham lam thì mọi người đã nghĩ đến việc nó định làm gì rồi. Tham lam cái đúng trước mắt và chưa quan tâm đến các thứ khác. Chỉ cần bước hiện tại tốt là được rồi và mong rằng nó sẽ đem đến kết quả tốt trong cả bài toán. Thế nên với phương thức tiếp cận này thì hiệu quả nhãn tiền rất tốt, ví dụ như lúc làm leet code thì hard code thêm cover luôn mấy trường hợp 'khó, dị' thì cũng là 1 dạng giải thuật tham lam nho nhỏ. Nhưng nó đúng. Còn tham lam toàn bộ mà vẫn đúng được thì sao?

The Greedy approach, a simple yet powerful optimization method, often yields optimal solutions by selecting locally optimal choices at each step without reconsideration. It entails: 1) Selecting a value immediately closer to the desired outcome. 2) Decomposing the problem into similar subproblems based on the chosen value. 3) Iterating until reaching the globally optimal solution. Decisions are solely based on past choices, lacking foresight for future adjustments. Once made, decisions remain final at each step. Similar to real life, a greedy decision looks at an immediate choice which will take one step closer to the desired goal.

A greedy algorithm is a type of algorithmic paradigm that makes locally optimal choices at each stage with the hope of finding a global optimum. In other words, a greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result. The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top-down approach. This algorithm may not produce the best result for all the problems. It's because it always goes for the local best choice to produce the global best result.

Designing a Greedy Algorithm: Define the Problem: Clearly understand the problem and goal. Identify Subproblems: Break down the problem into smaller components. Define Objective Function: Clearly define criteria for making decisions. Make Greedy Choices: Choose locally optimal options at each step. Prove Greedy Choice is Safe: Show locally optimal choices lead to a global optimum. Iterate or Recur: Repeat the process until a solution is found. Construct Solution: Build the final solution from greedy choices. Analyze Complexity: Assess time and space complexity.

Khi thiết kế thuật toán tham lam thì vấn đề đau đầu nhất là dựa vào tiêu chí gì để tham lam. Thường thì chúng ta nhìn vào biểu hiện của đáp án để tạo ra công thức tham lam hướng tới kết quả. Rồi tạo ra cách để khoanh vùng cũng như tiếp cận nó, mình hay dùng từ là tạo ra tiêu chí đánh giá. Nhưng bước đau đớn nhất là phải chứng minh rằng mình đúng. Và đúng được bao nhiêu trường hợp. Như bài toán cái túi thì tham lam cũng sẽ đúng thôi mà đúng nhiều hay ít, rồi bài toán sắp xếp phòng họp cũng vậy.

One of the best example of greedy algorithm is Dijkstra's algorithm. It is greedy algorithm because it selects the locally optimal choice at each step(choosing the node with the shortest known distance). This approach aims to find the globally optimal solution by extending the shortest paths to neighbouring nodes iteratively.

Here are some examples: Fractional Knapsack: Given weights and values of items, determine the maximum value that can be obtained by selecting fractional weights of each item. Greedy Approach: Select items with the highest value-to-weight ratio first. Activity Selection: Given a set of activities with start and finish times, find a maximum-size subset of mutually compatible activities. Greedy Approach: Choose activities that finish earliest and do not overlap with the current selection. Huffman Coding: Given a set of characters and their frequencies, build an optimal binary tree to represent characters, minimizing the total encoding length. Greedy Approach: Build the Huffman tree by repeatedly merging the two least frequent characters.

Khi bài toán thực tế xuất hiện thì chúng ta sẽ rất dễ dàng nghĩ ngay ra được 1 thuật toán tham lam ~> Nó rất đơn giản đề bắt đầu. Vừa dễ bắt đầu, vừa dễ hiểu và đôi khi triển khai cũng dễ (thường là vậy). Sau khi kiểm thử, và tối ưu thì nó cũng sẽ cung cấp được 1 phương án 'tối ưu' gần với đáp án tốt nhất. Vì thế nó dễ đạt được tiêu chuẩn về tốc độ hay bộ nhớ, và hiển nhiên là dễ triển khai và bảo trì. Và tất nhiên nó còn rất nhiều không gian để có thể cải thiện

Greedy algorithms offer several advantages: Simplicity: Greedy algorithms are often simple to understand and implement. Efficiency: Greedy algorithms are generally efficient and have low time complexity. Optimality in Some Cases: In many cases, greedy algorithms provide an optimal solution. Making the best local choice at each step can lead to a global optimum. Space Efficiency: Greedy algorithms typically require minimal additional memory beyond the input data. Applicability: Greedy algorithms are versatile and applicable to a wide range of problems. Incremental Solutions: Greedy algorithms often build solutions incrementally.

While greedy algorithms can not be used to solve all optimization problems they offer a good approximation of the problem. We can use greedy algorithms to generate viable starting points to be used for optimization allowing us to cut down on runtime or the search space. For example, using a Greedy Maximum Matching algorithm produces a 2-approximation or using a degree-sensitive greedy matching. This can be used to speed up the implementation of an exact answer such Edmond's Blossom algorithm which for large dense graphs will offer significant performance increases.

Tất nhiên bất lợi lớn nhất là nó không 'hoàn toàn đúng'. Tham lam có thể dẫn tới vấn đề về việc đem lại kết quả không đúng hay chưa phải là đúng nhất. Nên tính áp dụng của nó sẽ bị hạn chế. Ngoài ra thì do tính chất đơn giản và đưa lựa chọn dựa trên tập thông tin hiện tại nên nó sẽ tự hạn chế chính mình trong việc thu thập thêm thông tin để ra quyết định. Lúc này nó sẽ chuyển biến sang một dạng thuật toán khác thì mới đáp ứng đc các yêu cầu mở rộng. Cái khổ tiếp theo là đôi khi kết quả ra đúng rồi mà không thể tự chứng minh được mình đúng ra sao, đúng bao nhiêu, và sẽ sai trong bao nhiêu trường hợp.

Lack of Global Optimality: Greedy choices may lead to locally optimal solutions that are not globally optimal. No Backtracking: Once a decision is made, it is not reconsidered, potentially missing better alternatives. Dependency on Local Information: Decisions are made based on local information without a global view, leading to suboptimal solutions. Sensitivity to Input: Small changes in the input may result in significantly different outcomes. Hard to Modify: Modifying a greedy algorithm to accommodate additional constraints can be challenging. Not Always Applicable: Greedy algorithms may not be suitable for all problems, especially those with complex structures.

Because Greedy algorithms are one-way decision-making, they do not reconsider previous locally optimal choices based on updated context/ new information that would change the best choice. A way to offset this downside would to be pair Greey Algorithms without optimization techniques depending on the problem application to improve choices incorporating the new information.

Nếu với các bạn đi làm leetcode thì tham lam rất ít khi xuất hiện, nó thường là 'tham lam đúng đắn' mất rồi, tức là các bạn chứng minh được rằng thuật toán tham lam này luôn đúng trong mọi trường hợp mà đề bài yêu cầu. Thế nên nó thường xuất hiện trong tư tưởng hàng ngày nhiều hơn. Khi chúng ta phải đưa quyết định trong trạng thái thiếu thông tin thì tư duy của tham lam sẽ xuất hiện. Lúc đó thì tiêu chí đánh giá sẽ đóng vai trò quan trọng để đưa chúng ta đến phương án tiếp cận tối ưu nhất. Càng có nhiều thông tin thì sẽ có căn cứ để đưa tiêu chí mà ra lựa chọn hơn. 1 kẻ trộm không biết giá trị của đồ vật thì có giỏi thuật toán đến đâu cũng dễ dàng bỏ qua món đồ giá trị nhất. Nhưng ngược lại thì biết món đồ giá trị mà k bán đc thì cũng bỏ.