Bài giảng Thiết kế và Phân tích thuật toán_Chương 7: Các bài toán NP-Khó và NP-Đầy đủ

Chúng ta đã biết nhiều bài toán, điển hình là bài toán người bán hàng, bài toán ba lô, bài toán chu trình Hamilton,... Các thuật toán tốt nhất để giái quyết các bài toán này đều có thời gian chạy không phải là thời gian đa thức, chẳng hạn thuật toán quy hoạch động cho bài toán người bán hàng có thời gian chạy 0(n2),... Cho tới nay chưa có ai tìm ra được thuật toán thời gian đa thức cho bất kỳ bài toán nào trong lớp các bài toán trên. Vấn đề đặt ra là có tồn tại hay không thuật toán thời gian chạy đa thức cho cac bài toán trên?

ppt34 trang | Chia sẻ: diunt88 | Lượt xem: 3208 | Lượt tải: 2download
Bạn đang xem trước 20 trang tài liệu Bài giảng Thiết kế và Phân tích thuật toán_Chương 7: Các bài toán NP-Khó và NP-Đầy đủ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 7
Tài liệu liên quan