Bài giảng Môn toán - Giải thuật đệ qui quay lui

GIẢI THUẬT ĐỆ QUI QUAY LUI Quay lui là ban đầu ta tiến, tiến và tiến cho đến khi không tiến được nữa thì lui và lui cho đến khi có đường đi mới, ta lại tiến và tiến… lại lui, lui cho đến khi hết đường lui. Xong việc! NỘI DUNG Ý tưởng Mô hình Bài toán ngựa đi tuần Bài toán 8 quân hậu Bài tập Ý TƯỞNG Nét đặc trưng của phương pháp quay lui là các bước hướng tới lời giải cuối cùng của bài toán hoàn toàn được làm thử Tại một bước Nếu có một lựa chọn thì ghi nhận lại lựa chọn và tiến hành các bước thử tiếp theo Ngược lại thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về thử các lựa chọn còn lại Lời giải của bài toán thường biểu diễn bằng một vector gồm n thành phần x=(x1,x2,..,xn) phải thỏa mãn điều kiện nào đó Để chỉ ra lời giải x, ta phải xây dựng dần các thành phần lời giải xi Tại mỗi bước i: Đã xây dựng xong các thành phần: x1,x2,..xi-1 Xây dựng các thành phần xi bằng cách lần lượt thử tất cả các khả năng mà xi có thể chọn: MÔ HÌNH ĐỆ QUI QUAY LUI Nếu một khả năng j nào đó phù hợp cho xi thì xác định xi theo khả năng j. Thường phải thêm thao tác ghi nhận trạng thái mới của bài toán để hỗ trợ cho bước quay lui. Nếu i=n thì ta có được một lời giải, ngược lại thì tiến hành bước i+1 để xác định xi+1 Nếu không có khả năng nào chấp nhận được cho xi thì ta lùi lại bước trước (i-1) để xác định lại thành phần xi-1 MÔ HÌNH ĐỆ QUI QUAY LUI Mô hình của phương pháp quay lui có thể viết bằng thủ tục sau, với n là số bước cần thực hiện, k là số khả năng chọn xi Try(i) For (j=1->k) If (xi chấp nhận được khả năng j) Xác định xi theo khả năng j Ghi nhận trạng thái mới if(ik) if(xi chấp nhận được khả năng j) Xác định xi theo khả năng j Ghi nhận trạng thái mới If (i7) u=x+a[k]; v=y+b[k] if(18) -u=x+a[k];v=y+b[k] If ((1=4): n= '); readln(n); if n: Khong tim duoc loi giai '); readln; End. Nguyên tắc cơ bản của phương pháp tìm kiếm quay lui là như sau: - Chia tập tìm kiếm thành nhiều tập con, - Đánh số các tập con theo một tiêu chuẩn nào đó  có các tập P1, P2, . . ., Pk, - Với mỗi tập con nhận được: xác định một trong số các khả năng: - Không cần xét tiếp tập này, - Bài toán trở nên quá đơn giản và tìm được một lời giải, - Quay lại bước đầu với tập con này. - Tiêu chuẩn phân chia tập con: thỏa mãn một trong số các tính chất: Nhận được bài toán giống như ban đầu, nhưng có kích thước bé hơn, Nhận được bài toán đơn giản hơn, Nhận được bài toán với một số tính chất mới không có trong bài toán ban đầu. - Tiêu chuẩn đánh số các tập con: Theo thứ tự từ điển của một cấu trúc dữ liệu, Theo khả năng, triển vọng tồn tại nghiệm. - Tìm kiếm quay lui về bản chất gần giống các giải thuật đệ quy, nhưng có một số khác biệt cơ bản: Người lập trình điều khiển được quá trình duyệt theo các hướng có triển vọng, Không cần lưu toàn bộ các nút rẽ nhánh trong tìm kiếm, Có thể dễ dàng ngắt và quay lui khi cần thiết. Chính vì những đặc điểm trên nên giải thuật này thường áp dụng để giải các bài toán theo phương pháp nhánh và cận.