เอ็นพีบริบูรณ์
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ (อังกฤษ: NP-complete) เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C
นิยามแก้ไข
เราจะเรียกปัญหาการตัดสินใจ C ว่าเป็น เอ็นพีบริบูรณ์ เมื่อ
วิธีการแก้ปัญหาเอ็นพีบริบูรณ์แก้ไข
ในกรณีที่เราต้องการแก้ปัญหาแบบหาคำตอบดีที่สุด ของปัญหาที่เป็นเอ็นพีบริบูรณ์ เช่น ต้องการหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟ ๆ หนึ่ง เรามีความหวังเพียงน้อยนิดที่จะหาคำตอบแบบดีที่สุดได้ทุกครั้งด้วยขั้นตอนวิธีที่มีประสิทธิภาพ (อาจจะหาได้สำหรับตัวอย่างที่มีขนาดเล็ก) โดยทั่วไปแล้วเราจะยอมตอบผิดบ้าง ซึ่งวิธีที่อาจจะนำมาใช้มีดังต่อไปนี้
- ใช้การประมาณ เพื่อหาคำตอบที่พิสูจน์ได้ว่าไม่แย่เกินไปนัก
- ใช้ขั้นตอนวิธีที่มีประสิทธิภาพสำหรับบางรูปแบบการกระจายตัวของอินพุต
- จงใจตอบเฉพาะกรณีพิเศษ
- ใช้ฮิวริสติก ซึ่งจะทำให้ขั้นตอนวิธีทำงานได้ดีในหลาย ๆ กรณี แต่ไม่สามารถพิสูจน์อะไรได้เลย ในบางทีอาจจะได้คำตอบที่แย่เกินกว่าจะรับได้
 |
บทความนี้ยังเป็นโครง คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล หมายเหตุ: ขอแนะนำให้จัดหมวดหมู่โครงให้เข้ากับเนื้อหาของบทความ (ดูเพิ่มที่ วิกิพีเดีย:โครงการจัดหมวดหมู่โครงที่ยังไม่สมบูรณ์) |