Bài giảng Phương pháp sinh và thuật toán quay lui

Chương 8 Phương pháp sinhvà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. Nội dung Ôn tập Bài toán tổ hợp Phương pháp sinh Thuật toán quay lui Ô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. 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. Bài toán tổ hợp Ví dụ: Có 3 nhân viên bảo vệ làm 3 ca sáng, chiều tối. Trong 1 ca chỉ có 1 bảo vệ. Hỏi các cách bố trí các bảo vệ? Mã hóa bài toán: {x, y, z} là tập biến có thứ tự mô tả cho 3 ca :sáng, chiều, tối theo thứ tự. Miền trị của 3 biến là { a,b,c } mô tả cho 3 bảo vệ. Các phép gán x y z a b c a c b b a c b c a c a b c b a Số lời giải là số hoán vị của tập hợp 3 phần tử này: 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! Bài toán tổ hợp Ví dụ: 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} Nhận xét: 3 biến có 3 miền trị khác nhau Số phép gán: 3 * 2 * 3 = 18 Tích của các số phần tử của các miền trị Độ phức tạp: nm với n: số phần tử trung bình của mỗi miền trị, m: là số miền trị 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.2- Phương pháp sinh(Generating) 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. Thứ tự từ điển S1=“1234589” S2=“1235789” S1 =0 && vars[i]==‘1’) vars[i--] = ‘0’; vars[i] = ‘1’; Bài toán liệt kê các tập con.... Bài toán liệt kê các tập con.... Thêm dòng: delete[ ] vars; Thêm dòng: Stop = LastConfigure(vars,n); Bài toán liệt kê các tập con.... Bài toán liệt kê các tập con.... Nhận xét: Có thể tối ưu lại chương trình để bớt đi các vòng lặp. Bài toán liệt kê các tập con.... Kết hợp việc tìm cấu hình kế với việc kiểm tra ngưng lặp Bài toán liệt kê các tập con.... Thêm dòng: delete[ ] vars; Bài tập Viết chương trình liệt kê các tập con của tập { a,b,c,d,e,f,g,h } Xuất theo dạng [] [a] [a,b] ... 8.2.6- Bài toán tập con k-phần tử Liệt kê các tập con k phần tử của tập n phần tử. Ví dụ: Các tập con 3 phần tử của tập { 1,2,3,4,5 } là: { 1,2,3 } { 2,3,4 } { 1,2,4 } { 2,3,5 } { 1,2,5 } { 2,4,5 } { 1,3,4 } { 3,4,5 } { 1,3,5 } { 1,4,5 } C53 = 5!/ (3! * (5-3)!) = 5! / (3! * 2!) = 4*5/2 = 10 Tổ hợp n chập k Bài toán tập con k-phần tử Ánh xạ tập hợp bất kỳ n phần tử vào tập X={ 1,2...n } Một tập con k phần tử của X là một bộ có thứ tự a1 a2 a3 ..... ak với 1≤ a1a[j+1]) j--; Tìm vị trí đầu tiên k đi ngược từ cuối tập trị với a[k] > a[j] 1 3 4 2 ( k=3)  k=n; while (a[j]>a[k]) k--; Hoán vị a[j] với a[k] 1 4 3 2 Lật ngược đoạn aj+1 ... an 1 4 2 3 trạng thái kế tiếp Bài toán hoán vị {1,2,3,4,5,..., n} {n,..., 5,4,3,2,1} Bài toán hoán vị Tìm chỉ số lớn nhất j mà aj a[j] Hoán vị a[j], a[k] Đảo ngược nhóm trị a[j+1],... a[n] Bài toán hoán vị Thêm dòng: delete[ ] vars; Bài toán hoán vị - Kết qủa 4!= 24 hoán vị Bài tập Tạo file văn bản hoanvi.out có dạng Dòng đầu: 1 số nguyên n Các dòng sau là các hoán vị của tập n phần tử. Ví dụ: 5 1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 ............ 8.2.8- Bài toán chia 1 số nguyên thành tổng các số nguyên bé hơn Ví dụ: n=7 Các kết qủa 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 Cách chia: Số trước >= số sau. Ngược thứ tự từ điển Tại 1 thời điểm, số phần tử là k Bắt đầu: k=1, kết thúc: k=n Trạng thái đầu: 1 trị là n Trạng thái cuối: dãy n các số 1 Bài toán chia số nguyên n= 20 , trạng thái k=15 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 //số phải giảm là 4, số đầu tiên >1 từ bên phải, vị trí i=2 với chỉ số đi từ 1, giảm trị này 1 đơn vị 5 3 // số trị phải chia lại là 14 = số trị 1 bên phải +1= k-i+1=15-2+1=14 Số sẽ chia ra đi từ a[2]=3, 14/3 được 4 lần trị thêm vào là 3, dư 2 5 3 3 3 3 3 ( k=i+SốLầnBằngTrị) 5 3 3 3 3 3 2 //thêm phần dư vào cuối (k++) Đây chính là trạng thái kế tiếp- xong Bài toán chia số nguyên Bài toán chia số nguyên Bài toán chia số nguyên Bài toán chia số nguyên Thêm dòng: delete[ ] vars; Bài toán chia số nguyên 8.3-Thuật toán quay lui (backtracking) Không phải cấu hình nào cũng được sinh ra từ cấu hình trước đó một cách dễ dàng. Phương pháp sinh kế tiếp chỉ giải quyết được các bài toán đơn giản. Không phải cấu hình ban đầu và cấu hình kế tiếp được nhận diện một cách dễ dàng, nhiều khi phải chứng minh là tồn tại chúng. Với bài toán liệt kê phức tạp, thuật toán backtracking được áp dụng backtracking- Ý tưởng Tập biến x1 x2 x3 ... xn có thứ tự. Mỗi biến có thể có 1 miền trị riêng. Tại mỗi thời điểm, biến xi được tìm trị phù hợp. Nếu tìm được trị phù hợp thì tiếp tục sang biến xi+1 Ngược lại, tìm trị khác cho biến xi-1 Backtracking- Nhận xét Phải ghi nhớ các bước đã đi qua để có thể lùi về trạng thái trước đó  Cơ chế stack  Kỹ thuật đệ quy rất phù hợp. Nếu lưu trữ được các khả năng (trị của miền trị) đã được thử thì sẽ tránh được những việc lặp không cần thiết. Backtracking- Giải thuật tổng quát Tập biến X= (x1 x2 x3 ... xn), số biến n Tập miền trị D =(D1 D2 D3 ... Dn) void Try ( int i, X , n) { ∀j ∈ Di { if ( acceptable(xi, j)) { xi = j; if (i==n) Process (CấuHìnhCủa X) else Try (i+1, X, n) } } } Giải thuật tổng quát x1 x2 x3 x4 Bắt đầu D1 D2 D3 D4 for j= TrịĐầu ... TrịCuối của Di ......... Giải thuật tổng quát Bắt đầu x1 x2 x3 x4 D1 ( 2pt) D2 (2pt) D3 (2pt) D4 ( 3pt) for j= TrịĐầu ... TrịCuối của Di ... Một kết quả 8.3.1-Bài toán chuỗi bit Tập biến: char vars[], int n bit Nhận xét: Miền trị chung D={‘0’, ‘1’} Bit nào cũng được chấp nhận  Không cần kiểm tra acceptable(xi ,j) Bài toán chuỗi bit Thêm dòng: delete[ ] vars; Bài toán chuỗi 4 bit Bit 1 2 3 4 0 0 0 0  0000 1  0001 1 0  0010 1  0011 1 0 0  0100 1  0101 1 0  0110 1  0111 1 0 0 0  1000 1  1001 1 0  1010 1  1011 1 0 0  1100 1  1101 1 0  1110 1  1111 8.3.2-Bài toán liệt kê tập con k phần tử của tập n phần tử Thêm dòng: delete[ ] result; 8.3.3- Bài toán hoán vị Liệt kê các hoán vị của một tập n phần tử Một hoán vị được biểu diễn dạng p1p2p3...pn với pi ≠ pj với i ≠ j, mỗi pi sẽ nhận trị từ 1 .. n. Một trị j được gán cho pi nếu trị j này chưa được dùng  Cần quản lý trị j này đã dùng hay chưa  mảng B, n phần tử B[j] mang trị TRUE mô tả rằng trị j chưa được dùng  Ban đầu mọi B[j]= TRUE. Bài toán hoán vị Khi gán trị j cho pi, xong phải cho B[j]=FALSE. Sau khi thực hiện xong một lời giải (i==n) ( hay sau khi thực thi xong việc thử cho pi+1 để đi hết tập biến) phải trả lại B[j]= TRUE để dùng cho lần sau. Bài toán hoán vị Bài toán hoán vị Bài tập Làm lại các bài mẫu về giải thuật quay lui nhưng ghi kết qủa lên file. Bài tập Dùng giải thuật quay lui để sinh ra các mảng Result từ một ma trận m (hxc) các số nguyên sao cho: ma trận có h hàng thì mảng có h phần tử, trị của Result[i] là một trị của dòng m[i]. Hướng dẫn: Tập biến: mảng h phần tử kiểu int  int* Result; Miền trị của Result[i] là m[i] Bài tập Gọi hàm: Tóm tắt Kỹ thuật sinh: (1) Xác định trạng thái đầu của bài toán. (2) Xác định trạng thái kết thúc. (3) Xác định một thứ tự cho các trạng thái. (4) Tìm giải thuật đi từ trạng thái này sang trạng thái khác. Tóm tắt Giải thuật hồi quy- backtracking Tại 1 thời điểm, chỉ xét biến thứ i của tập biến Với mọi trị j trong miền trị của biến này 2.1- Nếu chọn được 1 trị hợp lệ thì Gán xi = j Xử lý biến ở vị trí i+1 Nếu i=0 thì bài toán không có lời giải. Tóm tắt Bài toán tổ hợp có độ phức tạp n! hoặc nm với n là số biến, m là số phần tử trung bình của các miền trị của các biến. Với n,m lớn, nếu phải xét hết mọi khả năng thì bài toán khó khả thi bằng máy tính vì chi phí qúa cao.