Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3 - Một số mô hình thuật toán

Bài giảng "Cấu trúc dữ liệu và thuật toán: Chương 3 - Một số mô hình thuật toán" trình bày các nội dung chính sau đây: Bài toán tối ưu hóa tổ hợp; Thuật toán vét cạn; Nhánh và cận; Thuật toán tham lam; Chia để trị; Quy hoạch động. Mời các bạn cùng 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 toán: Chương 3 - Một số mô hình thuật toán 10/18/2021 Một số mô hình thuật toán Brute force, greedy, branch and bound, divide and conquer, dynamic programming10/15/2021 hiep.nguyenduy@hust.edu.vn 1Nội dung• Bài toán tối ưu hóa tổ hợp• Thuật toán vét cạn• Nhánh và cận• Thuật toán tham lam• Chia để trị• Quy hoạch động10/15/2021 hiep.nguyenduy@hust.edu.vn 2 1 10/18/2021 Bài toán tối ưu hóa • Bài toán tối ưu hóa • Tìm kiếm lời giải tốt nhất trong những lời giải khả thi • Nếu đầu vào là rời rạc  Bài toán tối ưu tổ hợp • Bài toán tối ưu tổ hợp • Không gian tìm kiếm là hữu hạn hoặc vô hạn đếm được • Thỏa mãn tập ràng buộc C • Với mục đích tối ưu hàm mục tiêu, f(x)  min (max) • Phương án giải • Có thể vét cạn hết không gian lời giải khả thi • Xây dựng từng bước lời giải • Giải gần đúng (xấp xỉ) 10/15/2021 hiep.nguyenduy@hust.edu.vn 3 Thuật toán vét cạn• Thuật toán vét cạn: brute-force search hoặc exhaustive search • Là một dạng của thuật toán dạng “sinh và test” – sinh ra phương án và kiểm tra lại xem có đáp ứng ràng buộc của bài toán • Đây là cách thiết kế thuật toán đơn giản nhất (chỉ cần nhìn vào phát biểu bài toán là tạo ra thuật toán được), dựa vào khả năng tính toán của máy tính • Hiệu quả của thuật toán không cao, nhất là khi kích thước đầu vào lớn • Một số bài toán phức tạp không thể giải bằng phương pháp vét cạn được (không gian tìm kiếm phương án có thể quá lớn, vượt khả năng tính toán của máy tính) • Có thể kết hợp thêm với một số kỹ thuật khác (heuristics methods) để giảm bớt không gian cần tìm kiếm lời giải • Dùng để giải các bài toán khi mà yêu cầu về thời gian chạy không phải là yếu tố đáng quan tâm (VD. chỉ cần tìm ra lời giải là được) 10/15/2021 hiep.nguyenduy@hust.edu.vn 4 2 10/18/2021 Thuật toán vét cạn • Thuật toán vét cạn • Trong thuật toán luôn có 2 pha là sinh lựa chọn và kiểm tra • Có thể sinh lựa chọn là 1 phương án đầy đủ, hoặc từng bước sinh 1 phần của phương án (VD. thuật toán back tracking) • Pha kiểm tra: • xem phương án sinh ra có thỏa mãn là một lời giải của bài toán hay không, • thường dựa ngay chính vào mô tả ban đầu • Hoặc dùng chính hàm đích cần đạt được của bài toán làm hàm kiểm tra • Bước kiểm tra đôi khi có thể gộp luôn vào quá trình sinh 10/15/2021 hiep.nguyenduy@hust.edu.vn 5 Thuật toán vét cạn• Bài toán 1. Dò mật khẩu *******• Mật khẩu • là chuỗi các ký tự (thường bao gồm ký tự đặc biệt và số) • Độ dài tối thiểu 6-8 ký tự • Mật khẩu càng dài, càng khó đoán nhưng cũng khó nhớ • Thông thường là dò bằng cách thử hết các khả năng, tuy nhiên có thể kết hợp với các từ điển các password hay dùng để cải thiện thời gian • Thường kết hợp song song chạy trên nhiều CPU 10/15/2021 hiep.nguyenduy@hust.edu.vn https://www.grc.com/haystack.htm 6 3 10/18/2021 selectionSort(A[0..n-1]) Thuật toán vét cạn { for i=n to 2 do min = 0• Bài toán 2. Thuật toán sắp xếp lựa chọn for j=0 to i-1 do • Lần lượt chọn phần tử lớn nhất trong dãy hiện tại, đổi if (A[j]>A[min]) min = j chỗ với phần tử ở cuối dãy SWAP(A[min], A[i ...