Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quy hoạch động và giải thuật tham lam (Quy hoạch động (Bốn bước của quy…
Quy hoạch động và giải thuật tham lam
Quy hoạch động
Định nghĩa
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ào toán đang xét
Khả dụng khi các bài toán con không độc lập với nhau, tức là khi các bào toán con có dùng chung những bài toán cháu subsubproblem
Giải các bào 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 lặp đi lặp lại bài toán cháu đó
Áp dụng cho những bài toán tối ưu hóa optimization problem
Bốn bước của quy hoạch động
Đặc trưng hóa cấu trúc của lời giải tối ưu
Định nghĩa giá trị của lời giải tối ưu một các đệ quy
Tính trị của lời giải tối ưu theo kiể từ dưới lên
Cấu tạo lời giải tối ưu từ những thông tin đã được tính toán
Ví dụ
Nhân xâu ma trận
Bài toán chuỗi con chung dài nhất
Bài toán cái túi
Giải thuật Warshall và giải thuật Floyd
Giải thuật Watshall
Giải thuật Floyd
giải bài toán những lối đi ngắn nhất giữa những cặp có độ tính toán phức tạp O(V3)
Thành phần của quy hoạch động
Tiểu cấu trúc tối ưu potimal substructure
Nếu lời giải tối ưu chứa trong nó nhưng lời giải tối ưu của những bài toán con
Các bài toán con trùng lặp overlapping subproblem
Khi một giải thuật đệ quy gặp lại cùng một bài toán con nhiều lần ta bảo rằng bài toán tối ưu hóa có những bài toán con trùng lặp
Quy hoạch động lợi dụng bài toán con trùng lặp bằng cách giải 1 lần và cất vào một bảng và bảng này sẽ đc tham khảo ở những lần sau
Các giải thuật đề quy làm việc từ trên xuống tỏng khi các giải thuật quy hoạch động làm việc từ dưới lên
Giải thuật tham lam
Các giải thuật tối ưu hóa đừng đi qua một số bước với một tập các khả năng lựa chọn tại mỗi bước. Mội giải thuật thường chọn 1 khả năng mà xem như tốt nhật tại lúc đó
Tức là giải thuật chọn một khả năng tối ưu cục bộ với hy vọng sẽ dẫn đến một lời giải tối ưu toàn cục
Ví dụ
Bài toán xếp cái lịch cho các hoạt động
Bài toán cái túi dạng phân số
Bài toán mã Huffman
Giải thuật Prim để tính cây bao tùm tối thiểu