Top Ad unit 728 × 90

Latest news

recent

Ý tưởng tham lam (Greedy)

Trong mọi khía cạnh của cuộc sống hàng ngày, công việc và nghiên cứu, con người phải luôn đối mặt với các vấn đề (problem). Có ai đó còn phát biểu: sống là một quá trình cố gắng để giải quyết những bài toán, những vấn đề. Trong số những vấn đề đó, có những vấn đề chỉ đơn giản là cần có giải pháp nhưng cũng có những vấn đề khắt khe hơn đòi hỏi không chỉ là giải pháp (Solution) mà giải pháp đó phải là giải pháp tốt nhất (best solution) (nhanh nhất, đơn giản nhất, hiệu quả nhất ...) đó được gọi là những vấn đề cần tối ưu (Optimization Problem) .
Ý tưởng Greedy (tham lam) là một trong những hướng suy nghĩ được sử dụng trong tình huống này. Các thuật toán sử dụng greedy như nền tảng logic để tiếp cận, giải quyết vấn đề được gọi là những Greedy Algorithms. Các thuật toán ứng dụng Greedy thường diễn ra, hoạt động qua nhiều chặng (phase) về không gian hay thời gian, và tại mỗi chặng chúng ta thường không biết thông tin toàn bộ dữ liệu của cả quá trình mà chỉ biết tình trạng hiện tại và thông tin cho bước đi kế tiếp. Ý tưởng chính của Greedy là chúng ta không cần quan tâm tới dữ liệu tổng thể mà chỉ từ những dữ liệu tại từng chặng chọn ra giải pháp tối ưu tại mỗi chặng đó với hy vọng là tổng hợp những giải pháp tối ưu cục bộ sẽ mang lại một giải pháp tối ưu cho tổng thể.Từ ý tưởng đó cho thấy, kết quả có được từ Greedy Algorithm chỉ mang tính tương đối, thông thường giải pháp cuối cùng không phải là tối ưu mà chỉ là gần với tối ưu. Tuy nhiên với những điều kiện, thông tin thường không mấy rỏ ràng của đầu vào, và cách tiếp cận vấn đề khá trong sáng của mình, Greedy thường đưa ra giải pháp tương đối tốt trong giới hạn có thể chấp nhận và đặc biệt có tốc độ nhanh.

Một vài thuật toán áp dụng Greedy: Thuật toán tìm đường đi ngắn nhất Dijkstra, Traveling salesman, mã hóa Huffman, Các thuật toán tìm cây kết nối tối thiểu như Kruskal và Prim, ...

Thay cho lời kết của bài viết này, tôi muốn nói về một kinh nghiệm trong phương pháp học giải thuật, cũng như toán. Đừng bao giờ nghiên cứu những thứ đại loại như thế này với một cái đầu quá cứng nhắc. Trong quá khứ tôi đã được một người thầy dạy cho một thuật toán tìm đường đi ngắn nhất với cái tên là thuật toán greedy. Từ đó về sau tôi chỉ biết tới greedy như là một giải thuật với cái tên greedy mà không biết rằng  nó chỉ có thể coi là một ví dụ mà thôi :(. Thầy của tôi đã vô tình đem cái cụ thể mà che mất tầm nhìn của học sinh mình. Bạn không thể phát triển ý tưởng, ứng dụng tri thức một cách uyển chuyển với cách nhìn vấn đề như thế. Chính vì lý do đó mà bài viết này tôi không nói về thuật toán greedy mà tôi muốn nhấn mạnh tới ý tưởng mang tính greedy :p 


Binh Nguyen - Bioz
Ý tưởng tham lam (Greedy) Reviewed by Bioz on 3:51:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.