นิยาม ของ การค้นหาแบบสองทิศทาง

การค้นหาแบบสองทิศทางนั้นโดยนิยามแล้วก็คือขั้นตอนวิธีที่ใช้หลักการซึ่งคล้ายกับขั้นตอนวิธีแบ่งแยกเพื่อเอาชนะ(อังกฤษ: Divide and conquer)ในกรณีที่เราทราบตำแหน่งของเป้าหมายที่จะค้นหาแล้ว แทนที่จะค่อยๆเริ่มจากจุดเริ่มต้นไปยังจุดปลายเราจะทำการค้นหาจากจุดปลายย้อนกลับมาหาจุดเริ่มต้นไปพร้อมๆกันแทน ด้วยวิธีนี้ความเร็วในการค้นหาของแต่ละเส้นทางจะอยู่ที O (bd/2) เมื่อ b {\displaystyle b} คือจำนวนการแตกกิ่งก้าน (Branching factor) และ d {\displaystyle d} คือระยะทางทั้งหมดจากจุดเริ่มต้นไปยังจุดสิ้นสุด ซึ่งเมื่อนำระยะเวลาการค้นหามารวมกันแล้วก็ยังถือว่าได้ลดเวลาในการค้นหาลงไปอย่างมากหากเทียบกับการค้นหาแบบปกติ O (bd)

อย่างไรก็ตามแม้ว่าวิธีการนี้จะดูเหมือนว่าสามารถที่จะลดเวลาการค้นหาไปได้อย่างมากก็ตาม ข้อเสียของมันก็ยังมีอยู่หลายข้อด้วยกันคือ

  • วิธีการค้นหาแบบสองทิศทางมีลักษณะที่เป็นศึกษาสำนึกหรือก็คือไม่สามารถบอกได้อย่างแน่นอนว่าเส้นทางที่หาได้เป็นเส้นทางที่ดีที่สุดหรือไม่
  • ในการออกแบบขั้นตอนวิธีจำเป็นที่จะต้องคิดหาวิธีการที่จะทำให้สามารถค้นหาจากจุดปลายให้ย้อนกลับมายังจุดเริ่มต้นได้
  • ต้องออกแบบวิธีการหาจุดเชื่อมต่อที่มาจากการค้นของทั้งสองทิศทาง
  • ต้องมีการกำหนดเป้าหมายว่าอยู่ที่ใดบนกราฟ

ด้วยสาเหตุทั้งปวงที่กล่าวมาทำให้การนำเอาวิธีการค้นหาแบบสองทิศทางไปใช้งานจริงนั้นจึงยุ่งยากพอสมควร

ใกล้เคียง