อัลกอริทึมแบบละโมบ

เราได้ศึกษากลวิธีกำหนดการพลวัตเพื่อหาคำตอบดีที่สุดของ optimization problems ซึ่งได้มาจากลำดับของการตัดสินใจ โดยที่การตัดสินใจหนึ่งๆ นั้นตั้งอยู่บนคำตอบย่อย ๆ ของปัญหาที่มีขนาดเล็กกว่า (นั่นคือ ต้องหาคำตอบดีสุดของปัญหาเล็ก ๆ ทั้งหมดก่อน เพื่อใช้หาพิจารณาหาคำตอบดีสุดของปัญหาที่ใหญ่ขึ้น)  ในบทนี้เราจะมาศึกษาอัลกอริทึมแบบละโมบ (greedy algorithm) ซึ่งใช้กับปัญหาการหาค่าเหมาะที่สุดเช่นกัน โดยคำตอบของปัญหาได้มาจากลำดับของการตัดสินใจแบบละโมบ โดยใช้เกณฑ์อะไรบางอย่างที่ให้ผลดีที่สุดจากสภาพของปัญหา ณ ขณะนั้น (จึงเรียกว่า การตัดสินใจอย่างละโมบ เพราะไม่คิดไกล คิดจากสภาพที่เป็นอยู่ในปัจจุบัน)  มักมีการทำงานที่รวดเร็ว แต่มักไม่ได้คำตอบที่ดีสุดอย่างที่ต้องการ อย่างไรก็ตาม มีหลายปัญหา ที่สามารถพิสูจน์ได้ว่า การทำงานแบบละโมบนั้นก็ได้คำตอบที่ดีสุดได้ ในเวลาอันรวดเร็ว