Buổi 3:
Cấu trúc dữ liệu vàthuật giải
Giáo viên: Tạ Thúc Nhu
Khoa CNTT trường ĐH Lạc Hồng
Một số vấn đề cơ sở
của Tin học
Mã hó
a
2
ĐỆ QUI
RECURVE
Mã hó
a
3
Khái niệm Đệ Qui
Khái niệm Đệ Qui
Một đối tượng được gọi là đệ qui nếu nóhoặc 1 phần của nó
được định nghiã thông qua khái niệm về chính nó.
Vídụ: Định nghiã phép toán giai thừa, ký hiệu: N!
• (a) Nếu N = 0, thìN! = 1
• (b) nếu N > 0 thìN! = N*(N-1)!
Vídụ: Định nghiã UCLN của 2 số x vày, ký hiệu: UCLN(x, y)
• (a)UCLN(x,y) = x nếu y = 0
• (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y<>0
Mã hó
a
4
Chương trình đệ qui
Chương trình đệ qui
• Một chương trình là đệ qui nếu trong chương trình cólời
gọi đến chính nó.

Mã hó
a
8
Tổng quan thuật giải Quay lui (Back Tracking)
Tổng quan thuật giải Quay lui (Back Tracking)
• Dùng giải bài toán liệt kê các cấu hình
• Mỗi cấu hình được xác định bằng cách xây dựng tuần tự từng thành
phần trong cấu hình.
• Mỗi thành phần được xác định bằng cách chọn lựa dữ liệu trong tập khả
năng được đề xuất.
Xn…X3X2X1
Km……K2K1Tập khả năng
Cấu hình một lời giải
Mã hó
a
9
Mô hình thuật giải quay lui:
Xác định phần tử X
i
bằng đệ quy
Mô hình thuật giải quay lui:
Xác định phần tử X
i
bằng đệ quy
void Try( int i )
{
If (X
i
làphần tử cuối cùng trong cấu hình)
< Thông báo cấu hình tìm được>;

{
if ( i > n ) <Thông báo cấu hình tìm được>;
else
for (int j =0; j<= 1; j++)
{
X[ i ] = j;
Try( i + 1 );
}
}
Mã hó
a
12
Mã
đi tu
ầ
n: ch
ỉ
ra h
à
nh tr
ì
nh c
ủ
a quân Mã xu
ấ
t ph
á
t
từ một ô trên bàn cờ đi qua tất cả các ô còn lại của
bàn cờ, mỗi ô đúng 1 lần.

–Và chưa đi qua
1
2
(x, y)
(u, v)
Mã hó
a
13
Thuật giải xác định bước đi thứ i của quân Mã
Thuật giải xác định bước đi thứ i của quân Mã
void Try(int i)
{ int j,u,v;
if (i > n*n) <Thông báo cấu hình tìm được>;
else
for ( j =1; j <= 8 ; j++)
{
u =x+dx[j]; v = y+dy[j];
if (u >= 1 && u <= n && v >= 1 && v<=n && BC[u,v] = 0)
{
x = u; y = v;
BC[u,v] = i;
Try(i+1);
x = u-dx[j]; y = v-dy[j];
BC[u,v] = 0;
}
}
}
Mã hó
a
14

}
}
Mã hó
a
16
Vídụ: Liệt kê các tập con k phần tử
của tập S = {1, 2, , n}. Trong đó(k <= n)
Vídụ: Liệt kê các tập con k phần tử
của tập S = {1, 2, , n}. Trong đó(k <= n)
• Biểu diễn cấu hình một tập con K phần tử: X[1 K]
• Tập khả năng đề cử: { 1, 2, , n }
• Nhưng do Xi <> Xj với i <> j. Nên các giátrị đề cử cho Xi
phải khác với các giátrị đề cử cho các thành phần trước đó
Hướng giải quyết:
Dùng mảng F[1 N] để ghi nhớ tình trạng sử dụng của từng
khả năng trong tập S={1, 2, , N}, với qui ước:
F[ j ] = 0 nếu j chưa sử dụng
F[ j ] = 1 nếu j đã sử dụng
Mã hó
a
17
Thuật giải xác định phần tử Xi của một tập con
Thuật giải xác định phần tử Xi của một tập con
void Try(int i)
{if ( i > K ) <Thông báo cấu hình tìm được>;
else
for (int j = 1; j<= N; j++)
if (F[j] = 0)
{
X[i] = j;

for (int j = X[i-1]+1; j<= N-K+i; j++)
{
X[i] = j;
Try( i + 1 );
}
}
Mã hó
a
20
KỸ THUẬT NHÁNH CẬN
Mã hó
a
21
Công dụng
Công dụng
• Dùng giải quyết bài toán tìm cấu hình tốt nhất trong các cấu
hình liệt kê bằng thuật toán quay lui.
• Giảm thời gian thực hiện của thuật toán quay lui.
Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả năng đánh
giácấu hình ở từng bước.
Nếu tại bước thứ i đánh giá được cấu hình không tối ưu thìquay lui
ngay không cần phải gọi đệ quy tìm tiếp các thành phần khác của cấu
hình.
Mã hó
a
22
Mô hình đánh giánhánh cận
trong thuật toán quay lui:
Mô hình đánh giánhánh cận
trong thuật toán quay lui:

rồi quay về nơi xuất phát. Giả thiết biết được chi phí đi từ thành phố i đến thành
phố j làC[i,j], 1≤ i, j < n.
Hãy tìm 1 hành trình cho người du lịch để tổng chi phítheo hành trình này làít
nhất.
4
1
3
2
1
3
2
1
2
4
0421
4012
2103
1230
Ma trận chi phíC
Mã hó
a
24
Phân tích:
Phân tích:
• Cấu hình lời giải : X[1 n]
–X[1] = 1 được xem làthành phố xuất phát.
–Một hành trình làmột hoán vị của các thành phố 2, ,n.
• Tập khả năng đề cử : {2, 3, , n}
• Cấu hình BESTCONFIG:
–Smin làtổng chi phíthấp nhất đã chọn trong các hành trình tìm