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