อัลกอริทึม Local Search เป็นวิธีการค้นหาโซลูชันที่ดีที่สุดภายในบริเวณใกล้เคียงกับสถานะปัจจุบัน เทคนิคนี้มักใช้ในการปรับแต่งวิธีแก้ปัญหาโดยประมาณโดยการปรับเปลี่ยนส่วนประกอบแต่ละส่วนซ้ำๆ เพื่อค้นหาสถานะที่ดีขึ้น
มันทำงานอย่างไร
- การเริ่มต้น: เริ่มต้นด้วยสถานะเริ่มต้น
- สร้างเพื่อนบ้าน: สร้างรัฐเพื่อนบ้านโดยเปลี่ยนส่วนประกอบของสถานะปัจจุบัน
- การประเมิน: ประเมินคุณภาพของรัฐใกล้เคียงโดยใช้ฟังก์ชันวัตถุประสงค์
- เลือกรัฐที่ดีที่สุด: เลือกรัฐใกล้เคียงที่มีค่าวัตถุประสงค์ดีที่สุด
- ทำซ้ำ: ทำซ้ำขั้นตอนที่ 2 ถึง 4 จนกว่าจะไม่พบสถานะเพื่อนบ้านที่ดีกว่า
ตัวอย่าง: การปรับ Fibonacci ฟังก์ชัน ให้เหมาะสม
พิจารณาปัญหาการหาค่าสูงสุดของ Fibonacci ฟังก์ชัน F(x) = F(x-1) + F(x-2) โดยที่ F(0) = 0, F(1) = 1 เราต้องการหาค่าของ x ซึ่ง F(x) ถูกขยายให้ใหญ่สุด เราสามารถใช้วิธีการค้นหาในท้องถิ่นเพื่อสำรวจซ้ำๆ จากแต่ละขั้นตอน
ตัวอย่างโค้ดในภาษา C++
ในตัวอย่างนี้ เราใช้วิธี Local Search เพื่อเพิ่มประสิทธิภาพ Fibonacci ฟังก์ชัน เราวนซ้ำผ่านค่าต่างๆ ของ x และคำนวณ Fibonacci ค่าที่แต่ละ x เมื่อพบค่าที่ดีกว่า เราจะอัปเดตค่าที่ดีที่สุดและค่า x ที่สอดคล้องกัน