โครงการประมาณค่าเวลาพหุนาม

รูปแบบการประมาณเวลาพหุนาม

เราสามารถหาวิธีแก้ปัญหาเวลาพหุนามสำหรับปัญหา NP-Complete เช่น ปัญหา 0-1 เป้ หรือ ปัญหาผลรวมย่อย ปัญหาเหล่านี้เป็นที่นิยมอย่างมากในโลกแห่งความเป็นจริง จึงต้องมีวิธีจัดการกับปัญหาเหล่านี้บ้าง

โครงการการประมาณเวลาแบบพหุนาม (PTAS) เป็นประเภทที่ใช้ประมาณอัลกอริธึมสำหรับปัญหาการปรับให้เหมาะสมที่สุด สำหรับปัญหา 0-1 Knapsack มี Pseudo Polynomial Solution แต่เมื่อค่ามาก วิธีแก้ปัญหาก็ไม่สามารถทำได้ เราต้องการโซลูชัน PTAS

ปัญหาบางอย่างใน NP-complete เช่น Graph Coloring, K-Center ปัญหา ฯลฯ ไม่ทราบวิธีแก้ไขเวลาพหุนาม PTAS ใช้เพื่อประมาณอัลกอริทึม อัลกอริทึมเหล่านี้ใช้พารามิเตอร์ ε> 0 และเพื่อประมาณค่า เราจะย่อให้เล็กสุด (1 + ε) และขยายให้ใหญ่สุด (1 - ε)

ตัวอย่าง

ตัวอย่างเช่น หากเราเลือกปัญหาการย่อขนาดและหาค่า ε =0.5 วิธีแก้ปัญหาโดยใช้ PTAS จะเท่ากับ 1.5 ดังนั้นเวลาทำงานต้องเป็นพหุนามในรูปของ n แต่สามารถยกกำลังได้ในรูปของ ε