Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Các sơ đồ thuật toán - Nguyễn Khánh Phương

ột bước nữa tìm UCV
 mới vào vị trí thứ k-2, ... Nếu quay lại tận lời giải rỗng mà vẫn không tìm
 được UCV mới vào vị trí thứ 1, thì thuật toán kết thúc.
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
 Cây liệt kê lời giải theo thuật toán quay lui
 Gốc (lời giải rỗng)
 Tập UCV S1
 a1
 (a1)
 Tập UCV S2 khi đã có (a1)
 a2
 (a1, a2)
 Tập UCV S3
 khi đã có (a1, a2)
 (a1, a2, a3) a
 3
Tập UCV S4
 khi đã có (a1, a2 , a3)
 a4 a’4
 Thuật toán quay lui (đệ qui) Thuật toán quay lui (không đệ qui)
 void Bactrack(int k) void Bactraking ( ) 
 { {
 <Xây dựng Sk là tập chứa các ứng cử viên cho vị k=1;
 trí thứ k của lời giải>; ;
 for y Sk //Với mỗi UCV y từ Sk while (k > 0) {
 {
 while (Sk  ) {
 ak = y;
 ak  Sk; // Lấy ak từ Sk
 if (k == n) ; if then ;
 else Backtrack(k+1); 1 2 k
 else {
 }
 k = k+1;
 }
 ;
 Lệnh gọi để thực hiện thuật toán quay lui là: }
 Bactrack(1); } 
 k = k - 1; // Quay lui
• Nếu chỉ cần tìm một lời giải thì cần tìm cách }
 }
 chấm dứt các thủ tục gọi đệ qui lồng nhau
 sinh bởi lệnh gọi Backtrack(1) sau khi ghi Lệnh gọi để thực hiện thuật toán quay lui là: 
 nhận được lời giải đầu tiên. Bactraking ( );
• Nếu kết thúc thuật toán mà ta không thu
 được một lời giải nào thì điều đó có nghĩa là NGUYỄN KHÁNH PHƯƠNG
 bài toán không có lời giải. Bộ môn KHMT – ĐHBK HN
Hai vấn đề mấu chốt
• Để cài đặt thuật toán quay lui giải các bài toán tổ hợp cụ thể
 ta cần giải quyết hai vấn đề cơ bản sau:
 – Tìm thuật toán xây dựng các tập UCV Sk
 – Tìm cách mô tả các tập này để có thể cài đặt thao tác liệt kê
 các phần tử của chúng (cài đặt vòng lặp qui ước for y Sk ).
• Hiệu quả của thuật toán liệt kê phụ thuộc vào việc ta có xác
 định được chính xác các tập UCV này hay không.
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chú ý
• Thuật toán dễ dàng mở rộng cho bài toán liệt kê trong đó lời giải có 
 thể mô tả như là bộ (a1, a2, ..., an,...) độ dài hữu hạn, tuy nhiên giá trị 
 của độ dài là không biết trước và các lời giải cũng không nhất thiết 
 phải có cùng độ dài. Khi đó chỉ cần sửa lại câu lệnh
 if (k == n) ;
 else Backtrack(k+1);
 thành
 if ;
 else Backtrack(k+1);
 Cần xây dựng hàm nhận biết (a1, a2, ..., ak) đã là lời giải hay chưa. 
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ 1: LiÖt kª x©u nhÞ ph©n ®é dµi n
• Bài toán liệt kê xâu nhị phân độ dài n dẫn về việc liệt kê các phần tử
 của tập
 n
 B = {(b1, ..., bn): bi {0, 1}, i=1, 2, ..., n}.
• Ta xét cách giải quyết hai vấn đề cơ bản để cài đặt thuật toán quay lui:
 – Xây dựng tập ứng cử viên Sk: Rõ ràng ta có S1 = {0, 1}. Giả sử đã
 có xâu nhị phân cấp k-1 (b1, ..., bk-1), khi đó rõ ràng Sk = {0,1}. 
 Như vậy, tập các UCV vào các vị trí của lời giải đã được xác định.
 – Cài đặt vòng lặp liệt kê các phần tử của Sk: ta có thể sử dụng vòng 
 lặp for
 for (y=0;y<=1;y++)
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
C©y liÖt kª d·y nhÞ ph©n ®é dµi 3 
 ( ) Sk = {0,1} 
 0 1
 (0)
 (1)
 0 1 0 1
 (00) (01) (10) (11)
 0 1 0 1 0 1 0 1
