Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu trình bày những nội dung về đệ qui (recurve), khái niệm đệ qui, thuật giải quay lui (back tracking), kỹ thuật nhánh cận. Mời các bạn tham khảo.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu
- Một số vấn đề cơ sở
của Tin học
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
- ĐỆ QUI
RECURVE
2 Mã hóa
- 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 y0
3 Mã hóa
- 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ó.
Ví dụ: Định nghĩa hàm tính N! theo đệ qui.
int GiaiThua(int N)
{
if (N == 0) return 1;
return N * GiaiThua(N - 1);
}
4 Mã hóa
- Một định nghiã đệ qui phải có 2 thành phần:
• Thành phần dừng: Không chứa khái niệm đang định nghiã
Ví dụ: N! = 1
• Thành phần đệ qui: có chứa khái niệm đang định nghiã
5 Mã hóa
- Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide
• (a)UCLN(x,y) = x nếu y = 0
• (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y0
int UCLN(int x, int y)
{
if (y == 0) return x;
return UCLN(y, x % y);
}
6 Mã hóa
- THUẬT GIẢI QUAY LUI
BACK TRACKING
7 Mã hóa
- 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.
Cấu hình một lời giải X1 X2 X3 … Xn
Tập khả năng K1 K2 … … Km
8 Mã hóa
- Mô hình thuật giải quay lui:
Xác định phần tử Xi bằng đệ quy
void Try( int i )
{
If (Xi là phần tử cuối cùng trong cấu hình)
< Thông báo cấu hình tìm được>;
else
for ( mọi Kj thuộc tập khả năng đề cử cho Xi)
[ if ( Chấp nhận Kj ) ]
{
Thử chọn Kj cho Xi;
Try( i+1); //Gọi đệ quy để xác định phần tử Xi+1
Bỏ ghi nhận Kj đã chọn cho Xi để chọn khả năng khác;
}
}
9 Mã hóa
- Hai điểm mấu chốt quyết định độ phức tạp của bài toán là:
1. Xác định tập khả năng đề cử: Phụ thuộc vào việc phân tích
nhu cầu dữ liệu của từng thành phần trong cấu hình
2. Kiểm tra khả năng đề cử phải phù hợp với thành phần cần
xác định.
10 Mã hóa
- Bài toán: Liệt kê các dãy nhị phân có độ dài n
Phân tích:
• Biểu diến cấu hình dãy nhị phân dưới dạng: X[1..n]
• Tập khả năng đề cử cho mỗi phần tử Xi là {0, 1}
• Thuật giải xác định phần tử Xi của dãy nhị phân như sau:
void Try(int i)
{
if ( i > n ) ;
else
for (int j =0; j
- 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.
Phân tích:
• Cấu hình lời giải là BC[1..n][1..n]
chứa số thứ tự hành trình của 2
(u, v)
quân Mã.
• Tập khả năng chứa các giá trị
dùng tính tọa độ các ô kế tiếp 1
(x, y)
dx[1..8] = {-2,-1, 1, 2, 2, 1, -1, -2}
dy[1..8] = { 1, 2, 2, 1, -1, -2, -2, -1}
• Điều kiện chọn khả năng cho
bước đi thứ i là Ô được chọn
phải :
– Thuộc bàn cờ
– Và chưa đi qua
12 Mã hóa
- 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) ;
else
for ( j =1; j = 1 && u = 1 && v
- Bài toán:
Liệt kê các hoán vị của dãy số {1, 2, .., n}
• Biểu diễn cấu hình một hoán vị: X[1..n]
• Tập khả năng đề cử: { 1, 2, .., n }
• Nhưng do Xi Xj với i j. Nên phải kiểm tra giá trị đề cử
cho Xi phải khác với các giá trị đã chọn cho các thành phần
trước đó.
Hướng giải quyết chung là tổ chức các biến trạng thái lưu
trữ thông tin phục vụ cho việc kiểm tra:
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
14 Mã hóa
- Thuật giải xác định phần tử Xi của một hoán vị
void Try(int i)
{ if ( i > n ) ;
else
for (int j = 1; j
- Ví dụ: Liệt kê các tập con k phần tử
của tập S = {1, 2, .., n}. Trong đó (k
- 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 ) ;
else
for (int j = 1; j
- Một cách giải khác của bài toán tập con
Đưa ra điều kiện cho mỗi tập con là :
1
- 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 ) ;
else
for (int j = X[i-1]+1; j
- KỸ THUẬT NHÁNH CẬN
20 Mã hóa
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
