ช่วงนี้กำลังเมามันกับ approximation algorithms มาก เพื่อน ๆ อาจสงสัยว่ามันคืออะไร
ยังงี้ครับ สมมติว่าในโรงงาน เราต้องการที่จะหาค่าใช้จ่ายที่ตำ่ที่สุด แต่หาไม่ได้ “ง่าย” ๆ เราจะทำอย่างไรนะครับ approximation algorithms เป็นวิธีที่ให้คำตอบที่การันตีได้ว่าไม่เกินเท่าไร (เช่น ไม่เกิน 2 เท่า) ของค่าใช้จ่ายที่ตำ่ที่สุดได้นะครับ
ในกรณีของการค่าที่มากที่สุด ก็สามารถทำได้เช่นเดียวกันครับ เพื่อน ๆ ประหลาดใจไหมครับที่เราสามารถทำแบบนี้ได้ ทั้ง ๆ ที่เราไม่รู้ว่าค่าใช้จ่ายที่น้อยที่สุดคืออะไร
วิธีอื่น ๆ ที่ใช้แก้ปัญหาประเภทนี้ (optimization problems) ไม่สามารถให้การันตีได้นะครับ
วิชานี้ไม่มีสอนในเมืองไทย (เท่าที่ทราบ) แต่สามารถเรียนได้จาก MIT OCW ครับ
หากใครชอบอะไรแบบนี้ ผมแนะนำให้เรียน online algorithms กับ competitive analysis ด้วยครับ อันคือ approximation algorithms ที่ไม่รู้ข้อมูลเข้าทั้งหมดล่วงหน้าครับ ยังไม่มีสอนในเมืองไทยเช่นกัน แต่มีสอนที่ MIT OCW ครับผม