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

Chia sẻ: Mucnang222 Mucnang222 | Ngày: | Loại File: PDF | Số trang:110

Thêm vào BST

Báo xấu

43
lượt xem 6
download

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

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ủ đề:

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

Lưu

Nội dung Text: 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 LUI 4.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ự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 của quá trình tìm kiếm sau khi và trả lại trạng thái cũ sau lời gọi Try(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ến trạ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án liệ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ài toá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án quay 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ụng 4.2.1. Đƣa ra các dãy nhị phân độ dài n 1) 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 n 2) Thiết kế thuật toán Biểu diễn dãy nhị phân dưới dạng (b1, b2,…, bn), trong đó bi{0,1}. 87
Mỗ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 được chấ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("\n"); 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ới mỗ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ãy biế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án giá 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ị 1 cho 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(); else try(i+1); b[j]:=true; } } main() { init(); try(1); getch(); } 4.2.3. Đƣa ra các tập con của tập gồm n số nguyên 1) Bài toán Cho X = {x1, x2, ..., xn}, trong đó xi (i=1, 2, ...,n) là các số nguyên. Hãy đưa ra tất cả các tập con gồm m (m
a2= a’2 ak-1 = a’k-1 ak < a’k. Chẳng hạn X = {1, 2, 3, 4, 5} thì các tập con gồm 3 phần tử của X được liệt kê theo thứ tự từ điển như sau: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 Như vậy tập con đầu tiên trong thứ tự là (1, 2, ..., m) và tập con cuối cùng là (n - m +1, n - m + 2, ..., n). Từ đó suy ra các giá trị đề cử cho ai là từ ai-1+1 đến n - m +i. Để điều này đúng cho cả trường hợp i =1 cần có a0 = 0. Các giá trị đề cử này mặc nhiên được chấp nhận. Tổ chức dữ liệu: - Mảng x: dãy số nguyên đã cho - Mảng a: lưu trữ một tập con gồm m phần tử của tập chỉ số {1, 2, ..., n} Các hàm - Hàm init(): nhập n, m và khởi tạo - Hàm result(): đưa ra tập con gồm m phần tử của x vừa tìm được - Hàm Try(i): xác định thành phần thứ i của tập con. init() { scanf(n,m) 91
a[0]=0; end; result() { for(i=1;i
xi = j nghĩa là quân hậu dòng i được xếp vào cột j. Các giá trị đề cử cho xi là từ 1 đến 8. Giá trị j là được chấp nhận nếu ô (i, j) chưa bị quân hậu nào chiếu đến (quân hậu có thể ăn ngang, dọc và hai đường chéo). Để kiểm soát được điều này, ta cần phải ghi nhận trạng thái của bàn cờ trước cũng như sau khi xếp được một quân hậu. Việc kiểm soát theo chiều ngang là không cần thiết vì mỗi dòng được xếp đúng một quân hậu. Việc kiểm soát chiều dọc được ghi nhận nhờ dãy biến aj với qui ước rằng aj bằng 1 nếu cột j còn trống. Hai đường chéo đi qua ô (i, j) thì một đường chéo gồm những ô có i + j không đổi, còn một đường chéo gồm những ô có i - j không đổi (2 i+j  16, -7 i-j  7). Từ đó đường chéo thứ nhất được ghi nhận nhờ dãy biến bj (2 j  16) và đường chéo thứ hai nhờ nhờ dãy biến cj (-7 j  7) với qui ước các đường này còn trống nếu biến tương ứng có giá trị 1. Các biến trạng thái aj, bj, cj được khởi gán giá trị 1 trong hàm Init(). Như vậy giá trị j được chấp nhận khi và chỉ khi cả 3 biến ai, bi+j, ci-j cùng có giá trị 1. Các biến này phải được gán lại giá trị 0 khi xếp xong quân hậu thứ i và được trả lại giá trị 1 sau khi gọi Result() hay Try(i+1). Tổ chức dữ liệu: - Mảng x để lưu trữ cách xếp 8 quân hậu tìm được. - Mảng c với các phần tử c[j] để ghi nhận trạng thái cột j (c[j]=1 thì cột j chưa có quân hậu nào xếp, c[j]=0 thì cột j đã có quân hậu xếp) - Mảng ct để ghi nhận trạng thái đường chéo tổng i+j: + ct[i+j]=1 thì đường chéo i+j chưa có quân hậu nào chiếu đến + ct[i+j]=0 thì đường chéo i+j đã có quân hậu chiếu đến - Mảng ch để ghi nhận trạng thái đường chéo hiệu i-j: Để chỉ số của mảng chạy từ 1 nên với i-j chạy từ -7 đến 7 ta đặt tương ứng với i-j+8 chạy từ 1 đến 15. + ct[i-j+8]=1thì đường chéo i-j chưa có quân hậu nào chiếu đến + ct[i-j+8]=0 thì đường chéo i-j đã có quân hậu chiếu đến Các hàm: init() //Hàm khởi tạo { for(i=1;i
for(i=2;i
G = (V, E) là đơn đồ thị (có hướng hoặc vô hướng). V = {1,. ., n} là tập các đỉnh, E là tập cạnh (cung). Với s, t  V, tìm tất cả các đường đi từ s đến t. Các thuật toán tìm kiếm cơ bản : Thuật toán DFS : Tìm kiếm theo chiều sâu. Thuật toán BFS : Tìm kiếm theo chiều rộng. 2) ThiÕt kÕ thuËt to¸n * Thuật toán DFS tiến hành tìm kiếm trong đồ thị theo chiều sâu. Thuật toán thực hiện việc thăm tất cả các đỉnh có thể đạt được cho tới đỉnh t từ đỉnh s cho trước. Đỉnh được thăm càng muộn sẽ càng sớm được duyệt xong (cơ chế LIFO –Vào sau ra trước). Nên thuật toán có thể tổ chức bằng một thủ tục đệ quy quay lui. Input: G = (V,E), s, t Output: Tất cả các đường đi từ s đến t (nếu có). DFS (s) { for ( u = 1; u
Daxet[u] = 1 , u đã được thăm. Daxet[u] = 0 , u chưa được thăm. Mảng Daxet[] lúc đầu khởi t?o bằng 0 tất cả. Điều kiện chấp nhận được cho đỉnh u chính là u kề với v (a vu = 1) và u chưa được thăm ( Daxet[u] = 0). Để ghi nhận các đỉnh trong đường đi, ta dùng một mảng một chiều Truoc[ ], với qui ước : Truoc[u] = v với v là đỉnh đứng trước đỉnh u, và u kề với v Ta khởi tạo mảng Truoc[ ] bằng 0 tất cả. Thuật toán đượcc làm mịn hơn : Input G = (aij)nxn , s, t Output Tất cả các đường đi từ s đến t (nếu có). DFS(s) { daxet[s] = 1; for( u = 1;u
{ printf(t,"
ngược lại từ t đến các đỉnh trước t trong từng các tập trước cho đến khi gặp s. Trong thuật toán BFS, đỉnh được thăm càng sớm sẽ càng sớm trở thành duyệt xong, nên các đỉnh được thăm sẽ được lưu tr? trong hàng đợi queue. Một đỉnh sẽ trở thành duyệt xong ngay sau khi ta xét xong tất cả các đỉnh kề của nó . Ta dùng một mảng Daxet[] để đánh dấu các đỉnh được thăm, Daxet[i]=0 là đỉnh i chưa được thăm, Daxet[i]= là đỉnh i đã được thăm. Mảng này được khởi động bằng 0 tất cả để chỉ rằng lúc đầu chưa đỉnh nào được thăm. Một mảng truoc[ ] để lưu trữ các đỉnh nằm trên đường đi ngắn nhất cần tìm (nếu có), với ý nghĩa Truoc[i] là đỉnh đứng trước đỉnh i trong đường đi. Mảng Truoc[ ] được khởi tạo bằng 0 tất cả để chỉ rằng lúc đầu chưa có đỉnh nào. Đồ thị sẽ được biểu diễn bằng ma trận kề : a =(aij) 1
Ta có thể thấy mỗi lần gọi DFS(s), BFS(s) thì mọi đỉnh thuộc cùng một thành phần liên thông với s sẽ được thăm, nên sau khi thực hiện hàm trên thì : • Truoc[t] = 0 : không tồn tại đường đi từ s đến t, • Ngược lại, có đường đi từ s đến t. Khi đó lời giải được cho bởi : t ← p1 = Truoc[t] ← p2 = Truoc[p1] ← … ← s . 4.2.6. Bài toán ngựa đi tuần 1) Bài toán Cho bàn cờ có n x n ô. Một con ngựa được phép đi theo luật cờ vua, đầu tiên được đặt x0 , y0. Một hành trình của ngựa là đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần. Hãy đưa ra các hành trình (nếu có) của ngựa. 2) ThiÕt kÕ thuËt to¸n Cách giải quyết rõ ràng là xét xem có thể thực hiện một nước đi kế nữa hay không. Sơ đồ đầu tiên có thể phát thảo như sau : 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; if( i < n2 ) Try(i+1); else Ghi nhận nghiệm; Hoàn trả trạng thái ; } } Để mô tả chi tiết thuật toán, ta phải qui định cách mô tả dữ liệu và các thao tác, đó là : - Biểu diễn bàn cờ . 99
- Các khả năng chọn lựa cho xi - Cách thức xác định xi theo j. - Cách thức gi nhận trạng thái mới, trả về trạng thái cũ. - Ghi nhận nghiệm. * Ta sẽ biểu diễn bàn cờ bằng 1 ma trận vuông cấp n: h[n][n] mà h[i][j] tương ứng với ô ở hàng i cột j (1 ≤ i, j ≤ n) và dùng các phần tử của ma trận để ghi nhận quá trình di chuyển của con ngựa với qui ước như sau: h[x][y] = 0: Ô ngựa chưa đi qua; h[x][y] = i : Ô ngựa đã đi qua ở bước thứ i (1  i  n2 ). * Các khả năng lựa chọn cho xi? Đó chính là các nước đi của ngựa mà xi có thể chấp nhận được. Với ô bắt đầu như trong hình vẽ, có tất cả 8 ô mà con ngựa có thể đi đến. Giả sử chúng được đánh số từ 0 đến 7 như hình sau : ( ô có dấu * là ô ở hàng x cột y nơi ngựa đang đứng) 4 3 5 2 * 6 1 7 0 Hình 4.1. Các ô mà ngựa có thể đi đến Một cách tương đối các ô mà ngựa có thể đi qua khi đang đứng ở ô là: Ô đánh số 0: Ô đánh số 1: Ô đánh số 2: Ô đánh số 3: Ô đánh số 4: Ô đánh số 5: Ô đánh số 6: Ô đánh số 7: 100
Ta dùng mảng a lưu trữ các sai khác về chỉ số hàng của các ô trên so với x và dùng mảng b lưu trữ caùc sai khác về chỉ số cột của các ô trên so với y thì mảng a và mảng b sẽ được khởi tạo như sau: Mảng a: a[0] = 2; a[1] = 1; a[2] = -1; a[3] = -2; a[4] = -2; a[5] = -1; a[6] = 1; a[7] = 2; Mảng b: b[0] = 1; b[1] = 2; b[2] = 2; b[3] = 1; b[4] = -1; b[5] = -2; b[6] = -2; b[7] = -1; Dùng một biến chỉ số k để đánh số các bước đi tiếp theo có thể thì việc duyệt các bước đi tiếp theo có thể được diễn tả là: for(k = 0; k
thái); và để hủy một nước đi thì ta gán h[u][v] = 0 (hoàn trả trạng thái). * Ma trận h ghi nhận kết quả nghiệm. Nếu có sao cho h = 0 thì không có đường đi , còn ngược là h chứa đường đi của ngựa. Thuật toán có thể mô tả như sau : Input n, //Kích thước bàn cờ x, y;//Toạ độ xuất phát ở bước i Output h; Try(i, x, y) { for(k = 0; k
init(); h[x0 ][y0 ] = 1; try(2,x0 , y0); } Với n=5 và x0=1, y0=1 thì thuật toán cho một trong các lời giải là: 1 6 15 10 21 14 9 20 5 16 19 2 7 22 11 8 13 24 17 4 25 18 3 12 23 Hình 4.2. Một lời giải Nếu chọn ô xuất phát chẳng hạn là (2,3) thì bài toán không có lời giải. 103
BÀI TẬP CHƢƠNG 4 1.Cho một dãy số nguyên a1, a2, ..., an và một số nguyên S. Liệt kê tất cả các cách phân tích S = ai1 + ai2 + ... + aik (ai1, ai2, ..., aik là các số của dãy đã cho) Hướng dẫn: Với mỗi giá trị k từ 1 đến n ta xây dựng các tập con gồm k phần tử của dãy số nguyên a1, a2, ..., an. Với mỗi tập con này ta tính tổng các phần tử của nó, nếu tổng bằng S thì hiển thị tổng đó ra. Ta áp dụng thuật toán quay lui để liệt kê các cách phân tích S = ai1 + ai2 + ... + aik Sử dụng : - Mảng a để lưu trữ n số nguyên a1, a2, ..., an - Mảng b với các phần tử b[i] dùng để ghi nhận chỉ số của phần tử của mảng a. Phần tử có chỉ số này của mảng a được gán cho c[i]. - Mảng c dùng để lưu trữ tập con gồm k phần tử xây dựng được. - Hàm khoitao để nhập n, nhập S, nhập n số nguyên a1, a2, ..., an - Hàm Try để xây dựng các tập con gồm k phần tử. - Hàm ht để hiển thị ra tổng thoả mãn điều kiện. Với mỗi tập con gồm k phần tử lấy từ n số nguyên a1, a2, ..., an, hàm ht sẽ kiểm tra xem tổng của k phần tử này có bằng S không? Nếu bằng thì hiển thị tổng đó ra. try(int i) {int j; for(j=b[i-1]+1;j
for(k=1;k