ทำความเข้าใจกับความซับซ้อนของ NP: คำจำกัดความและตัวอย่าง
NP ย่อมาจาก "เวลาพหุนามที่ไม่สามารถกำหนดได้" เป็นคลาสความซับซ้อนที่หมายถึงระยะเวลาที่ต้องใช้ในการแก้ไขปัญหา ใน NP เวลารันของอัลกอริธึมสามารถเป็นพหุนามในขนาดของอินพุต แต่ก็สามารถไม่กำหนดได้ด้วยเช่นกัน ซึ่งหมายความว่าเวลารันอาจแตกต่างกันไปขึ้นอยู่กับโซลูชันเฉพาะที่เลือกโดยอัลกอริธึม
อีกนัยหนึ่ง NP คือ ประเภทของปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามบนเครื่องจักรที่ไม่สามารถกำหนดได้ เครื่องจักรที่ไม่สามารถกำหนดได้คือเครื่องจักรที่สามารถลองวิธีแก้ไขปัญหาที่เป็นไปได้ทั้งหมดพร้อมกัน และยอมรับเครื่องแรกที่ใช้งานได้ ซึ่งช่วยให้เครื่องสามารถแก้ไขปัญหาบางอย่างได้เร็วกว่าเครื่องที่กำหนดขึ้นมาก ซึ่งสามารถลองวิธีแก้ปัญหาได้ครั้งละหนึ่งเครื่องเท่านั้น
ตัวอย่างบางส่วนของปัญหาใน NP ได้แก่:
* ปัญหาพนักงานขายที่กำลังเดินทาง (ให้รายชื่อเมืองและระยะทางเป็นคู่ของเมือง ค้นหาเส้นทางที่สั้นที่สุดเท่าที่จะเป็นไปได้ซึ่งเยี่ยมชมแต่ละเมืองเพียงครั้งเดียว)
* ปัญหาเกี่ยวกับกระเป๋าเป้สะพายหลัง (โดยพิจารณาจากชุดสิ่งของ น้ำหนัก และมูลค่าของสิ่งของเหล่านั้น ให้กำหนดชุดย่อยของสิ่งของที่จะรวมไว้ในกระเป๋าเป้สะพายหลังที่มีความจุจำกัดซึ่งจะทำให้มูลค่ารวมสูงสุด)
* ปัญหาความพึงพอใจแบบบูลีน (กำหนดชุดของตัวแปรบูลีนและข้อจำกัดของตัวแปรเหล่านั้น ให้พิจารณาว่ามีการมอบหมายค่าให้กับตัวแปรที่เป็นไปตามข้อจำกัดทั้งหมดหรือไม่) คลาสความซับซ้อนของ NP มีความสำคัญเนื่องจากมันรวมปัญหามากมายที่ยากต่อการแก้ไขในพหุนาม เวลา แต่สามารถตรวจสอบได้อย่างรวดเร็วด้วยเครื่องกำหนด ซึ่งหมายความว่าแม้ว่าอัลกอริทึมอาจไม่สามารถค้นหาวิธีแก้ปัญหาในเวลาพหุนามได้ แต่ก็ยังมีประโยชน์หากสามารถตรวจสอบวิธีแก้ปัญหาที่เสนอได้อย่างรวดเร็ว
ฉันชอบวิดีโอนี้
ฉันไม่ชอบวิดีโอนี้
รายงานข้อผิดพลาดของเนื้อหา
share
