อัลกอริทึม Greedy Search เป็นวิธีการแก้ปัญหาที่เลือกตัวเลือกที่ดีที่สุดในแต่ละขั้นตอนเสมอ โดยไม่คำนึงถึงผลกระทบระยะยาวของการตัดสินใจ แม้ว่าจะไม่รับประกันว่าจะพบโซลูชันที่เหมาะสมที่สุดทั่วโลก แต่วิธีนี้มักได้ผลอย่างรวดเร็วและง่ายต่อการนำไปใช้
มันทำงานอย่างไร
- การเริ่มต้น: เริ่มด้วยวิธีการแก้ปัญหาที่ว่างเปล่าหรือเริ่มต้น
- ตัวเลือกที่เหมาะสมที่สุดในท้องถิ่น: ในแต่ละขั้นตอน ให้เลือกตัวเลือกที่เหมาะสมที่สุดในพื้นที่ตามฟังก์ชันวัตถุประสงค์หรือเกณฑ์ที่กำหนด
- ใช้ตัวเลือก: ใช้ตัวเลือกที่เหมาะสมที่สุดกับโซลูชันปัจจุบัน
- ทำซ้ำ: ทำซ้ำขั้นตอนที่ 2 ถึง 4 จนกว่าจะไม่สามารถทำการเลือกในท้องถิ่นที่ดีกว่านี้ได้
ตัวอย่าง: Knapsack Problem
พิจารณา Knapsack Problem, โดยที่เรามีเป้ที่มีน้ำหนักสูงสุดและรายการสิ่งของที่มีน้ำหนักและค่าต่างๆ เป้าหมายคือการเลือกสิ่งของเพื่อเพิ่มมูลค่ารวมในกระเป๋าเป้ให้สูงสุด วิธีการค้นหาแบบโลภสำหรับปัญหานี้คือการเลือกรายการตามอัตราส่วนมูลค่าต่อน้ำหนักสูงสุด
ตัวอย่างโค้ดในภาษา C++
ในตัวอย่างนี้ เราใช้วิธี Greedy Search เพื่อแก้ปัญหา Knapsack Problem. เราจัดเรียงสิ่งของตามอัตราส่วนมูลค่าต่อน้ำหนักจากมากไปหาน้อย และเลือกสิ่งของที่มีอัตราส่วนสูงสุดซึ่งยังคงพอดีกับน้ำหนักที่จำกัดของกระเป๋าเป้