Approximation Algorithm — กระบวนท่าที่ดีพอ

สมมติว่า เราเป็นบริษัทขนส่งแห่งหนึ่ง ซึ่งจำเป็นต้องส่งของให้กับลูกค้า 7 คน ตามที่ต่างๆ ในกรุงเทพฯ เราจะมีวิธีในการขนส่งกี่แบบ

คำตอบก็น่าจะเป็นนับไม่ถ้วน

แต่ถ้าเราต้องการหาเส้นทางที่สั้นที่สุด ประหยัดน้ำมันที่สุด หรือใช้เวลาน้อยที่สุด คำตอบก็น่าจะมีเส้นทางไม่เยอะนัก

ลักษณะของปัญหาที่เราต้องหาทางออกที่ดีที่สุด ท่ามกลางทางที่เป็นไปได้ เราจะเรียกมันว่า Optimization Problem

ซึ่งปกติแล้ว การหาคำตอบที่ดีที่สุด ก็มักจะใช้เวลาที่แปรผันกับขนาดของที่ ๆ ต้องการค้นหา เช่น ถ้าเราต้องคิดจะหาเส้นทางที่ดีที่สุดในการส่งของให้ลูกค้าที่อยู่ในกรุงเทพฯ​ ย่อมจะใช้เวลามากกว่าการหาเส้นทางที่ดีที่สุดในการส่งของให้กับลูกค้าที่เกาะหลีเป๊ะแน่นอน

แนวโน้มของเวลาที่ใช้ที่มากเกินไปในการแก้ปัญหา

เป็นเรื่องที่โชคดีที่ในเราสามารถประมาณแนวโน้มการใช้เวลาในการแก้ปัญหา ให้อยู่ในกรอบของสมการกราฟได้ เช่น

ปัญหา A ถ้ามีข้อมูล 10 อย่าง จะใช้เวลาแก้ไขประมาณ 100 วินาที ข้อมูล 20 อย่างใช้ 400 วินาที จนถึง 100 อย่างใช้เวลา 100000 วินาที อย่างนี้เราก็จะบอกว่า ปัญหา A จะมีแนวโน้มการใช้เวลาอยู่ประมาณ X² เมื่อ X เป็นจำนวนข้อมูล หรือมีแนวโน้มแบบกราฟพาราโบล่า

ขณะที่ปัญหา B ถ้ามีข้อมูล 10 อย่าง ใช้เวลา 10 นาที ข้อมูล 20 อย่างใช้เวลา 20 นาที ข้อมูล 100 อย่างใช้เวลา 100 นาที ก็จะมีแนวโน้มการใช้เวลาเป็นเส้นตรง

ข้อสังเกตคือ แม้ว่า B จะเป็นหน่วยนาที แต่ในระยะยาว A จะใช้เวลามากกว่า B ในที่สุด

แต่ปัญหา C มีข้อมูล 10 อย่าง ใช้เวลา 1024 วินาที 20 อย่าง ใช้เวลา 1,048,576 วินาที 100 อย่าง ใช้เวลา 1.26 ล้านล้านล้านล้านล้านวินาที ซึ่งถ้าเรามาหาเป็นจำนวนปี เราจะได้ประมาณ 4 แสนล้านล้านล้านปี ซึ่งถ้าเอาจริงๆ แล้วเราก็อยู่ไม่ถึงมันแก้ปัญหาเสร็จ โลกก็อาจจะแตกก่อนที่จะแก้ปัญหาเสร็จก็ได้ ตรงนี้มีแนวโน้มเป็น 2^X หรือถ้าเป็นกราฟก็จะเป็น Exponential เลยทีเดียว

ดังนั้น เราจะถือว่า ปัญหาแบบ C ในทางปฎิบัติก็คือน่าจะหาวิธีที่ดีที่สุดได้ยากมากๆ นั่นเอง

บางครั้งคำตอบที่ดีพอก็เพียงพอ

