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