Tiếp nội dung phần 1 Bài giảng Thiết kế và đánh giá thuật toán: Phần 2 cung cấp cho người học các kiến thức cơ bản như: Kỹ thuật quay lui; Kỹ thuật nhánh và cận; Kỹ thuật quy hoạch động. Mời các bạn cùng tham khảo! | Chƣơng 4 KỸ THUẬT QUAY LUI . Nội dung kỹ thuật Nét đặc trưng của kỹ thuật quay lui là các bước hướng tới lời giải hoàn toàn được làm thử. Tại mỗi bước nếu có một lựa chọn được chấp nhận thì ghi nhận lựa chọn này và tiến hành các bước thử tiếp theo. Ngược lại nếu không có lựa chọn nào thích hợp thì làm lại bước trước xoá bỏ sự ghi nhận và quay về chu trình thử các lựa chọn còn lại. Hµnh éng nµy -îc gäi lµ quay lui thuật toán sử dụng kỹ thuật này là thuật toán quay lui. Lời giải của bài toán thường được biểu diễn bằng một bộ gồm n thành phần x x1 . xn phải thoả mãn các đ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 xi. Nhu vậy nội dung chính của kỹ thuật này là việc xây dựng dần các thành phần xi bằng cách thử tất các khả năng. Giả sử đã xác định được i -1 thành phần x1 x2 xi-1 mà ta sẽ gọi là lời giải bộ phận cấp i- 1 bây giờ ta xác định thành phần xi bằng cách duyệt tất cả các khả năng có thể đề cử cho nó đánh số các khả năng từ 1 đến ni . Với mỗi khả năng j kiểm tra xem j có chấp nhận được không. Xảy ra hai trường hợp - Nếu chấp nhận j thì xác định xi theo j. Sau đó nếu i n thì ta được một cấu hình còn trái lại ta tiến hành xác định xi 1. - Nếu thử tất cả các khả năng mà không có khả năng nào chấp nhận được thì quay lại bước trước để xác định lại xi-1. Điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đã đi qua những khả năng nào đã thử để tránh trùng lặp. Rõ ràng những thông tin này cần được lưu trữ theo cơ cấu ngăn xếp Stack- Vào sau ra trước . Vì thế kỹ thuật này rất phù hợp với việc lập trình trên một ngôn ngữ cho phép gọi đệ qui. Bước xác định xi có thể diễn tả qua hàm được tổ chức đệ qui dưới đây Try i for j 1 j if i n else try i 1 Phần quan trọng nhất trong hàm trên là việc đưa ra một danh sách các khả năng đề cử và việc xác định giá trị biểu thức thông thường giá trị này ngoài việc phụ thuộc j còn phụ thuộc vào việc đã chọn các khả năng tại i -1 bước trước. Trong những trường hợp như vậy cần ghi nhớ trạng thái mới
