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<br /> Xấp Xỉ<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Phương pháp chính xác<br />
Phương pháp xấp xỉ<br />
Bài toán tìm kiếm tối ưu<br />
Một số bài toán tiêu biểu<br />
Một số phương pháp<br />
<br /> <br /> 1<br /> <br /> P.P. Chính Xác<br />
<br />
<br />
<br /> <br />
<br /> <br /> Tìm được lời giải tốt nhất (tối ưu)<br /> Thời gian tìm kiếm lâu<br /> Với những bài toán phức tạp<br />
Không khả thi (quá lâu)<br /> Với những bài toán thực tế<br />
Thời gian tìm lời giải có vai trò quan trọng<br /> <br /> 2<br /> <br /> P.P. Xấp Xỉ<br />
<br />
<br />
<br /> <br /> Tìm lời giải cận tối ưu<br /> Trong khoảng thời gian hợp lý<br /> Phù hợp:<br />
Với những bài toán phức tạp<br />
Với những bài toán thực tế<br />
Đôi<br /> <br /> khi chỉ cần tìm được lời giải chấp nhận được<br /> <br /> 3<br /> <br /> Bài Toán Tìm Kiếm Tối Ưu<br />
<br />
<br /> <br />
<br /> <br /> Tìm lời giải tối ưu trong các lời giải khả thi<br /> Lời giải khả thi:<br />
Phải thỏa mãn các ràng buộc cứng<br /> Đánh giá / so sánh giữa các lời giải khả thi:<br />
Tối thiểu các vi phạm ràng buộc mềm<br />
Giữa trên một (hoặc vài) hàm mục tiêu<br /> <br /> 4<br /> <br />