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

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

ขั้นตอนวิธีการค้นเฉพาะที่นี้ยังเป็นกลวิธีในการแก้ปัญหาการหาค่าเหมาะที่สุดเชิงการจัด (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 ที่ได้เราพอใจ

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

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

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

 อ้างอิง 
 Local Search Algorithms 
 Heuristic Search Techniques
 การออกแบบอัลกอริทึม

หมวดหมู่:ขั้นตอนวิธีการหาค่าเหมาะที่สุด
หมวดหมู่:ขั้นตอนวิธีการค้นหา