Thuật toán tham lam

Các thuật toán tham lam xây dựng một giải pháp từng bước bằng cách lặp lại lựa chọn tốt nhất ở bước hiện tại, và chúng chính xác khi những lựa chọn tối ưu cục bộ như vậy được chứng minh là dẫn đến một giải pháp tối ưu toàn cục.

Definition

Một thuật toán tham lam xây dựng một giải pháp thông qua một chuỗi các lựa chọn, mỗi lựa chọn được chọn để tối ưu hóa một tiêu chí cục bộ nào đó, không bao giờ xem xét lại các lựa chọn trước đó; nó chỉ chính xác khi các lựa chọn tối ưu cục bộ mang lại kết quả tối ưu toàn cục.

Scope

Chủ đề này bao gồm mô hình tham lam: thuộc tính lựa chọn tham lam và cấu trúc con tối ưu làm cơ sở cho nó, các kỹ thuật chứng minh tiêu chuẩn (lập luận trao đổi và khung matroid), và các thuật toán tham lam kinh điển bao gồm mã hóa Huffman, cây bao trùm tối thiểu (Kruskal và Prim), đường đi ngắn nhất của Dijkstra, và lập lịch khoảng. Nó cũng đề cập đến khi các chiến lược tham lam chỉ đóng vai trò là các phương pháp phỏng đoán xấp xỉ chứ không phải là các phương pháp chính xác.

Core questions

• Thuộc tính lựa chọn tham lam là gì, và làm thế nào để chứng minh nó cho một vấn đề cụ thể?
• Làm thế nào một lập luận trao đổi chứng minh rằng một lựa chọn tham lam là an toàn?
• Những vấn đề nào có cấu trúc matroid đảm bảo tính tối ưu tham lam?
• Khi nào một phương pháp tham lam chỉ là một phương pháp xấp xỉ chứ không phải là một thuật toán chính xác?
• Thuật toán tham lam so sánh như thế nào với quy hoạch động cho cùng một vấn đề?

Key concepts

• thuộc tính lựa chọn tham lam
• cấu trúc con tối ưu
• lập luận trao đổi
• matroid
• mã hóa Huffman
• cây bao trùm tối thiểu
• lập lịch khoảng
• bài toán cái túi phân số

Key theories

Thuộc tính lựa chọn tham lam và các lập luận trao đổi

Một vấn đề chấp nhận giải pháp tham lam khi một giải pháp tối ưu toàn cục luôn có thể được sửa đổi để phù hợp với lựa chọn đầu tiên tham lam mà không làm mất tính tối ưu; các lập luận trao đổi (hoặc 'tham lam luôn dẫn đầu') chính thức hóa điều này.

Matroid và tính tối ưu tham lam

Khi các giải pháp khả thi tạo thành các tập hợp độc lập của một matroid có trọng số, thuật toán tham lam luôn tìm thấy một tập hợp độc lập có trọng số tối đa; điều này thống nhất các kết quả như tính tối ưu của thuật toán cây bao trùm tối thiểu của Kruskal.

Clinical relevance

Các thuật toán tham lam thúc đẩy các hệ thống được sử dụng rộng rãi: mã hóa Huffman trong các định dạng nén dữ liệu, thuật toán cây bao trùm tối thiểu trong thiết kế mạng, thuật toán Dijkstra trong định tuyến và điều hướng, và các phương pháp phỏng đoán lập lịch và bao phủ tập hợp tham lam trong hệ điều hành và phân bổ tài nguyên.

History

Lý luận tham lam xuất hiện trong các kết quả kinh điển như thuật toán cây bao trùm tối thiểu của Kruskal (1956) và Prim (1957), mã tiền tố tối ưu của Huffman (1952), và thuật toán đường đi ngắn nhất của Dijkstra (1959). Giải thích dựa trên lý thuyết matroid về thời điểm các phương pháp tham lam thành công đã được Edmonds và những người khác phát triển vào những năm 1960 và 1970.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

Tại sao thuật toán tham lam hoạt động với bài toán cái túi phân số nhưng không hoạt động với bài toán cái túi 0/1?

Trong bài toán cái túi phân số, các vật phẩm có thể được chia nhỏ, vì vậy việc chọn vật phẩm có giá trị trên trọng lượng cao nhất trước luôn an toàn và được chứng minh là tối ưu. Trong bài toán cái túi 0/1, các vật phẩm không thể chia nhỏ, lựa chọn tham lam có thể loại trừ một sự kết hợp tốt hơn, và quy hoạch động là cần thiết để tìm ra một tối ưu chính xác.

Làm thế nào để chứng minh một thuật toán tham lam là chính xác?

Hai kỹ thuật tiêu chuẩn là lập luận trao đổi, biến đổi bất kỳ giải pháp tối ưu nào thành giải pháp tham lam mà không làm xấu đi nó, và lập luận 'tham lam luôn dẫn đầu', cho thấy giải pháp từng phần tham lam ít nhất cũng tốt bằng bất kỳ giải pháp nào khác ở mỗi bước. Lý thuyết Matroid cung cấp một điều kiện đủ tổng quát.