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. nội dung chi tiết. | Bài 12: Các chiến lược thiết kế thuật toán Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014 Nội dung chính Ý tưởng các chiến lược 2. Ví dụ minh họa 1. 2 diepht@vnu Các chiến lược Chia-để-trị 1. divide-and-conquer 2. Quy hoạch động backtracking greedy method 5. Các thuật toán ngẫu nhiên dynamic programming 3. Quay lui 4. Tham ăn randomized / probabilistic algorithm Mỗi chiến lược có các tính chất riêng và chỉ thích hợp cho một số dạng bài toán nào đó. 3 diepht@vnu Ý tưởng Chia-để-trị Chia bài toán thành các bài toán kích thước nhỏ có thể giải quyết độc lập. Sau đó kết hợp nghiệm các bài toán kích thước nhỏ 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ết quả bài toán con. Tránh lặp lại việc giải cùng một bài toán con bằng cách lưu nghiệm các bài toán con trong một bảng Thuật toán lặp 4 Tham ăn Thực hiện từng bước một. Tại mỗ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ật toá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ên diepht@vnu Thuật toán tiêu biểu Chia-để-trị Tìm kiếm nhị phân (binary search) Sắp xếp trộn (merge sort) Sắp xếp nhanh (quick sort) Quy hoạch động Tìm dãy con tăng dài Tìm dãy con chung của hai dãy số (longest common subsequence) Tham ăn Xây dựng mã Huffman (Huffman encoding) Tìm cây bao trùm nhỏ nhất (minimum spanning tree) nhất (longest increasing subsequence) Bài toán ba lô (backpacker/knapsack) Bài toán người bán hàng (traveling .
