Bài giảng Thiết kế và đánh giá thuật toán: Xấp xỉ - TS. Lê Nguyên Khôi

Bài giảng "Thiết kế và đánh giá thuật toán: Xấp xỉ" gồm các nội dung: Phương pháp chính xác, phương pháp xấp xỉ, bài toán tìm kiếm tối ưu, một số bài toán tiêu biểu, một số phương pháp. 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 Thiết kế và đánh giá thuật toán: Xấp xỉ - TS. Lê Nguyên Khôi Phân Tích & Thiết Kế Thuật Toán Xấp Xỉ TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Phương pháp chính xác
Phương pháp xấp xỉ
Bài toán tìm kiếm tối ưu
Một số bài toán tiêu biểu
Một số phương pháp
1 P.P. Chính Xác



Tìm được lời giải tốt nhất (tối ưu) Thời gian tìm kiếm lâu Với những bài toán phức tạp
Không khả thi (quá lâu) Với những bài toán thực tế
Thời gian tìm lời giải có vai trò quan trọng 2 P.P. Xấp Xỉ


Tìm lời giải cận tối ưu Trong khoảng thời gian hợp lý Phù hợp:
Với những bài toán phức tạp
Với những bài toán thực tế
Đôi khi chỉ cần tìm được lời giải chấp nhận được 3 Bài Toán Tìm Kiếm Tối Ưu


Tìm lời giải tối ưu trong các lời giải khả thi Lời giải khả thi:
Phải thỏa mãn các ràng buộc cứng Đánh giá / so sánh giữa các lời giải khả thi:
Tối thiểu các vi phạm ràng buộc mềm
Giữa trên một (hoặc vài) hàm mục tiêu 4