tailieunhanh - Bài giảng Cơ sở lập trình nâng cao - Chương 4: Phương pháp thiết kế thuật toán – quay lui

Bài giảng cung cấp cho người học các kiến thức: Phương pháp thiết kế thuật toán – quay lui, ưu điểm và khuyết điểm, sơ đồ cài đặt, phương pháp Quay lui,. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. chi tiết nội dung bài giảng. | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – QUAY LUI – Chương 4 2 Nội dung Giới thiệu Phương pháp Sơ đồ cài đặt Các ví dụ Ưu điểm và khuyết điểm 3 Hình ảnh 4 Giới thiệu Định nghĩa [Quay lui – Backtracking]: Quay lui là một phương pháp thiết kế thuật toán để tìm nghiệm của bài toán bằng cách xét tất cả các phương án. Một phương án gồm nhiều thành phần, và phương pháp quay lui sẽ xây dựng từng thành phần trong mỗi bước. Trong quá trình xây dựng thành phần thứ i (tìm nghiệm cho thành phần thứ i), nếu không thể xây dựng được thì quay lại chọn nghiệm khác cho thành phần thứ (i-1) 5 Bài toán Phát biểu bài toán: Giả sử nghiệm của bài toán cần tìm có dạng X=(x1, x2, , xk, ), trong đó xi là 1 thành phần nghiệm của bài toán xi có một miền giá trị Di nào đó (xi Di). Số lượng thành phần xi có thể xác định hay không xác định Bài toán có những ràng buộc là F Yêu cầu: Hãy xây dựng 1 nghiệm hay tất cả các nghiệm của bài toán thỏa điều kiện F 6 Phương pháp Phương pháp Quay lui Phương pháp Quay lui xây dựng dần nghiệm X của bài toán: Bắt đầu từ x1 được chọn ra từ tập D1, rồi đến x2 được chọn ra từ tập D2, . bằng cách thử mọi khả năng có thể xảy ra. Một cách tổng quát: Nếu chúng ta đã xác định được lời giải bộ phận gồm (i-1) thành phần X(i-1) = (x1, x2, ., xi-1), bây giờ chúng ta tìm giá trị cho thành phần xi bằng cách xét mọi khả năng có thể có của xi trong tập Di. Với mỗi khả năng j (j Di), chúng ta kiểm tra xem có thể thỏa điều kiện là nghiệm thành phần của bài toán không 7 Phương pháp Có 2 khả năng xảy ra: Nếu khả năng j thỏa điều kiện thì Gán xi = j Tiếp theo tìm nghiệm cho thành phần xi+1 Nếu đã thử mọi khả năng của j mà không thỏa điều kiện bài toán thì có nghĩa là đi theo con đường X(i-1) = (x1, x2, ., xi-1) sẽ không thể dẫn đến kết quả. Chúng ta quay về bước trước để xác định lại xi-1 . | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – QUAY LUI – Chương 4 2 Nội dung Giới thiệu Phương pháp Sơ đồ cài đặt Các ví dụ Ưu điểm và khuyết điểm 3 Hình ảnh 4 Giới thiệu Định nghĩa [Quay lui – Backtracking]: Quay lui là một phương pháp thiết kế thuật toán để tìm nghiệm của bài toán bằng cách xét tất cả các phương án. Một phương án gồm nhiều thành phần, và phương pháp quay lui sẽ xây dựng từng thành phần trong mỗi bước. Trong quá trình xây dựng thành phần thứ i (tìm nghiệm cho thành phần thứ i), nếu không thể xây dựng được thì quay lại chọn nghiệm khác cho thành phần thứ (i-1) 5 Bài toán Phát biểu bài toán: Giả sử nghiệm của bài toán cần tìm có dạng X=(x1, x2, , xk, ), trong đó xi là 1 thành phần nghiệm của bài toán xi có một miền giá trị Di nào đó (xi Di). Số lượng thành phần xi có thể xác định hay không xác