Lược đồ xấp xỉ thời gian đa thức

Lược đồ xấp xỉ thời gian đa thức

Chúng ta có thể tìm thấy một số giải pháp thời gian đa thức cho các bài toán NP-Complete như bài toán Knapsack 0-1 hoặc bài toán tổng tập hợp con. Những vấn đề này rất phổ biến trong thế giới thực, vì vậy phải có một số cách để xử lý những vấn đề này.

Lược đồ xấp xỉ thời gian đa thức (PTAS) là một loại thuật toán gần đúng cho các bài toán tối ưu hóa. Đối với bài toán Knapsack 0-1, có một lời giải đa thức Pseudo, nhưng khi các giá trị lớn thì lời giải không khả thi. Sau đó, chúng tôi cần một giải pháp PTAS.

Một số bài toán NP-đầy đủ như Tô màu đồ thị, bài toán K-Center, v.v. chúng không có phương pháp giải thời gian đa thức đã biết. PTAS được sử dụng để tính gần đúng các thuật toán. Các thuật toán này nhận tham số ε> 0 và để tính gần đúng, chúng tôi sẽ tối thiểu hóa (1 + ε) và tối đa hóa (1 - ε).

Ví dụ

Ví dụ, nếu chúng ta chọn một bài toán tối thiểu và lấy ε =0,5, thì nghiệm bằng PTAS là gần 1,5. Vì vậy, thời gian chạy phải là đa thức theo n, nhưng nó có thể là cấp số nhân theo ε.