(000) (001) (010) (011) (100) (101) (110) (111)
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chương trình trên C++ (Đệ qui)
 #include void Xau(int i){
 using namespace std; int j;
 int n, count; for (j = 0; j<=1; j++) {
 int b[100]; b[i] = j;
 if (i==n) Ghinhan();
 void Ghinhan() { else Xau(i+1);
 int i, j; }
 count++; }
 cout<<"Xau thu " << count<<": ";
 for (i=1 ; i<= n ;i++) { int main() {
 j=b[i]; cout>n;
 cout<<j<<" "; count = 0; Xau(1);
 } cout<<"So luong xau = "<<count<<endl;
 cout<<endl; }
 }
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chương trình trên C++ (không đệ qui)
 #include void Xau( ) {
 using namespace std; k=1; s[k]=0;
 int n, count,k; while (k > 0) {
 int b[100], s[100]; while (s[k] <= 1) {
 b[k]=s[k];
 void Ghinhan() { s[k]=s[k]+1;
 int i, j; if (k==n) Ghinhan();
 count++; else {
 cout<<"Xau thu " << count<<": k++;
 "; s[k]=0;
 for (i=1 ; i<= n ;i++) { }
 j=b[i]; }
 cout<<j<<" "; k--; //Quaylui
 } }
 cout<<endl; }
 }
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chương trình trên C++ (không đệ qui)
 int main() {
 cout>n;
 count = 0; Xau();
 cout<<"So luong xau = "<<count<<endl;
 }
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ 2. Liệt kê các m-tập con của n-tập
Bài toán: Liệt kê các tập con m phần tử của tập N = {1, 2, ..., n}.
Ví dụ: Liệt kê các tập con 3 phần tử của tập N = {1, 2, 3, 4, 5}
Giải: (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)
 Bài toán dẫn về: Liệt kê các phần tử của tập: 
 m
 S(m,n)={(a1,..., am) N : 1 ≤ a1<...<am≤ n}
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ 2. Liệt kê các m-tập con của n-tập
Ta xét cách giải quyết 2 vấn đề cơ bản để cài đặt thuật toán quay lui:
• Xây dựng tập ứng cử viên Sk: 
 – Từ điều kiện: 1 a1 < a2 < ... < am n
 suy ra S1 = {1, 2, ..., n-(m-1) }. 
 – Giả sử có tập con (a1, ..., ak-1). Từ điều kiện ak-1 < ak < . . . < am
 ≤ n, ta suy ra:
 Sk = {ak-1+1, ak-1+2, ..., n-(m-k)}. 
