KỸ THUẬT THIẾT KẾ GIẢI THUẬT Nguyễn Văn Linh Mục tiêu • Biết kỹ thuật thiết kế giải thuật: từ ý tưởng giải thuật chi tiết • Hiểu rõ nguyên lý kỹ thuật phân tích thiết kế giải thuật • Vận dụng kỹ thuật phân tích thiết kế để giải tốn thực tế: tốn dạng áp dụng kỹ thuật Mơ hình từ tốn đến chương trình Lập trình Thiết kế Bài tốn thực tế Giải thuật Kỹ thuật thiết kế giải thuật: Chia để trị, quy hoạch động, … #includ e … Chương trình •Ngơn ngữ lập trình: •PASCAL, C/C++, JAVA, … Kỹ thuật chia để trị • Cần phải giải tốn có kích thước n • Ta chia tốn ban đầu thành số toán đồng dạng với tốn ban đầu có kích thước nhỏ n • Giải toán tổng hợp lời giải chúng, ta có lời giải tốn ban đầu • Đối với tốn con, ta áp dụng kỹ thuật để chia chúng thành tốn nhỏ • Quá trình phân chia cho tốn sở Nhìn lại giải thuật MergeSort QuickSort • MergeSort: • Phân chia: chia danh sách có n phần tử thành danh sách có n/2 phần tử • Q trình phân chia dẫn đến danh sách có phần tử, tốn sở • Tổng hợp: trộn (merge) danh sách có thứ tự thành danh sách có thứ tự • QuickSort: • Phân hoạch danh sách ban đầu thành danh sách “bên trái” “bên phải” • Sắp xếp danh sách “bên trái” “bên phải” ta thu danh sách có thứ tự • Bài tốn sở: Sắp xếp danh sách có phần tử nhiều phần tử có giá trị giống • Tổng hợp: bao hàm giai đoạn phân chia Bài tốn nhân số ngun lớn • Các NNLT có kiểu liệu số nguyên (integer Pascal, Int C…), kiểu có miền giá trị hạn chế • Người lập trình phải tìm cấu trúc liệu thích hợp để biểu diễn cho số nguyên • Để thao tác số nguyên biểu diễn cấu trúc mới, người lập trình phải xây dựng phép toán cho số nguyên phép cộng, phép trừ, phép nhân… • Sau ta đề cập đến toán nhân hai số nguyên lớn Giải thuật nhân số ngun lớn • Xét tốn nhân số nguyên lớn X Y, số có n chữ số • Theo cách nhân thơng thường: • Việc nhân chữ số X Y tốn n2 phép nhân • Nếu phép nhân chữ số tốn O(1) thời gian độ phức tạp giải thuật O(n2) 1426 x 3219 12834 1426 2852 4278 4590294 Giải thuật chia để trị cho toán nhân số nguyên lớn • Để đơn giản cho việc phân tích giải thuật ta giả sử n lũy thừa • Cịn phương diện lập trình, giải thuật trường hợp n • Biểu diễn X = A10n/2 + B Y = C10n/2 + D • Trong A, B, C, D số có n/2 chữ số • Ví dụ X = 1234 A = 12 B = 34 12*10 + 34 = 1234 = X • Với cách biểu diễn XY = AC10n + (AD + BC)10n/2 + BD Giải thuật chia để trị cho tốn nhân số ngun lớn (tt) • Ta phân tích tốn ban đầu thành số tốn nhân số có n/2 chữ số • Sau đó, ta kết hợp kết trung gian theo công thức XY = AC10n + (AD + BC)10n/2 + BD • Việc phân chia dẫn đến tốn nhân số có chữ số Đây toán sở Đánh giá giải thuật • Theo cơng thức XY = AC10n + (AD + BC)10n/2 + BD • Ta thực phép nhân số nguyên có n/2 chữ số, phép cộng số lớn n chữ số phép nhân với 10n 10n/2 • Phép cộng số có lớn n chữ số cần O(n) • Phép nhân với 10n tốn O(n) (dịch trái n lần) • Gọi T(n) thời gian nhân số có n chữ số ta có phương trình đệ quy sau: • T(1) = • T(n) = 4T(n/2) + n • Giải hệ ta T(n) = O(n2) Ta không cải tiến so với giải thuật nhân thông thường Kỹ thuật cắt tỉa Alpha-Beta (Alpha-Beta Pruning) • Nếu P nút MAX ta xét nút Q (dĩ nhiên Q nút MIN) Nếu Vp ≥ Vq cắt chưa xét Q • Tương tự P nút MIN (tất nhiên Q nút MAX) Vp ≤ Vq cắt chưa xét Q • Quy tắc định trị cho nút nút sau: – Khởi đầu nút MAX có giá trị tạm -∞ nút MIN có giá trị tạm ∞ – Nếu tất nút nút xét bị cắt tỉa giá trị tạm nút trở thành giá trị – Nếu nút MAX n có giá trị tạm V1 nút có giá trị V2 đặt giá trị tạm n max(V1,V2) Nếu n nút MIN đặt giá trị tạm n min(V1,V2) – Vận dụng quy tắc cắt tỉa Alpha-Beta nói để hạn chế số lượng nút phải xét X-đi X X X O O X-đi Max O-đi Min X X X X O O X X X X O O B A X X X O X O C D X-đi Max X O X X X O O E X X X X O O O F X O X X O X O G X X O X O X O H -1 O-đi Min X O X X X O X O I X O X X X O X O J X X X O X O X O K Cài đặt giải thuật cắt tỉa alpha – beta định trị trò chơi float cat_tia(NodeType Q, ModeType mode, float Vp) { NodeType C; /*C nút nút Q*/ Xét C trái Q; while (C Q) { if (mode == MAX) { float Vq; Vq = max(Vq, Cat_tia(C, MIN, Vq)); /*Vq giá trị tạm Q, sau tất nút Q xét bị cắt tỉa Vq giá trị nút Q*/ if (Vp= Vq) return Vq; if (mode == MAX) Vq = -∞; } else Vq = ∞; /*Xét Q, lần xác định giá trị nút Q, ta phải đặt lại giá trị tạm Vq so sánh với Vp để cắt tỉa hay không*/ return Vq; } Kỹ thuật nhánh cận • Nhánh cận kỹ thuật xây dựng tìm kiếm phương án tối ưu, khơng xây dựng toàn mà sử dụng giá trị cận để hạn chế bớt nhánh • Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất phương án có, nút biểu diễn cho phương án Nút n có nút tương ứng với khả lựa chọn tập phương án xuất phát từ n Kỹ thuật gọi phân nhánh • Vói nút ta xác định giá trị cận Giá trị cận giá trị gần với giá phương án Với tốn tìm ta xác định cận cịn với tốn tìm max ta xác định cận Cận giá trị nhỏ giá phương án, ngược lại cận giá trị lớn giá phương án Kỹ thuật nhánh cận: tốn TSP • Cây tìm kiếm phương án nhị phân đó: • Nút gốc nút biểu diễn cho cấu hình gồm tất phương án • Con trái biểu diễn cho cấu hình gồm tất phương án chứa cạnh đó, phải biểu diễn cho cấu hình gồm tất phương án khơng chứa cạnh (các cạnh để xét phân nhánh thành lập tuân theo thứ tự đó, chẳng hạn thứ tự từ điển) • Mỗi nút kế thừa thuộc tính tổ tiên có thêm thuộc tính (chứa hay khơng chứa cạnh đó) • Nút biểu diễn cho cấu hình bao gồm phương án • Ðể q trình phân nhánh mau chóng tới nút lá, nút ta cần có định bổ sung dựa nguyên tắc đỉnh chu trình có cấp khơng tạo chu trình thiếu Kỹ thuật nhánh cận: tốn TSP – ví dụ: b 4 a c e d Kỹ thuật nhánh cận: toán TSP- Phân nhánh Các cạnh theo thứ tự từ điển để xét là: ab, ac, ad, ae, bc, bd, be, cd, ce de Tất phương án B C ab D ac ae ad A ab E ac Tính cận cho nút gốc A • Ðỉnh a chọn ad = 2, ab = b • Ðỉnh b chọn ba = 3, be = • Ðỉnh c chọn ca = 4, cb = 4 a c e • Ðỉnh e chọn eb = 3, ed = • Ðỉnh d chọn da = 2, dc = d Tổng độ dài cạnh chọn 35, cận nút gốc A 35/2 = 17.5 Tính cận cho nút D • Ðỉnh a chọn ab = 3, ac = 4, hai cạnh buộc phải chọn b • Ðỉnh b chọn ba = 3, be = a c • Ðỉnh c chọn ca = 4, cb = • Ðỉnh d chọn de = 6, dc = 5, không chọn da nên ta phải chọn de • Ðỉnh e chọn eb = 3, ed = e d Tổng độ dài cạnh chọn 41, cận nút D 41/2 = 20.5 Áp dụng kỹ thuật nhánh cận cho tốn TSP • Xây dựng nút gốc, tính cận cho nút gốc • Sau phân nhánh cho nút, ta tính cận cho hai • Nếu cận nút >= giá nhỏ tạm thời phương án tìm thấy ta khơng cần xây dựng cho nút (Ta gọi cắt tỉa nút đó) • Nếu hai có cận nhỏ giá nhỏ tạm thời phương án tìm thấy nút có cận nhỏ ưu tiên phân nhánh trước • Mỗi lần quay lui để xét nút chưa xét nút ta phải xem xét lại nút để cắt tỉa hay khơng phương án có giá nhỏ tạm thời vừa tìm thấy • Sau tất phân nhánh bị cắt tỉa phương án có giá nhỏ phương án tìm phương án cần tìm • Trong q trình xây dựng ta xây dựng số nút lá, ta biết nút biểu diễn cho phương án Giá nhỏ số giá phương án gọi giá nhỏ tạm thời Ví dụ Kỹ thuật nhánh cận: BTcái ba lơ • Danh sách đồ vật xếp theo thứ tự giảm đơn giá • Nút gốc biểu diễn cho trạng thái ban đầu ba lơ, ta chưa chọn vật Tổng giá trị chọn TGT = Cận nút gốc CT = W * Ðơn giá lớn • Nút gốc có nút tương ứng với khả chọn đồ vật có đơn giá lớn Với nút ta tính lại thông số: – TGT = TGT (của nút cha) + số đồ vật chọn * giá trị vật – W = W (của nút cha) - số đồ vật chọn * trọng lượng vật – CT = TGT + W * Ðơn giá vật xét Kỹ thuật nhánh cận: BTcái ba lơ • Trong nút con, ta ưu tiên phân nhánh cho nút có cận lớn trước Các nút tương ứng với khả chọn đồ vật có đơn giá lớn Với nút ta lại phải xác định lại thông số TGT, W, CT theo công thức nói bước • Lặp lại bước với ý: nút có cận nhỏ giá lớn tạm thời phương án tìm thấy ta khơng cần phân nhánh cho nút (cắt bỏ) • Nếu tất nút phân nhánh bị cắt bỏ phương án có giá lớn phương án cần tìm Kỹ thuật nhánh cận: BTcái ba lơ Ví dụ Ta có ba lơ có trọng lượng 37 loại đồ vật với trọng lượng giá trị tương ứng cho bảng bên dưới: ĐV TL GT ĐV TL GT ĐG A 15 30 B 10 25 2.5 B 10 25 A 15 30 2.0 C 2 D 1.5 D C 2 1.0 ĐV TL GT ĐG B 10 25 2.5 A 15 30 2.0 D 1.5 C 2 1.0 TGT =0 W=37,CT = 92.5 XB=3 XB=2 TGT=75 W=7 CT = 89 B XA=0 TGT=75 W=7 CT=85.5 XD=1 TGT=81 W=3 CT = 84 TGT=50 W=17 CT = 84 C TGT=80 W=2 CT = 83 TGT=25 W=27 CT = 79 XB=0 TGT=0 W=37 CT = 74 D XA=0 K TGT=50 L W=17 CT=75.25 XD=0 G XC=1 TGT=83 W=1 XB=1 XA=1 E A TGT=75 W=7 CT = 82 H XC=0 I TGT=81 W=3 Cắt tỉa J E ...Mục tiêu • Biết kỹ thuật thiết kế giải thuật: từ ý tưởng giải thuật chi tiết • Hiểu rõ nguyên lý kỹ thuật phân tích thiết kế giải thuật • Vận dụng kỹ thuật phân tích thiết kế để giải tốn thực tế:... kế để giải tốn thực tế: tốn dạng áp dụng kỹ thuật Mơ hình từ tốn đến chương trình Lập trình Thiết kế Bài tốn thực tế Giải thuật Kỹ thuật thiết kế giải thuật: Chia để trị, quy hoạch động, … #includ... thước xấp xỉ hiệu suất cao Kỹ thuật “tham ăn” (greedy) • Đây kỹ thuật dùng nhiều để giải toán tối ưu tổ hợp • Áp dụng kỹ thuật không cho lời giải tối ưu cho lời giải “tốt”; bù lại lợi nhiều