Trong bài đăng này, chúng ta sẽ hiểu sự khác biệt giữa thuật toán tham lam và các phương pháp lập trình động.
Thuật toán tham lam
Nó là một mô hình thuật toán xây dựng trên một giải pháp theo từng phần, từng bước. Bước tiếp theo được chọn sao cho nó mang lại lợi ích rõ ràng và tức thì nhất.
- Các vấn đề liên quan đến việc lựa chọn các giá trị tối ưu cục bộ sẽ giúp ích trong việc lựa chọn các giá trị / giải pháp tối ưu toàn cục cho vấn đề. Như vậy đã gây ra các vấn đề liên quan đến thuật toán tham lam.
- Không có gì chắc chắn rằng một thuật toán tham lam sẽ dẫn đến một giải pháp tối ưu.
- Một lựa chọn tối ưu được đưa ra ở mọi giai đoạn của vấn đề, tức là giải pháp tối ưu cục bộ.
- Nó hiệu quả về mặt sử dụng bộ nhớ vì không có vấn đề gì về việc phải quay lại hoặc thay đổi các giải pháp / giá trị trước đó.
- Nhìn chung, chúng rất nhanh so với các kỹ thuật lập trình động.
- Ví dụ:Thuật toán đường đi ngắn nhất của Dijkstra mất thời gian O (ELogV + VLogV).
- Giải pháp trong thuật toán tham lam được tính theo phương pháp chuyển tiếp, không bao giờ truy cập các giá trị / giải pháp trước đó hoặc thay đổi chúng.
Lập trình động
Đây là một kỹ thuật tối ưu hóa giúp lưu trữ kết quả của các bài toán con để chúng không cần phải tính toán lại khi cần thiết trong tương lai. Chúng chỉ có thể được trích xuất từ tập hợp được tính toán trước. Nó làm giảm độ phức tạp về thời gian từ độ phức tạp hàm mũ sang độ phức tạp đa thức.
- Ví dụ:Một giải pháp đệ quy có thể được biến thành một bài toán lập trình động bằng máy tính.
- Trong điều này, quyết định được đưa ra ở mỗi bước được thực hiện bằng cách xem xét vấn đề hiện tại và giải pháp cho bài toán tổng đã giải trước đó. Điều này sẽ được sử dụng để tính toán giá trị / giải pháp tối ưu.
- Đảm bảo rằng giải pháp của một vấn đề lập trình động sẽ là giải pháp tối ưu.
- Ở đây, giải pháp tối ưu được chọn là giải pháp tối ưu toàn cầu. Nó sử dụng một công thức nhất định đã được sử dụng để lưu trữ các giá trị trạng thái được tính toán trước đó.
- Cần có bảng lập trình động để ghi nhớ. Điều này làm tăng độ phức tạp của bộ nhớ.
- Nó tương đối chậm hơn.
- Ví dụ:Thuật toán Bellman Ford mất thời gian O (VE).
- Lập trình động xác định giải pháp bằng cách tiếp cận từ dưới lên hoặc từ trên xuống, bằng cách phát triển từ các vấn đề nhỏ hơn có giải pháp tối ưu.