• Cài đặt vòng lặp liệt kê các phần tử của Sk:
 for (y=a[k-1]+1;y<=n-m+k;y++) ...
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chương trình trên C++ (Đệ qui)
 #include void MSet(int i){
 using namespace std; int j;
 for (j = a[i-1] +1; j<= n-m+i; j++) {
 int n, m, count; a[i] = j;
 if (i==m) Ghinhan();
 int a[100];
 else MSet(i+1);
 void Ghinhan() { }
 int i; }
 count++; int main() {
 cout>n; cin>>m;
 for (i=1 ; i<= m ;i++) a[0]=0; count = 0; MSet(1);
 cout<<a[i]<<" "; cout<<"So tap con "<<m<<" phan tu cua tap
 cout<<endl; "<<n<<" phan tu = "<<count<<endl;
 }
 }
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chương trình trên C++ (không đệ qui)
 #include void MSet(){
 using namespace std; k=1; s[k]=1;
 while(k>0){
 int n, m, count,k; while (s[k]<= n-m+k) {
 int a[100], s[100]; a[k]=s[k]; s[k]=s[k]+1;
 void Ghinhan() { if (k==m) Ghinhan();
 int i; else { k++; s[k]=a[k-1]+1; }
 count++; } k--;
 cout<<"Tap con thu " <<count<<": }
 "; }
 for (i=1 ; i<= m ;i++) int main() {
 cout>n; cin>>m;
 cout<<endl; a[0]=0; count = 0; MSet();
 } cout<<"So tap con "<<m<<" phan tu cua
 tap "<<n<<" phan tu = "<<count<<endl;
 }
 Cây liệt kê S(5,3)
 MSet(1); ( )
 3
 1 2
 (1) (2) (3)
 2 4
 3 3 4 4
 (2,3)
 (1,2) (1,3) (1,4) (2,4) (3,4)
 5 5
 3 4 5 4 5 4 5 5
(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)
 Sk = {ak-1+1, ak-1+2, ..., n-(m-k)} NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ 3. Liệt kê hoán vị
TËp c¸c ho¸n vÞ cña c¸c sè tù nhiªn 1, 2, ..., n lµ tËp:
 n
 n = {(x1,..., xn) N : xi ≠ xj , i ≠ j }.
Bài toán: Liệt kê tất cả các phần tử của n
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ 3. Liệt kê hoán vị
• Xây dựng tập ứng cử viên Sk: 
 – Râ rµng S1 = N. Gi¶ sö ta ®ang cã ho¸n vÞ bé phËn (a1, a2, ..., ak-1), 
 tõ ®iÒu kiÖn ai ≠ aj, víi mäi i ≠ j ta suy ra
 Sk = N \{ a1, a2, ..., ak-1}.
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Mô tả Sk
Xây dựng hàm nhận biết UCV:
bool UCV(int j, int k) 
{
 //UCV nhận giá trị true khi và chỉ khi j Sk
 int i;
 for (i=1;i++;i<=k-1)
 if (j == a[i]) return false;
 return true;
}
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Liệt kê hoán vị
• Cài đặt vòng lặp liệt kê các phần tử của Sk:
 for (y=1; y++; y <= n)
 if (UCV(y, k) )
 {
 // y là UCV vào vị trí k
 . . .
 }
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Chương trình trên C++
#include bool UCV(int j, int k)
using namespace std; {
 int i;
int n, m, count; for (i=1; i<=k-1; i++)
int a[100]; if (j == a[i]) return false;
 return true;
 }
int Ghinhan() {
 int i, j;
 count++;
 cout<<"Hoan vi thu "<<count<<": ";
 for (i=1 ; i<= n ;i++) 
 cout<<a[i]<<" ";
 cout<<endl;
}
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
void Hoanvi(int i) int main() {
{ cout>n;
 int j; count = 0; Hoanvi(1);
 for (j = 1; j<=n; j++) cout<<"So hoan vi = " << count;
 if (UCV(j,i)) }
 { a[i] = j;
 if (i==n) Ghinhan( );
 else Hoanvi(i+1);
 }
}
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Cây liệt kê hoán vị của 1, 2, 3
 ( )
 Hoanvi(1);
 S1 = ?
 1 2 3
 (1) (2) (3)
 S = ?
 2 3
 2 1 3 1 2
 (1,2) (1,3) (2,1) (2,3) (3,1) (3,2)
 S3 = ? 3 1
 3 2 2 1
 (1,2,3) (1,3,2) (2,1,3)(2,3,1) (3,1,2) (3,2,1)
 Sk = N \{ a1, a2, ..., ak-1}
Ví dụ 4. Bài toán xếp hậu
• Liệt kê tất cả các cách xếp n quân Hậu trên bàn cờ n n sao
 cho chúng không ăn được lẫn nhau, nghĩa là sao cho không
 có hai con nào trong số chúng nằm trên cùng một dòng hay
 một cột hay một đường chéo của bàn cờ.
 n cột
The n-Queens Problem
Hai con hậu bất kỳ không được xếp
trên cùng một dòng ...
The n-Queens Problem
Hai con hậu bất kỳ không được xếp
trên cùng một cột ...
The n-Queens Problem
Hai con hậu bất kỳ không được
xếp trên cùng một dòng, một cột
hay một đường chéo!
Biểu diễn lời giải
• Đánh số các cột và dòng của bàn cờ từ 1 đến n.
• Một cách xếp hậu có thể biểu diễn bởi bộ có n thành phần
 (a1, a2 ,..., an), trong đó ai là toạ độ cột của con hậu ở dòng i.
• Các điều kiện đặt ra đối với bộ (a1, a2 ,..., an):
 – ai aj , với mọi i j (nghĩa là hai con hậu ở hai dòng i và j không
 được nằm trên cùng một cột);
 – | ai – aj | | i–j |, với mọi i j (nghĩa là hai con hậu ở hai ô (i, ai)
 và (j, aj) không được nằm trên cùng một đường chéo).
Phát biểu bài toán
• Như vậy bài toán xếp Hậu dẫn về bài toán liệt kê các phần 
 tử của tập:
 n
 D={(a1, a2, ..., an) N : ai ≠ aj và |ai –aj| ≠ |i–j|, i ≠ j }
Bài toán xếp hậu: Duyệt toàn bộ
• Cần xếp N quân hậu lên bàn cờ có tất cả NxN ô, hỏi có tất cả bao nhiêu cách
 xếp ?
 – Quân thứ 1 có thể đặt vào 1 trong số N*N ô có N2 cách
 – Sau khi đặt quân thứ 1, tiến hành đặt quân thứ 2: bỏ qua ô đã đặt quân
 thứ 1 chỉ còn N2 – 1 ô có thể đặt quân thứ 2 có N2 – 1 cách
 – 
 ==> tổng cộng có tất cả (N2)! cách đặt. Với mỗi cách ta kiểm tra xem có
 thỏa mãn điều kiện không có quân nào cùng dòng/cột/đường chéo; nếu
 thỏa mãn thì thu được lời giải tương ứng.
• Có một cách khác: giảm không gian xét duyệt từ (N2)! xuống còn N! 
Bài toán xếp hậu: Duyệt toàn bộ
• Có một cách khác: giảm không gian xét duyệt từ (N2)! xuống còn N! 
 – Mỗi cách xếp N quân hậu lên bàn cờ sao cho không có quân nào cùng dòng, cùng cột ~ 
 một hoán vị N phần tử
 Mảng a gồm 4 phần tử
 a[1] =3; a[2] = 1; a[2] = 4; a[4] = 2
 Dòng 1: xếp quân hậu ở cột 3
 Dòng 2: xếp quân hậu ở cột 1
 Dòng 3: xếp quân hậu ở cột 4
 Dòng 4: xếp quân hậu ở cột 2
 Hoán vị: (3, 1, 4, 2)
 – Chú ý: không phải hoán vị nào cũng là lời giải của bài toán xếp hậu:
 Thuật toán: Liệt kê tất cả N! hoán vị;
 kiểm tra điều kiện không cùng đường
 chéo tại mỗi hoán vị. Nếu hoán vị nào
 thỏa mãn điều kiện cho ta 1 lời giải
 ? Làm thế nào để kiểm tra được điều kiện
 Hoán vị: (3, 1, 4, 2) Hoán vị: (3, 2, 1, 4) Không cùng đường chéo
 => lời giải => Không phải là lời giải
 Vì còn phải kiểm tra điều kiện: không có quân hậu nào cùng đường chéo
Bài toán xếp hậu: Duyệt toàn bộ
• Có một cách khác: giảm không gian xét duyệt từ (N2)! xuống còn N!
 – Kiểm tra hai quân hậu đặt ở ô (i1, j1) và ô (i2, j2) không thuộc cùng một đường chéo
 8
 7
 |i -i | ≠ |j -j |
 6 1 2 1 2
 5
 4
 3
 2
 1
 1 2345 678
Bài toán xếp hậu: Thuật toán quay lui
Thuật toán: Xếp từng quân hậu lên lần lượt từng dòng của bàn cờ: tại bước lặp thứ
k (k=1,..,n): ta cần tìm tọa độ cột ak để đặt quân cờ lên dòng k [tức là đặt lên ô 
(dòng k, cột ak)]
• Giả sử đã xây dựng được lời giải bộ phận (a1, a2, , ak-1): tức là đã xếp được
 (k-1) quân hậu lần lượt vào các ô (1, a1), (2, a2), (k-1, ak-1) thỏa mãn điều kiện
 đề bài. 
• Giờ tiếp tục xây dựng thành phần thứ k của lời giải: tức là cần tìm tọa độ cột để
 xếp quân hậu lên dòng thứ k của bàn cờ. Ta tiến hành như sau:
 – Duyệt lần lượt từng cột j =1,2,..,n:
 • Kiểm tra xem có thể xếp quân hậu lên ô (k, j) - dòng k cột j hay không: 
 bằng cách dùng hàm nhận biết ứng cử viên
 UCVh(int j, int k) trả về giá trị 1 nếu xếp được; ngược lại hàm trả
 về giá trị 0
 UCVh nhận giá trị 1 khi và chỉ khi j Sk
Thuật toán quay lui: Hàm nhận biết ứng cử viên
int UCVh(int j, int k) //check xếp quân hậu vào ô (k, j)
{ // UCVh nhận giá trị 1 khi và chỉ khi j Sk
 for (i=1; i<k; i++) //duyệt qua lần lượt từ dòng 1..(k-1) là những dòng đã xếp quân hậu
 if ((j == a[i]) || (fabs(j-a[i])== k-i)) return 0;
 return 1;
}
void Hau(int k) //tìm a[k]: cột xếp quân hậu thứ k lên dòng k
{
 for (int j=1; j<=n; j++) //duyệt qua lần lượt từ cột 1..n: xem có xếp được lên ô (k, j) không
 if (UCVh(j,k)) //nếu xếp được quân hậu lên ô (k, j)
 { 
 a[k]=j;
 if (k==n) Ghinhan(); //nếu đã xếp được đủ cả n quân hậu thì in ra lời giải
 else Hau(k+1); //nếu không thì tiếp tục tìm vị trí xếp quân hậu thứ k+1 lên dòng thứ k+1
}
114
Chú ý
• Rõ ràng là bài toán xếp hậu không phải là luôn có lời giải,
 chẳng hạn bài toán không có lời giải khi n = 2, 3. Do đó
 điều này cần được thông báo khi kết thúc thuật toán.
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
 ROW 1, COL 1
Thuật toán làm việc như thế nào
Xếp con hậu ở dòng 1
vào vị trí cột 1
 ROW 1, COL 1
 1 đã đặt
Thuật toán làm việc như thế nào
Thử xếp con hậu ở dòng 2 
vào vị trí cột 1
 ROW 2, COL 1
 ROW 1, COL 1
 1 đã đặt
Thuật toán làm việc như thế nào
Thử xếp con hậu ở dòng 2 
vào vị trí cột 2
 ROW 2, COL 2
 ROW 1, COL 1
 1 đã đặt
Thuật toán làm việc như thế nào
Thử xếp con hậu ở dòng 2 
vào vị trí cột 3
 ROW 2, COL 3
 ROW 1, COL 1
 1 đã đặt
Thuật toán làm việc như thế nào
Chấp nhận xếp con hậu ở dòng 2 
vào vị trí cột 3
 ROW 2, COL 3
 ROW 1, COL 1
 2 đã đặt
Thuật toán làm việc như thế nào
Thử xếp con hậu ở dòng 3 
vào cột đầu tiên
 ROW 3, COL 1
 ROW 2, COL 3
 ROW 1, COL 1
 2 đã đặt
Thuật toán làm việc như thế nào
Thử cột tiếp theo
 ROW 3, COL 2
 ROW 2, COL 3
 ROW 1, COL 1
 2 đã đặt
Thuật toán làm việc như thế nào
Thử cột tiếp theo
 ROW 3, COL 3
 ROW 2, COL 3
 ROW 1, COL 1
 2 đã đặt
Thuật toán làm việc như thế nào
Thử cột tiếp theo
 ROW 3, COL 4
 ROW 2, COL 3
 ROW 1, COL 1
 2 đã đặt
Thuật toán làm việc như thế nào
...không có vị trí đặt
con hậu ở dòng 3.
 ROW 3, COL 4
 ROW 2, COL 3
 ROW 1, COL 1
 2 đã đặt
Thuật toán làm việc như thế nào
Quay lại dịch
chuyển con hậu ở 
dòng 2
 ROW 2, COL 3
 ROW 1, COL 1
 1 đã đặt
Thuật toán làm việc như thế nào
Đẩy con hậu ở dòng
2 sang cột thứ 4.
 ROW 2, COL 4
 ROW 1, COL 1
 1 đã đặt
Thuật toán làm việc như thế nào
Xếp được con hậu ở 
dòng 2 ta tiếp tục xếp
con hậu ở dòng 3
 . . .
 ROW 2, COL 4
 ROW 1, COL 1
 2 đã đặt
Mét lêi gi¶i cña bµi to¸n xÕp hËu khi n = 8