อ้างอิง:
ข้อความเดิมของคุณ tana:
อยากทราบความแตกต่างของปัญหา NP , NP complete , NP Hard น่ะครับ ช่วยอธิบายพร้อมยกตัวอย่างให้ดูหน่อยนะครับ ว่ามีอะไรบ้าง แล้วยังมี NP ชนิด อื่นอีกรึป่าวครับ
|
ตอบให้คร่าวๆ ระดับหนึ่งแล้วกันนะครับ
ปัญหา NP ก็คือ ปัญหาที่มนุษย์ไม่สามารถรอคอยผลได้ ด้วยการ run program บนคอมพิวเตอร์ที่ใช้กันทั่วๆไป เพราะเวลาที่ใช้คำนวณ อาจเติบโตด้วย exponential rate ของจำนวน input
บางปัญหา อาจกินเวลาเป็นหลายๆพันปี ถ้ามีข้อมูลมากๆ
แต่ NP จะ solve ให้เสร็จแบบเร็วๆ ด้วยการ run algorithm บน processor กลุ่ม nondeterministic turing machine ซึ่งไอ้เจ้า processor แบบที่ว่า เป็น คอมพิวเตอร์ใน จินตนาการ พอสมควร (อย่าถามผมต่อนะ ว่าหลักการของ turing machine ชนิดนี้เป็นยังไง อันนี้ไม่รู้จริงๆ)
สำหรับ NP hard จะมีลักษณะที่ว่า ถ้ามี algorithm ที่ solve ปัญหานี้ได้ แล้ว จะสามารถแปลง solution ไปสู่การแก้ปัญหาอื่นๆใน NP ได้ด้วย
NP hard อาจเป็น NP หรือไม่เป็นก็ได้ ตัวอย่างปัญหาที่เป็น NP hard แต่ไม่เป็น NP เช่น halting problem (
More details about NP hard and halting problem)
ถ้าปัญหาใดเป็นทั้ง NP และ NP hard จะเรียกปัญหานั้นว่า NP Complete (NPC) และเพราะ NPC มีความเป็น NP hard ในตัว ดังนั้น ถ้าสามารถแก้ปัญหาใด ปัญหาหนึ่งในกลุ่ม NP complete ได้ ก็จะ สามารถ แปลง solution ดังกล่าว ไปสู่การแก้ปัญหาทุกๆ ปัญหาในกลุ่ม NP ได้ เรียกได้ว่า แก้เพียง 1 อาจแก้ได้หมดทั้ง group
ตัวอย่างปัญหา NP complete มีมากมาย เช่น การหา hamiltonian cycle ในกราฟ ที่ผมกล่าวไปแล้ว , การหากลยุทธ์ในการเล่นเกม Minesweeper (เกมใน window ที่มีระเบิด ล้อมรอบตัวเลขน่ะครับ) ,ปัญหาการบรรจุของ เช่น ควรจะใช้ thumb drive 128 MB น้อยสุดกี่อัน ถึงจะบรรจุไฟล์สารพัด size ที่มีอยู่ลงไปได้หมด ฯลฯ
ส่วน NP อื่นๆ ไม่น่าจะมีแล้วมั้งครับ
ใครอยากจะเสริมเติมแต่ง หรือจะแก้ไข ก็ตามสบายเลยนะครับ