Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu

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.
Nội dung trích xuất từ tài liệu:
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ọcBuổ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 ĐỆ QUIRECURVE 2 Mã hóaKhái niệm Đệ QuiMộ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óaChươ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óaMộ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óaVí 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 y0int UCLN(int x, int y){ if (y == 0) return x; return UCLN(y, x % y);} 6 Mã hóaTHUẬT GIẢI QUAY LUI BACK TRACKING 7 Mã hóaTổ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óaMô hình thuật giải quay lui: Xác định phần tử Xi bằng đệ quyvoid 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óaHai đ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ình2. 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óaBài toán: Liệt kê các dãy nhị phân có độ dài nPhâ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; jMã đi tuần: chỉ ra hành trình của quân Mã xuất pháttừ một ô trên bàn cờ đi qua tất cả các ô còn lại củabà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óaThuậ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 && vBà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óaThuật giải xác định phần tử Xi của một hoán vịvoid Try(int i){ if ( i & ...