Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Chương 5: Phương pháp quy hoạch động Phương pháp phân tích và thiết kế chia để trị ở chương trước phát huy tác dụng rất mạnh, do nó xuất phát từ việc chia nhỏ bài toán ban đầu thành hai bài toán con cỡ gần bằng nhau để giải. | ChươNq5 PHƯƠNG PHÁP QUY HOẠCH ĐỘNG 5.1. Giới thiệu phương pháp quy hoạch động.133 5.1.1 Ví dụ so sánh với phương pháp chia đế trị. . . . 133 5.1.2 Một số ván đề trong phương pháp quy hoạch động 37 5.1.3 Kĩ thuật lập thuật toan theo quy hoạch động . 138 5.2. Bài toán nhân ma trận.140 5.2.1. Giới thiệu bài toán.140 5.2.2. Thiết kế thuật toán theo cách chia để trị.142 5.2.3. Thiết kế theó quy hoạch động.144 53. Ghi nhở hóa và tam giác hỏa . .150 5.3.1. Ghi nhớ hóa.150 5.3.2. Đa giác và tam gỉác hóa .151 5.4. Dãy con chung dàỉ nhất. . 157 5.5. Đường đí ngắn nhất.162 5.5.1. Nhắc lại một số khái niệm trong lí thuyết dồ thị 162 5.5.2. Đường đi ngắn nhất giữa hai cặp đỉnh.163 5.5.3. Thuật toán Floyd . 164 5.5.4. Thuật toán Warshall.167 5.6. Bài toán đường đỉ của người bán -hàng.168 5.7. Bài tập. . 173 Phương pháp phận tích vã thiết kế chĩa để trị ỏ chương trước phát huy tác dựng rất mạnh do nó xuất phát từ việc chia nhồ bài toán ban đầu thành hai bài toán con có cỡ gần bằng nhau để giải. Trong thực tế không có giới hạn chia bài toán thành bao nhiêu bài toán con đế giải cũng như cỡ của các bài toán con khắc nhau như thế nào. Nhưng có một giới hạn quan trọng mà ta không để ý là không hai bài toán con nào giao nhau và việc giải chúng cho ta nghiệm trực tiếp của bài toán ban đầu Phương pháp quy hoạch động nghiên cứu ỏ chương này thường liên quan tới những bài toán con có phần giao nhau ỉà bắt buộc. Phần 5.1. Giới thiệu phương pháp quy hoạch động 133 sau đây ta sẽ xem xét hai điều kiện cần đế áp dụng phương pháp quy hoạch động. ỹ.l. GIỚI THIỆU PHƯƠNG PHÁP QUY HOẠCH ĐỘNC Một cách định nghía trừu tượng cho phương pháp quy hoạch động là tìm những giá trị cực trị cực đại hoặc Cực tiểu trên một hàm mà hàm này có đối sốlầ một hàm khác Phương pháp quy hoạch động nói chung có thể xem như phương pháp suy nghĩ hoặc quy hoạch với nó thông qua việc tìm những nghiệm tối ưu cho một phần hoặc tất cả nhũng tập con của một tập hợp thi có thể tìm được nghiệm tối ưu của cả tập hợp. Định nghĩa .
