Sakidus
 | บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
การค้นทาบู (อังกฤษ:Tabu search) เป็นการค้นหาข้อมูลในคอมพิวเตอร์แบบวิธีโคจรตามเส้นกราฟ โดยการค้นทาบูเพิ่มประสิทธิภาพการค้นหาตามเส้นกราฟด้วยการใช้โครงสร้างข้อมูลเพื่อจำปัญหาที่ได้แก้และทราบคำตอบที่ยอมรับได้แล้ว ไม่กลับมาแก้ปัญหาเดิมซ้ำอีกครั้ง
รายละเอียดเบื้องต้น แก้
การค้นทาบูใช้สำหรับแก้ปัญหาคำตอบที่ดีที่สุดในคณิตศาสตร์เชิงการจัด ตัวอย่างเช่น ปัญหาเดินทางของพนักงานขาย (Travelling salesman problem) กระบวนการทำงานของการค้นทาบูคือในแต่ละรอบการทำงานปัจจุบันจะเลือกผลเฉลยบริเวณใกล้เคียงที่มีคะแนนสูงที่สุดจากฟังก์ชันประเมิณผลที่กำหนดขึ้น แล้วเคลื่อนย้ายจากผลเฉลยปัจจุบันไปแก้ปัญหาของผลเฉลยบริเวณใกล้เคียงจนกระทั่งพบเกณฑ์ที่เหมาะสมจึงหยุดการค้นหา ผลเฉลยที่ถูกแก้และยอมรับแล้วในรอบทำงานปัจจุบันจะถูกบันทึกไว้ในรายการต้องห้าม (tabu list) โดยในการแก้ปัญหาในรอบถัดไปจะรวมการพิจารณาผลจากรายการต้องห้าม ซึ่งเป็นผลเฉลยจากเส้นทางที่ได้เคลื่อนผ่านมาแล้ว ไม่กลับไปพิจารณาปัญหาซ้ำอีก เป็นการบังคับให้แผ่ขยายขอบเขตการค้นหาไปยังส่วนที่ยังไม่ได้รับการค้นหา
ตัวอย่างปัญหา การเดินทางของพนักงานขาย แก้
ปัญหาเดินทางของพนักงานขายสินค้าเป็นตัวอย่างการทำงานของการค้นแบบทาบู โดยพนักงานขายต้องการเดินทางไปตามเมืองต่าง ๆ เพื่อขายสินค้า แต่การเดินทางมีได้หลายรูปแบบขึ้นกับจำนวนเมืองที่ต้องไป ปัญหานี้ต้องการหาเส้นทางการเดินทางไปทั่วทุกเมืองแล้วได้ระยะทางรวมสั้นที่สุด ตัวอย่างเช่นถ้าเมือง ก และเมือง ข อยู่ติดกันและมีเมือง ค ซึ่งอยู่ห่างออกไป ระยะทางที่ใช้ในการเดินทางไปทั้งสามเมือง โดยเดินทางผ่านเมือง ก และ ข ก่อนจากนั้นไปสิ้นสุดที่เมือง ค จะน้อยกว่าการเดินทางจากเมือง ก หรือ ข ไปเมือง ค แล้วกลับยังเมืองที่เหลือ เนื่องจากการหารูปแบบการเดินทางที่ดีที่สุดของปัญหาการเดินทางของพนักงานขายเป็นปัญหาเอ็นพีชนิดยาก วิธีการประมาณแบบฮิวริสติกจึงเป็นวิธีที่ใช้ได้ดี
บรรณานุกรม แก้
- Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer, Norwell, MA.
- Cvijovic, D.; Klinowski, J. "Taboo search - an approach to the multiple minima problem". Science 1995 267, 664-666.