การค้นหาแบบทาบู

การค้นทาบู (อังกฤษ: 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.