แนะนำหัวข้อ
สามารถดู video ของหัวข้อนี้ก่อนได้ ดู video
Greedy Algorithm คืออะไร
Greedy Algorithm คืออัลกอริทึมที่ใช้วิธีการแก้ปัญหาแบบ heuristic โดยการเลือกทางเลือกที่ดูเหมือนจะเป็นตัวเลือกที่ดีที่สุดในขณะนั้นมาใช้ในแต่ละขั้นตอน อัลกอริทึมแบบ Greedy มักจะให้ผลลัพธ์ที่ดี แต่ไม่ได้รับประกันว่าจะเป็นคำตอบที่ดีที่สุดเสมอไป
ลักษณะสำคัญของอัลกอริทึมแบบ Greedy ได้แก่
- เลือกทางเลือกที่ดูเหมือนจะเป็นตัวเลือกที่ดีที่สุดในขณะนั้น โดยไม่คำนึงถึงผลกระทบในอนาคต
- "ทำงานแบบขั้นตอนเดียว" ไม่มีการย้อนกลับไปแก้ไขการตัดสินใจก่อนหน้า
ตัวอย่างของอัลกอริทึมแบบ Greedy เช่น
- Dijkstra's algorithm สำหรับหาเส้นทางที่สั้นที่สุดในกราฟ (เราจะคุยกันในหัวข้อ Graph Algorithms อีกที)
- Huffman coding สำหรับการบีบอัดข้อมูล
- Kruskal's algorithm และ Prim's algorithm สำหรับหา minimum spanning tree (เราจะคุยกันในหัวข้อ Advance Tree DSA อีกที)
อย่างไรก็ตาม อัลกอริทึมแบบ Greedy ก็มีข้อจำกัด เช่น
- ไม่ได้ให้คำตอบที่ดีที่สุดเสมอไป เนื่องจากมองแค่ทางเลือกที่ดีที่สุดในขณะนั้น
- ไม่มีการตรวจสอบความถูกต้องของผลลัพธ์ เพราะทำงานแบบขั้นตอนเดียว
ดังนั้น การใช้ Greedy algorithm ต้องคำนึงด้วยว่า "เราต้องมั่นใจด้วยว่านี่คือวิธีการที่ถูกต้องแล้วจริงๆ" เพราะ จุดเด่นใหญ่ๆของ solution ที่เป็น Greedy algorithm คือ มี complexity ที่น้อย (big O จะขนาดเล็ก) เนื่องจากการทำงานจะทำเพียงแค่ครั้งเดียวในการหาคำตอบออกมาเท่านั้น อัลกอริทึมแบบ Greedy เลยมีประโยชน์ในการแก้ปัญหาที่ต้องกา รหาค่าที่มากที่สุดหรือน้อยที่สุด เพราะให้ผลลัพธ์ที่ดีและรวดเร็ว จึงนิยมนำมาประยุกต์ใช้อย่างแพร่หลายในเคสเหล่านี้เป็นต้น