Bài giảng Thiết kế và đánh giá thuật toán: Phần 2 - ĐH Sư Phạm Kỹ Thuật Nam Định

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!
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Phần 2 - ĐH Sư Phạm Kỹ Thuật Nam Định Chương 4 KỸ THUẬT QUAY LUI4.1. 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ựachọ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àothí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áclự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ậttoá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âydự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ànhphầ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ầnxi 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 haitrườ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ấuhì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ữngkhả 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ưutrữ 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ợpvớ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 -1bước trước. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quátrình tìm kiếm sau khi và trả lại trạng thái cũ sau lời gọiTry(i+1). Các trạng thái này được ghi nhận nhờ một số biến tổng thể, gọi là biếntrạng thái. Sau khi xây dựng thủ tục đệ qui Try, đoạn chương trình chính giải bài toánliệt kê có dạng: main() { Init; Try(1); }trong đó Init là hàm khởi tạo các giá trị ban đầu (nhập các giá trị tham số, của bàitoán, khởi gán các biến trạng thái, biến đếm, ... Người ta đã chứng tỏ được rằng độ phức tạp tính toán của các thuật toánquay lui thường là hàm mũ. Ta công nhận điều này và trong các ví dụ áp dụng ta sẽkhông đặt vấn đề xác định độ phức tạp tính toán của các thuật toán. Kỹ thuật quay lui thường được áp dụng cho các bài toán liệt kê tổ hợp.4.2. Các ví dụ áp dụng4.2.1. Đưa ra các dãy nhị phân độ dài n1) Bài toán Cho một số nguyên dương n. Hãy đưa ra các dãy nhị phân độ dài n2) Thiết kế thuật toánBiểu diễn dãy nhị phân dưới dạng (b1, b2,…, bn), trong đó bi{0,1}. 87Mỗi thành phần bi có các giá trị đề cử là 0 và 1. Các giá trị này mặc nhiên đượcchấp nhận mà không phải thoả mãn điều kiện gì.Mảng b lưu trữ dãy nhị phân xây dựng được.Hàm Try(i) xác định thành phần thứ i và hàm Result() đưa ra dãy tìm được. result() { printf( ); for(i=1;i Ta nhận thấy rằng mỗi một hoán vị của tập X tương đương với một hoán vịcủa tập chỉ số {1, 2, ..., n} Biểu diễn hoán vị tập chỉ số dưới dạng a1, a2, …, an trong đó ai nhận giá trị từ1 đến n và ai  aj với i  j. Các giá trị từ 1 đến n được lần lượt đề cử cho ai, trong đógiá trị j được chấp nhận nếu nó chưa được dùng. Vì thế cần phải ghi nhớ đối vớimỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãybiến bj, trong đó bj bằng 1 nếu j chưa được dùng. Sau khi xác định ai theo j cần gángiá trị 0 cho bj. Khi thực hiện xong Result hay Try(i+1) cần phải gán lại giá trị 1cho bj.Tổ chức dữ liệu:- Mảng x: dãy số nguyên đã cho- Mảng a: lưu trữ một hoán vị của tập chỉ số {1, 2, ..., n}- Mảng b: lưu trữ trạng thái các phần tử của x với b[j]=1 thì x[j] đã được dùng, b[j]=0 thì x[j] chưa được dùng.Các hàm- Hàm init(): nhập n và khởi tạo- Hàm result(): đưa ra hoán vị vừa tìm được- Hàm Try(i): xác định thành phần thứ i của hoán vị.init() { scanf(n); for(i=1;i if(b[j]==1) { a[i]=j; b[j]=0; if(i==n) result(); ...