Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 12 - Hoàng Thị Điệp (2014)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 12: Các chiến lược thiết kế thuật toán" cung cấp cho người học các kiến thức: Ý tưởng các chiến lược, ví dụ minh họa. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 12 - Hoàng Thị Điệp (2014)Bài 12: Các chiến lược thiết kếthuật toánGiảng viên: Hoàng Thị ĐiệpKhoa Công nghệ Thông tin – Đại học Công NghệCấu trúc dữ liệu và giải thuậtHKI, 2013-2014Nội dung chínhÝ tưởng các chiến lược2. Ví dụ minh họa1.2diepht@vnuCác chiến lượcChia-để-trị1.divide-and-conquer2. Quy hoạch độngbacktrackinggreedy method5. Các thuật toán ngẫunhiêndynamic programming3. Quay lui4. Tham ănrandomized /probabilistic algorithmMỗi chiến lược có các tính chất riêng và chỉ thíchhợp cho một số dạng bài toán nào đó.3diepht@vnuÝ tưởng Chia-để-trị Chia bài toán thành các bàitoán kích thước nhỏ có thể giảiquyết độc lập. Sau đó kết hợpnghiệm các bài toán kích thướcnhỏ thành nghiệm bài toán gốc Thuật toán đệ quy Quy hoạch động Giải bài toán lớn dựa vào kếtquả bài toán con. Tránh lặp lạiviệc giải cùng một bài toán conbằng cách lưu nghiệm các bàitoán con trong một bảng Thuật toán lặp4 Tham ăn Thực hiện từng bước một. Tạimỗi bước, chọn phương ánđược xem là tốt lúc đó. Không phải tất cả các thuậttoán tham ăn đều cho kết quảtối ưu toàn cục Các chiến lược khác Quay lui Thuật toán ngẫu nhiêndiepht@vnuThuật toán tiêu biểu Chia-để-trị Tìm kiếm nhị phân(binary search) Sắp xếp trộn (mergesort) Sắp xếp nhanh (quicksort) Quy hoạch động Tìm dãy con tăng dài Tìm dãy con chung củahai dãy số (longestcommon subsequence) Tham ăn Xây dựng mã Huffman(Huffman encoding) Tìm cây bao trùm nhỏnhất (minimum spanningtree)nhất (longest increasingsubsequence) Bài toán ba lô(backpacker/knapsack) Bài toán người bán hàng(traveling salesman)5diepht@vnu