Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng

Dưới đây là bài giảng Phân tích thiết kế giải thuật: Chương 4 của Trịnh Huy Hoàng. Mời các bạn tham khảo bài giảng để hiểu rõ hơn về phương pháp thiết kế thuật giải như thiết kế thuật toán, phân loại các phương pháp thiết kế thuật toán, các thuật toán chính xác, các thuật toán gần đúng, các bước để thiết kế một thuật giải cho một vấn đề cho trước.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng Các phương pháp thiết kế thuật giải Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM 1 Nội dung  Thiếtkế thuật toán  Phân loại các phương pháp thiết kế thuật toán  Các thuật toán chính xác  Các thuật toán gần đúng  Các bước để thiết kế một thuật giải cho một vấn đề cho trước 2 Mô hình từ bài toán đến chương trình Thiết kế Lập trình #includ Bài toán  e … thực tế Giải thuật Chương  trình Kỹ  thuật  thiết  kế  giải  thuật: Chia  để  trị,  quy  hoạch  động, … 3 Các bước để giải 1 bài toán trên máy tính  Bước 1: Xác định vấn đề - bài toán  Bước 2: Lựa chọn phương pháp giải  Bước 3: Xây dựng thuật toán hoặc thuật giải  Bước 4: Cài đặt chương trình  Bước 5: Hiệu chỉnh chương trình  Bước 6: Thực hiện chương trình 4 Thiết kế một thuật toán  Cho một vấn đề cần giải quyết  Xác định các bước và trình tự các bước để giải quyết vấn đề đó  Phân tích  thuật toán tốt đến mức nào 5 Phân loại các phương pháp thiết kế thuật toán  Phương pháp chính xác – Bảo đảm nếu thuật toán được thi hành hoàn toàn thi lời giải là chính xác cho vấn đề cần giải quyết – Tuy nhiên  Ràng buộc về thời gian  Ràng buộc về không gian  Ràng buộc về thực tế vấn đề cần giải quyết: chi phí đầu tư, mức độ chấp nhận được của giải pháp  Phương pháp gần đúng – Không bảo đảm thuật toán sẽ chính xác cho tất cả các trường hợp – Sẽ tốt cho một số các trường hợp nào đó – Nhanh, dễ thiết kế 6 Một số các phương pháp thiết kế thuật toán  Tuần tự (vét cạn)  Quay lui (thử và sai)  Chia để trị  Quy hoạch động  Tham lam  Heuristics 7 Phương pháp tuần tự  Tuần tự xét tất cả các khả năng có thể có (vét cạn) cho đến khi gặp giải pháp cho vấn đề cần giải quyết  Ví dụ: giải bài toán cổ sau bài toán cổ – Trăm trâu trăm cỏ – Trâu đứng ăn năm – Trâu nằm ăn ba – Lụ khụ trâu già – Ba con một bó 8 Thuật toán 1  Gọi x là số trâu đứng,y là số trâu nằm, z là số trâu già  x, y, z Thuật toán 1 for x  0 to 100 do for y  0 to 100 do for z  0 to 300 do if ((5*x+3*y+z/3 = 100) && (x+y+z=100)) then (x, y, z) là giải pháp của bài toán  Nhận xét: ??? 10 Thuật toán 2  Giớihạn lại phạm vi của x, y, z hợp lý hơn  Thuật toán: for x  0 to 100/5 do for y  0 to 100/3 do for z  0 to 300 do if ((5*x+3*y+z/3 = 100) && (x+y+z=100)) then (x, y, z) là giải pháp của bài toán  Nhận xét: ??? 11 Thuật toán 3  Giới hạn tiếp phạm i của x, y, z: – ??? 12 Thiết kế thuật toán theo kiểu tuần tự vét cạn  Dễ thiết kế  Chậm  Tăng tốc thuật toán bằng cách giới hạn miền vét cạn 13 Thiết kế thuật toán theo kiểu quay lui  Thật sự cũng là một phương pháp tuần tự xét hết tất cả các khả năng có thể có  Kết hợp với cơ chế stack và kỹ thuật đệ qui nhằm giúp thuật toán gọn, dễ hiểu 14 Phương pháp quay lui  Ý tưởng: – Giả sử lời giải của bài toán là một bộ – Tại bước thứ i: tìm giải pháp tạm thời cho S i  Tìm khả năng có thể cho thành phần S i.  Nếu có thể chọn một khả năng nào đó làm giải pháp cho Si tạm thời. – Chuyển sang tìm giải pháp cho Si+1.  Nếu không tồn tại một giải pháp tạm thời cho S i thì quay lại bước thứ i-1, loại bỏ giải pháp tạm thời của S i-1, tìm giải pháp khác cho Si-1.  Nếu i=n+1, bộ các giải pháp tạm thời 15 chính là giải pháp của bài toán  Nếu i=0, đã xét tất cả khả năng có thể xảy ra Phương pháp quay lui – Input: thành phần thứ k cần tìm giải pháp tạm thời – Output: giải pháp tạm thời cho thành phần thứ k Try(i) if (i = n + 1) đã tìm thấy giải pháp else Xét mọi khả năng T có thể của Si Thiết lập T là giải pháp tạm thời cho Si Try(i+1) Khôi phục các trạng thái trước khi chọn T là giải pháp tạm thời Loại bỏ T ra khỏi tập có thể thành giải pháp của Si 16 Phương pháp quay lui  Ví dụ: – Xét tình huống có một ông già mù qua suối. – Bài toán xếp hậu  Chobàn cờ vua (8x8), hai con hậu được gọi là khống chế nhau nếu chúng – cùng nằm trên một dòng, hoặc – cùng nằm trên một cột, hoặc – cùng nằm trên một đường chéo song song đường chéo chính – cùng nằm trên một đường chéo song song đường chéo phụ  Hãy tìm cách xếp tám con hậu lên bàn cờ sao cho không tồn tại hai con hậu bất kỳ nào khống chế nhau. 17 Bài toán 8 hậu – Input: bàn cờ, trạng thái cột, chéo chính, chéo phụ, kích thước và dòng đang xét hiện tại (từ 1) – Output: giải pháp tạm thời cho thành phần thứ k ...