Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Chương 6: Phương pháp tham Phần lớn những bài toán trong chương trước là ta tìm nghiệm tối ưu trong tất cả khả năng nghiệm. Ta nhớ lại với phương pháp quay lui như trong thiết kế các thuật toán để tìm nghiệm tối ưu cần thiết phải tìm tất cả những nghiệm tối ưu của tất cả những bài toán con | ChươNCịò PHƯƠNG PHÁP THAM 6.1. Lập chương trình cho nhíểu hoạt động.176 6.1.1. Thuật toán tham lâp lịch hoạt động.177 6 1.21 Tính đúng đắn củã thuật toẩn. 179 6.2. Mã Huffman. .180 6.2.1. Phân tích và thiết kế thuật toán. . 181 6.2.2. Chứng minh tính đúng đắn của thuật toán . . . 184 6.3. Bài toán ba lữ. 187 6.4. Bải toán cây bao trùm nhỏ nhất và thuật toán.192 6.4.1. Cây bao trùm nhỏ nhất .192 6.4.2. Tiếp cận thuật toán tìm cây bao trùm nhỏ nhất . 193 6.5. Thuật toán Kruskal.196 Phần lớn những bài toán trong chương trước là ta tìm nghiệm tối ưu toong tâ t cả các khả năng nghiệm. Ta nhớ lại với phương pháp quay lui như trong thiết kế các thuật toán để tìm nghiệm tối ưu cần thiết phải tìm tất cả những nghiệm tốì ưu của tất cả những bài toán con nhưng không may một số bài toán con lạí phải tính đi tính lại nhiều lần . Sự tính đi tính lại nhiều lần một bài toán con có thể khắc phục được bằng quy hoạch động nhưng thật không may quy hoạch động lại liên quan đến việc cần một lượng bộ nhớ đủ lớn chõ việc giữ những kết quả tính được. Tư tưởng để khắc phục điều này là thuật toán tiến đêh một trong những trường hợp con của bài toán và giải duy nhất với nó với hỉ vọng rằng nó sẽ cho lời giải đúng. Sự lựa chọn những trường hợp con này được thực hiện hoàn toàn theo tiêu chuẩn chủ quan cục bộ cho sự tới ưu. Ví dụ như những thuật toán tham ỉam luôn luôn chỉ đến cách chọn tốt nhất tại thời điểm đó như một cách tự nhiên cho đến những giai đoạn sau mới phát hiện ra rằng sự lựa chọn như vậy là không phù hợp. 175 Những thuật toán tham được tạo ra râ t dễ dàng tương ứng với việc thể hiện nó trong ngôn ngữ lập trình không phức tạp nhưng có nhược điểm là đôi khi chúng không đảm bầo nghiệm đúng bài toán ban đầu. Nhược điếm này không làm giảm sự có ích của loại thuật toán này vì những thuật toán loại này tính toán râ t nhanh và tìm được lời giải bái toán những lời giải này cũng gần tối ưu. Ví dụ trong râ t nhiều những bài toán thực tế ta không nghiên cứu được tất cả các trường hợp đành .
