Kỹ thuật đệ qui hoặc ngay cả phương pháp chia để trị có thể phải giải nhiều lần một bài toán con, nên giảm hiệu quả Kỹ thuật qui hoạch động khắc phục hạn chế này bằng cách giải các bài toán con trước khi giải bài toán đã cho | CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT CHƯƠNG 5 Nội dung Qui hoạch động Giải thuật tham lam Giải thuật quay lui (backtracking) Giải thuật nhánh và cận Nội dung Kỹ thuật đệ qui hoặc ngay cả phương pháp chia để trị có thể phải giải nhiều lần một bài toán con, nên giảm hiệu quả Kỹ thuật qui hoạch động khắc phục hạn chế này bằng cách giải các bài toán con trước khi giải bài toán đã cho Kết quả các bài toán con được lưu trữ vào các bảng và sau đó khỏi phải tính lại khi gặp lại bài toán con đó. Trong thiết kế cần tìm được mối ràng buộc giữa bài toán cần giải và bài toán con, sự liên hệ thường là các hệ thức truy hồi Qui hoạch động là một phương pháp rất hiệu quả và được áp dụng cho những bài toán tối ưu hóa (optimization problem). Qui hoạch động (bỏ) Quy hoạch động (dynamic programming) giải các bài toán bằng cách kết hợp các lời giải của các bài toán con của bài toán đang xét. Phương pháp này khả dụng khi các bài toán con không độc lập đối với nhau, tức là khi các bài toán con có dùng chung những bài toán “cháu” (subsubproblem). Qui hoạch động giải các bài toán “cháu” dùng chung này một lần và lưu lời giải của chúng trong một bảng và sau đó khỏi phải tính lại khi gặp lại bài toán cháu đó. Qui hoạch động được áp dụng cho những bài toán tối ưu hóa (optimization problem). Qui hoạch động Quy hoạch động là một ký thuật thiết kế thuật toán trong đó: Bài toán được chia thành những bài toán con kích thước nhỏ hơn và giải chúng một cách độc lập, ghi lại các kết quả, để tổng hợp thành lời giải của bài toán ban đầu Khác với chia để trị: Trong giải thuật chia để trị: Các bài toán con độc lập, sau đó các bài toán con này được giải một cách đệ quy. Trong giải thuật quy hoạch động: Các bài toán con là không độc lập với nhau, nghĩa là các bài toán con cùng có chung các bài toán con nhỏ hơn. Ba giai đoạn của quy hoạch động Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất | CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT CHƯƠNG 5 Nội dung Qui hoạch động Giải thuật tham lam Giải thuật quay lui (backtracking) Giải thuật nhánh và cận Nội dung Kỹ thuật đệ qui hoặc ngay cả phương pháp chia để trị có thể phải giải nhiều lần một bài toán con, nên giảm hiệu quả Kỹ thuật qui hoạch động khắc phục hạn chế này bằng cách giải các bài toán con trước khi giải bài toán đã cho Kết quả các bài toán con được lưu trữ vào các bảng và sau đó khỏi phải tính lại khi gặp lại bài toán con đó. Trong thiết kế cần tìm được mối ràng buộc giữa bài toán cần giải và bài toán con, sự liên hệ thường là các hệ thức truy hồi Qui hoạch động là một phương pháp rất hiệu quả và được áp dụng cho những bài toán tối ưu hóa (optimization problem). Qui hoạch động (bỏ) Quy hoạch động (dynamic programming) giải các bài toán bằng cách kết hợp các lời giải của các bài toán con của bài toán đang xét. Phương pháp này khả dụng khi các bài toán con không độc lập đối với nhau, tức là khi .
