Phương pháp sinh và thuật toán quay lùi

Chia sẻ: Nguyen Dang Tan | Ngày: | Loại File: PPT | Số trang:68

Thêm vào BST

Báo xấu

588
lượt xem 113
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hàm đệ quy là hàm mà trong thân hàm lại gọi chính nó. • Hàm đệ quy kém hiệu qủa vì: tốn bộ nhớ va gọi hàm qúa nhiều lần. Tuy nhiên viết hàm đệ quy rất ngắn gọn.Tuy nhiên nhiều giải thuật vẫn phải dùng kỹ thuật đệ quy vì việc khử đệ quy không dễ dàng. • Vòng lặp và stack là những kỹ thuật giúp khử giải thuật đệ quy.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phương pháp sinh và thuật toán quay lùi

Chương 8 Phương pháp sinh và Thuật toán quay lui.
Mục tiêu • Giải thích được sinh dữ liệu là gì. • Biết sử dụng một số giải thuật sinh. • Biết sử dụng giải thuật quay lui để giải một số bài toán. 2
Nội dung • Ôn tập • Bài toán tổ hợp • Phương pháp sinh • Thuật toán quay lui 3
Ôn tập • Hàm đệ quy là hàm mà trong thân hàm lại gọi chính nó. • Hàm đệ quy kém hiệu qủa vì: tốn bộ nhớ va gọi hàm qúa nhiều lần. Tuy nhiên viết hàm đệ quy rất ngắn gọn.Tuy nhiên nhiều giải thuật vẫn phải dùng kỹ thuật đệ quy vì việc khử đệ quy không dễ dàng. • Vòng lặp và stack là những kỹ thuật giúp khử giải thuật đệ quy. 4
8.1- Bài toán tổ hợp • Có n biến x1, x2, x3, ..., xn • Mỗi biến xi có thể mang trị thuộc về 1 tập hợp Pi  Miền của bài toán là tập tích P1 x P2 x P3 x ... x Pn • Phép gán trị (assignment): Là một bộ trị a1, a2, a3, ..., an Trong đó a1  ai ∈ Pi • Một lời giải của bài toán là 1 phép gán trị. • Một phép gán trị được gọi là một cấu hình. 5
Bài toán tổ hợp Các phép gán x y z • Ví dụ: Có 3 nhân viên bảo vệ a b c làm 3 ca sáng, chiều tối. Trong a c b 1 ca chỉ có 1 bảo vệ. Hỏi các b a c cách bố trí các bảo vệ? b c a • Mã hóa bài toán: c a b {x, y, z} là tập biến có thứ tự c b a mô tả cho 3 ca :sáng, chiều, tối theo thứ tự. Số lời giải là số hoán vị của tập hợp 3 Miền trị của 3 biến là phần tử này: { a,b,c } mô tả cho 3 bảo vệ. 3*2*1 = 3! = 6. Bài toán liệt kê các hoán vị của một tập hợp n phần tử có thứ tự có độ phức tạp n! 6
Bài toán tổ hợp x y z a d m Số phép gán: a d n 3 * 2 * 3 = 18 • Ví dụ: Tìm số a d t a e m chuỗi có độ dài 3 a e n Tích của các ký tự xyz với a e t số phần tử b d m x ∈ { a,b,c}, của các b d n b d t miền trị y ∈ { d,e}, b e m b e n z ∈ { m,n,t} b e t c d m • Nhận xét: 3 biến c d n Độ phức tạp: nm với c d t có 3 miền trị n: số phần tử trung bình c e m của mỗi miền trị, khác nhau c e n m: là số miền trị c e t 7
Bài toán tổ hợp Bài toán tổ hợp có độ phức tạp là n! hoặc nm Làm thế nào tạo ra các phép gán trị ?  Phương pháp sinh. 8
8.2- Phương pháp sinh (Generating) 9
8.2.1- Định nghĩa • Sinh: Tạo ra dữ liệu. • Phương pháp sinh: Từ dữ liệu ban đầu, sinh ra dữ liệu kế tiếp cho đến khi kết thúc. • Dùng để giải quyết bài toán liệt kê của lý thuyết tổ hợp. • Điều kiện của thuật toán sinh: (1) Có thể xác định 1 thứ tự tập các cấu hình của tổ hợp (thứ tự của các phép gán trị, thường dùng thứ tự từ điển). (2)Có một cấu hình cuối (điều kiện kết thúc của giải thuật). (3) Có một cách để suy ra được cấu hình kế tiếp. 10
Thứ tự từ điển • S1=“1234589” • S2=“1235789” • S1 < S2 nếu có 1 vị trí i tại đó S1[ i ] < S2[ i ] 11
8.2.2- Một ví dụ x y z Dùng thứ Bài toán:Tìm số chuỗi có a d m tự từ điển a d n độ dài 3 ký tự xyz với để so sánh a d t x ∈ { a,b,c}, y ∈ { d,e}, a e m các phép z ∈ { m,n,t} a e n gán trị. a e t Cấu hình ban đầu: trị đầu b d m Ví dụ: tiên của mỗi miền trị b d n b d t adm < adn b e m Cách sinh:Lấy trị kết tiếp b e n của mỗi miền trị theo cơ chế b e t vòng tròn c d m c d n c d t Cấu hình cuối: trị cuối cùng c e m của mỗi miền trị c e n c e t 12
8.2.3- Thuật toán sinh tổng quát. Procedure Generate Begin c = InitialConfigure; //cấu hình ban đầu // xử lý cấu hình đang có Process (c); if c=LastConfigure then Stop:=true else stop := false; while (not stop) do Begin //Sinh cấu hình kế tiếp từ cấu hình đang có c=getNextConfigure(c); Process (c); // xử lý cấu hình này if c= LastConfigure then stop = true; End; End; 13
8.2.4- Bài toán chuỗi 3 ký tự 14
Bài toán chuỗi 3 ký tự... 15
Bài toán chuỗi 3 ký tự... Bài toán:Tìm số chuỗi có độ dài 3 ký tự xyz với x ∈ { a,b,c}, y ∈ { d,e}, z ∈ { m,n,t} 16
8.2.5- Bài toán liệt kê các tập con của 1 tập gồm n phần tử • Mã hóa tập biến: Tập biến gồm n biến ký tự theo th ứ t ự các phần tử  mảng n ký tự. • Miền trị của mỗi biến {‘0’, ‘1’}. ‘0’ mô tả cho tình huống phần tử này không có trong tập con, ‘1’: mô tả cho tình huống phần tử này có mặt trong tập con. • Với tập cha là 4 phần tử X={ a, b, c, d }, có th ể dùng mảng “0111” mô tả cho tập con { b,c,d }.  Mỗi tập con được biểu diễn là một chuỗi (xâu) nhị phân. • Trạng thái khởi tạo: “0000” mang ý nghĩa tập tr ống. • Trạng thái kết thúc: “1111” mang ý nghĩa là tập cha. 17
Bài toán liệt kê các tập con.... • Với tập cha gồm 4 phần tử, có 24 tập con b với các biểu diễn: vars p(b) vars p(b) 0000 0 1000 8 Với thứ tự 0001 1 1001 9 từ điển, tập con 0010 2 1010 10 sau lớn hơn tập con trước 1 đơn vị 0011 3 1011 11 theo cách tính 0100 4 1100 12 chuỗi nhị phân 0101 5 1101 13 0110 6 1110 14 0111 7 1111 15 18
Bài toán liệt kê các tập con.... • Cách cộng thêm 1 vào chuỗi nhị phân: 0000 0001 • Gọi i : vị trí bit 0 đầu tiên từ 0001 0010 bên phải. • Cho các bit 1 bên phải vị trí i 0011 0100 thành 0 •Cho bit i mang trị 1 0111 1000 i= n-1; while (i>=0 && vars[i]==‘1’) vars[i--] = ‘0’; vars[i] = ‘1’; 19
Bài toán liệt kê các tập con.... 20