การค้นหาเฉพาะที่

การค้นหาเฉพาะที่ (อังกฤษ: local search) เป็นกลวิธีในการใช้ค้นหาคำตอบแบบหนึ่ง จากเซตของผลเฉลยที่มีขนาดใหญ่มากๆ ซึ่งเป็นไปไม่ได้ที่จะตรวจสอบผลเฉลยทั้งหมดเพื่อให้เจอผลเฉลยที่ดีที่สุด โดยจะมีฟังก์ชันต้นทุนสำหรับพิจารณาแต่ละผลเฉลย เพื่อเปลี่ยนแปลงสถานะของผลเฉลยปัจจุบันที่ค้นหา ไปจนกว่าจะเจอผลเฉลยที่เราพอใจ

ขั้นตอนวิธีการค้นเฉพาะที่นี้ยังเป็นกลวิธีในการแก้ปัญหาการหาค่าเหมาะที่สุดเชิงการจัด (combinatorial optimization problem) ซึ่งเป็นปัญหาเอ็นพีแบบยาก (NP-hard) อีกทั้งยังถูกนำไปประยุกต์ใช้ในหลากหลายวงการ ซึ่งสามารถหาผลเฉลยที่ดีได้สำหรับปัญหาที่พบในทางปฏิบัติ

กระบวนการทำงาน

ขั้นตอนวิธีการค้นเฉพาะที่จะเริ่มต้นจาก s โดยเป็นผลเฉลยหนึ่งที่อยู่ใน S โดย S เป็นเซตของผลเฉลยที่เป็นไปได้ทั้งหมดของปัญหา แล้วค่อยๆ ตรวจสอบผลเฉลยที่ไม่ห่างไกลจาก s มากไปเรื่อยๆ ว่ามีผลสัมฤทธิ์ที่ดีขึ้นหรือไม่ โดยเราจะมีฟังก์ชัน f(s) สำหรับใช้การคำนวณต้นทุนของผลเฉลย s ฟังก์ชันนี้จะใช้เป็นดัชนีชี้วัดความเหมาะสมของแต่ละผลเฉลย

localSearch()
{
	s = initialSolution()
	while not terminate(s) {
		s' = select( next(s) )
		if( accept(s,s') ) then s = s'
	}
}

รหัสเทียมข้างต้นเป็นแนวการทำขั้นตอนวิธีการค้นหาเฉพาะที่ โดยเริ่มต้นจะเริ่มจาก initialSolution() แล้วทำงานแบบวนซ้ำสำหรับในการหาผลเฉลยที่เป็นเพื่อนบ้านกับ s คือ s' โดยมีฟังก์ชัน select() เป็นตัวเลือกตัวที่พิจารณา หากผลเฉลย s' ดีกว่า s ก็จะแทนที่ s ด้วย s' โดยมี accept() เป็นตัวตัดสินว่าจะยอมรับ s' หรือไม่ การทำซ้ำนี้จะทำไปเรื่อยๆ จนกว่าความเหมาะสมของ s ที่ได้เราพอใจ

ขั้นตอนวิธีการค้นหาเฉพาะที่นี้มีหัวใจสำคัญอยู่ที่ฟังก์ชันต้นทุน หากกำหนดดีๆ การค้นหาคำตอบก็จะมีประสิทธิภาพ

ลักษณะการค้นหาเฉพาะที่นี้ ถูกนำไปใช้กับขั้นตอนวิธีเกี่ยวกับการค้นหาในแบบอื่นๆ อยู่มากมาย

ตัวอย่างขั้นตอนวิธีที่ใช้การค้นหาเฉพาะที่

1. กลวิธีการค้นอย่างไต่เขา (Hill Climbing) หรือ กลวิธีการค้นแบบสืบเชื้อสายอย่างง่าย (Simple descent)
2. กลวิธีการค้นแบบสืบเชื้อสายอย่างสูงชัน (Steepest descent)
3. Simulated annealing
4. การค้นทาบู (Tabu search)
5. ขั้นตอนวิธีเชิงพันธุกรรม (Genetic algorithm)

อ้างอิง

• Local Search Algorithms เก็บถาวร 2011-08-20 ที่ เวย์แบ็กแมชชีน
• Heuristic Search Techniques
• การออกแบบอัลกอริทึม