Thuật toán tham lam - Greedy Algorithm
Lại là mình đây 😘, sau một thời gian rất dài bỏ bê việc viết blog, thì hôm nay mình quay trở lại.
Nhưng không phải để viết tiếp về hành trình những ngày dài đằng đẵng cô đơn, buồn bã nơi xứ người nữa, mà là quay lại với một diện mạo hoàn toàn mới, viết về chủ đề cũng hoàn toàn mới với mình- đó chính là chủ đề liên quan đến Toán học!!!!
Muc đích để tất cả mọi người đều thấy, Toán học không hề khô khan và khó hiểu. Toán học thực chất sẽ rất thú vị nếu như mình biết ứng dụng vào mọi vấn đề trong cuộc sống, hihi 😍.
Đầu tiên, mình xin được viết về chủ đề- Greedy Algorithm- thuật toán tham lam.
Thuật toán này khá mới với mình- mình mới học trong kì này qua bộ môn "Methoden des Decision Support" ( nằm trong tổ hợp môn Kombinatorische Optimierung- tối ưu hóa tổ hợp- chương trình Thạc Sĩ - khoa Thống Kê).
Đầu tiên chúng mình cần tìm hiểu: thuật toán tham lam là gì? Đó chính là một thuật toán giải quyết một bài toán theo kiểu siêu hình (metaheuristic ) để lựa chọn được giải pháp tối ưu.
Vẫn hơi khó hiểu đúng không?- Vậy thì chúng mình chuyển qua các bước- phương pháp "tham lam" nhé:
Ứng dụng của thuật toán này mình thấy khá hữu dụng cho cuộc sống hàng ngày, đặc biệt sẽ giúp chúng mình làm việc đạt hiệu quả tốt nhất nếu mình biết áp dụng lối giải của thuật toán Tham lam vào đời sống.
Mình lấy ví dụ nhé: Cho n công việc cần phải hoàn thành, mỗi việc thực hiện trong một đơn vị thời gian. Công việc i sẽ mang lại tiền thưởng W_i trong một khoảng thời gian t_i
Bài toán đưa ra sẽ là: Hãy tính cách thực hiện các công việc để đạt được số tiền thưởng cao nhất và trong khoảng thời gian ngắn nhất.
Cách để giải bài toán kia khá đơn giản. Đầu tiên hãy kẻ 1 bảng ra- một cột là số thứ tự cho từng công việc. Cột tiếp theo là số thời gian cần hoàn thành cho từng công việc đó. Cột cuối cùng sẽ là số tiền thưởng của mỗi công việc đó.
Tiếp đến là các bước giải quyết bài toán:
Trong bộ môn của mình, mình gặp khá nhiều bài tập sử dụng thuật toán Tham lam- đó chính là dạng bài toán Cây bao trùm nhỏ nhất (Minimum Spanning Tree Problem- MST), hoặc Trọng lượng rừng tối đa (Maximum weight forest problem-MWF).
Trong dạng MST thì khá đơn giản- mình chỉ việc xác định các đỉnh và các cạnh.
Lưu ý nhỏ: đó là- kết quả số cạnh luôn bằng sổ đỉnh trừ đi 1 nhé.
Vì là dạng toán cây bao trùm nhỏ nhất, nên mình sẽ bắt đầu từ đỉnh với trọng lượng thấp nhất, rồi lần lượt đến các đỉnh khác - Một cây bao trùm là một tập hợp của các đỉnh sao cho nó không được tạo thành 1 vòng (chu trình) mà nó vẫn phải nối được tất cả các đỉnh.
Ví dụ như: dạng bài toán ban đầu dưới dạng 1 hình vuông- (là 4 đỉnh)- nhưng khi xác định cây bao trùm nhỏ nhất- kết quả sẽ chỉ là 3 cạnh (nối 4 đỉnh)- chứ không phải là 4 cạnh (1 vòng- chu trình) nhé 😜.
Dạng MWF thì ngược lại với MST- nghĩa là bắt đầu từ đỉnh với trọng lượng lớn nhất.
Các bước làm giống như trong bài toán MST nhé.
Đấy- hoàn toàn có ứng dụng vào thực tiễn đúng không? - Thực chất mình thấy mình suy nghĩ khá linh hoạt, và nhanh nhẹn hơn sau mỗi lần học thêm một thuật toán, hoặc một chủ đề toán học nào đó, hihi.
Và cũng giúp cho mình rất nhiều trong công việc bán hàng online, tính toán số lợi nhuận, cũng như số tiền chi tiêu, sinh hoạt, tiết kiệm, đầu tư của mình.
Mình sẽ tiếp tục viết về các chủ đề liên quan đến Toán học sau nhé.
Hẹn gặp lại tất cả mọi người vào một ngày gần nhất 💕.
Thủ đô Vienna, Áo- ngày 10 tháng 05 năm 2019.
Lien Nguyen.
Nhưng không phải để viết tiếp về hành trình những ngày dài đằng đẵng cô đơn, buồn bã nơi xứ người nữa, mà là quay lại với một diện mạo hoàn toàn mới, viết về chủ đề cũng hoàn toàn mới với mình- đó chính là chủ đề liên quan đến Toán học!!!!
Muc đích để tất cả mọi người đều thấy, Toán học không hề khô khan và khó hiểu. Toán học thực chất sẽ rất thú vị nếu như mình biết ứng dụng vào mọi vấn đề trong cuộc sống, hihi 😍.
Đầu tiên, mình xin được viết về chủ đề- Greedy Algorithm- thuật toán tham lam.
Thuật toán này khá mới với mình- mình mới học trong kì này qua bộ môn "Methoden des Decision Support" ( nằm trong tổ hợp môn Kombinatorische Optimierung- tối ưu hóa tổ hợp- chương trình Thạc Sĩ - khoa Thống Kê).
Đầu tiên chúng mình cần tìm hiểu: thuật toán tham lam là gì? Đó chính là một thuật toán giải quyết một bài toán theo kiểu siêu hình (metaheuristic ) để lựa chọn được giải pháp tối ưu.
Vẫn hơi khó hiểu đúng không?- Vậy thì chúng mình chuyển qua các bước- phương pháp "tham lam" nhé:
- Tìm lựa chọn sao cho các bước tiếp theo chỉ việc giải quyết một bài toán con.
- Chứng minh: mỗi sự lựa chọn Tham lam tại mỗi bước 🔜 luôn tìm được một giải pháp tối ưu (cho bài toán ban đầu).
- Chỉ ra: với sự lựa chọn tham lam tại mỗi bước 🔜 giải pháp tối ưu của bài toán con còn lại kết hợp với sự lựa chọn Tham lam này sẽ đi đến một giải pháp tối ưu.
Ứng dụng của thuật toán này mình thấy khá hữu dụng cho cuộc sống hàng ngày, đặc biệt sẽ giúp chúng mình làm việc đạt hiệu quả tốt nhất nếu mình biết áp dụng lối giải của thuật toán Tham lam vào đời sống.
Mình lấy ví dụ nhé: Cho n công việc cần phải hoàn thành, mỗi việc thực hiện trong một đơn vị thời gian. Công việc i sẽ mang lại tiền thưởng W_i trong một khoảng thời gian t_i
Bài toán đưa ra sẽ là: Hãy tính cách thực hiện các công việc để đạt được số tiền thưởng cao nhất và trong khoảng thời gian ngắn nhất.
Cách để giải bài toán kia khá đơn giản. Đầu tiên hãy kẻ 1 bảng ra- một cột là số thứ tự cho từng công việc. Cột tiếp theo là số thời gian cần hoàn thành cho từng công việc đó. Cột cuối cùng sẽ là số tiền thưởng của mỗi công việc đó.
Tiếp đến là các bước giải quyết bài toán:
- Bước 1: Sắp xếp công việc theo chiều giảm của số tiền thưởng ( từ công việc 1 cho tới công việc thứ n)
- Bước 2: Xét trục thời gian tương ứng với công việc trên bước 1. .
- Bước 3: Phân loại và so sánh số tiền thưởng tương ứng với các lịch ⇨đưa ra lịch cần tìm với số tiền thưởng tương ứng.
Trong bộ môn của mình, mình gặp khá nhiều bài tập sử dụng thuật toán Tham lam- đó chính là dạng bài toán Cây bao trùm nhỏ nhất (Minimum Spanning Tree Problem- MST), hoặc Trọng lượng rừng tối đa (Maximum weight forest problem-MWF).
Trong dạng MST thì khá đơn giản- mình chỉ việc xác định các đỉnh và các cạnh.
Lưu ý nhỏ: đó là- kết quả số cạnh luôn bằng sổ đỉnh trừ đi 1 nhé.
Vì là dạng toán cây bao trùm nhỏ nhất, nên mình sẽ bắt đầu từ đỉnh với trọng lượng thấp nhất, rồi lần lượt đến các đỉnh khác - Một cây bao trùm là một tập hợp của các đỉnh sao cho nó không được tạo thành 1 vòng (chu trình) mà nó vẫn phải nối được tất cả các đỉnh.
Ví dụ như: dạng bài toán ban đầu dưới dạng 1 hình vuông- (là 4 đỉnh)- nhưng khi xác định cây bao trùm nhỏ nhất- kết quả sẽ chỉ là 3 cạnh (nối 4 đỉnh)- chứ không phải là 4 cạnh (1 vòng- chu trình) nhé 😜.
Dạng MWF thì ngược lại với MST- nghĩa là bắt đầu từ đỉnh với trọng lượng lớn nhất.
Các bước làm giống như trong bài toán MST nhé.
Đấy- hoàn toàn có ứng dụng vào thực tiễn đúng không? - Thực chất mình thấy mình suy nghĩ khá linh hoạt, và nhanh nhẹn hơn sau mỗi lần học thêm một thuật toán, hoặc một chủ đề toán học nào đó, hihi.
Và cũng giúp cho mình rất nhiều trong công việc bán hàng online, tính toán số lợi nhuận, cũng như số tiền chi tiêu, sinh hoạt, tiết kiệm, đầu tư của mình.
Mình sẽ tiếp tục viết về các chủ đề liên quan đến Toán học sau nhé.
Hẹn gặp lại tất cả mọi người vào một ngày gần nhất 💕.
Thủ đô Vienna, Áo- ngày 10 tháng 05 năm 2019.
Lien Nguyen.
Bài viết hay bạn ơi, tuy nhiên cái này chỉ hiệu quả khi tất cả deterministic nghĩa là bạn biết dc tất cả step sau đó( theo mình hiểu cách bạn viết thì bạn chỉ optimize đúng điểm t mà thôi) và maximize khi mà take account tất cả thông tin đó. Mình ko biết có phải là ý nghĩa của greedy hay ko( mình ko biết gì về toán lắm) như vậy greedy có vẻ chỉ mang tính static chứ không optimize in general, và nếu gặp stochastic( cuộc sống thì thường vậy) thì gần như bó tay. Vdu cuộc sống thì bạn optimize thời gian cho làm và học đi, làm nhiều có tiền, có vẻ ổn vì chưa cần học nhiều, nhưng biết đâu học nhiều thì bạn gặp một ai đó đưa đến một cơ hội khác tốt hơn về tương lai và ngược lại. Vậy nên mình vẫn là fan của dynamic programming hơn
ReplyDelete