Bai13_thietkethuattoan2

Thiết kế thuật toán Lê Sỹ Vinh Bộ môn Khoa Học Máy Tính – Khoa CNTT Đại Học Công Nghệ - ĐHQGHN Email: [email protected]

Chiến lược vét cạn Tư tưởng: Duyệt tất cả các nghiệm có thể trong không gian nghiệm để tìm ra nghiệm tốt nhất Ví dụ: 1. Tìm đường đi ngắn nhất qua tất cả các đỉnh 2. Ba lô 3 Chia 3. Chi kẹo k 4. 8 quân hậu

Chiến lược tham ăn (G d strategy)) (Greedy Ý tưởng: Quá trình xây dựng nghiệm được tiến hành qua N bước, tại mỗi bước thay vì xét tất cả các khả năng có thể, ta chỉ xét một khả năng cho là tốt nhất. Nghiệm tìm được thường chỉ là nghiệm gần tối ưu Ví dụ: 1. Bài toán người bán hàng 2 Bài toán cái ba lô 2. 3. Bài toán chia kẹo

Thuật toán leo đồi (hill climbing) Ý tưởng: Từ một nghiệm ban đầu, cải tiến liên tục để thu được nghiệm tốt hơn cho đến khi không cải tiến được nữa. Ví dụ: 1. Bài toán chia kẹo 2. Bài toán người bán hàng