เมื่อเราไม่สามารถที่จะหาวิธีแก้ปัญหาที่ดีที่สุด และใช้เวลาที่เหมาะสมได้ (ในทางทฤษฎีมันก็มีวิธีหาแหละ แต่กว่าจะ Execute จบได้ โลกแตกก่อน)​ ทางเลือกคือ

ลดความซีเรียสของคำว่าดีที่สุดซะ แล้วหาทางแก้ที่ดีพอและสามารถอยู่ในกรอบเวลาที่เป็นไปได้ได้

นั่นจึงเป็นที่มาของ Approximation Algorithm ซึ่งวิธีการนี้ แม้จะไม่รับประกันว่าจะได้ผลลัพธ์ที่ดีที่สุด แต่ก็ได้ผลลัพธ์ที่ดีเพียงพอ ภายใต้เวลาที่เหมาะสม ที่จะทำให้ทำงานต่อได้

วิธีการที่เหมาะสมในโลกแห่งความจริง

Approximation Algorithm อยู่ในวิชา Algorithm ของหลักสูตรเกี่ยวกับ Computer Science / Engineer ในทุกที่ แต่มักจะเป็นกระบวนท่าที่ถูกลืมด้วย ความที่มันมีการพิสูจน์มายุ่ง และมันไม่ค่อยเท่ แบบพวก Divide & Conquer, Dynamic Programming หรือ Greedy Algorithm ซึ่งพวกนั้นมันการันตีของดีในเวลาที่ดีได้

ปัญหาคือ ในชีวิตจริงมันไม่ค่อยจะเจอปัญหาที่ใช้ท่าสามเทพนั้น แล้วได้ผลหล่อๆแบบในที่เรียนสักเท่าไหร่ และท่าที่การันตีของดีในเวลาที่ดี ส่วนใหญ่ก็จะถูก package เป็น Library สวยงาม หรือเป็น Best Practice ให้เรียบร้อยแล้ว

ขณะที่เรายังต้องแก้ปัญหาภายใต้เวลาที่จำกัดกว่าโลกแตกอีก เช่น ต้องจัดการให้เสร็จใน 1 ปี 6 เดือน

นอกจากนี้ก็อาจจะมีคำถามว่า คำว่าดีที่สุด มันคุ้มหรือไม่

เช่น ถ้าเราใช้พื้นที่เก็บไฟล์สำหรับ JPEG ให้คุณภาพดีที่สุด จะใช้พื้นที่ 4 MB แต่ถ้าเราใช้พื้นที่ 500​KB เราจะยังคงได้คุณภาพที่ 80% ของคุณภาพที่ดีที่สุด

คุณภาพ vs ขนาดไฟล์ของ JPEG cr: https://www.impulseadventure.com/photo/jpeg-compression.html

หรือในการทำงานของเราเองที่งาน 80% ของทั้งหมดมักจะเสร็จภายใน 20% ของเวลาที่ใช้ทั้งหมด ขณะที่ถ้าเราจะพยายามจัดการ 20% ที่เหลืออยู่ ก็จะใช้เวลาอีก 80% (Pareto Principle)

ในโลกแห่งความจริง จะมีกรอบเวลาหรือกรอบทรัพยากร ควบคุมผลลัพธ์เสมอ

ส่งท้าย

ทุกคนคาดหวังสิ่งที่ดีที่สุด แต่กรอบเวลาและทรัพยากร มักจะทำให้เราต้องเลือกทางที่ดีพอมาใช้ อย่างไรก็ตามด้วยชั่วโมงบินและประสบการณ์จะทำให้ “ดีพอ” ดีขึ้นเรื่อยๆ ตราบที่เราจะยังมีใจจะพัฒนามันอยู่ ถึงจุดนั้น มันจะเป็น ดีพอที่ 99% ก็เป็นได้

เพราะ Engineer มีหน้าที่ Optimize ผลลัพธ์ ภายใต้ทรัพยากรที่จำกัดนั่นเอง