การค้นหาแบบกองซ้อนบีม

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

แนวคิด

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

การใช้งาน

การค้นหาแบบกองซ้อนบีมสามารถมองเป็นเหมือน การค้นตามแนวกว้างแบบขยายและจำกัดเขต (breadth first search branch-and-bound) ที่ปรับปรุงให้ไม่มีการเก็บปมไว้มากกว่าความกว้างบีม (beam width)

โดยการค้นหาจะทำโดยขยายตามแนวกว้าง(breadth first) และใช้ค่าในการตัดสินใจเพื่อจะตัดปมออกจากการค้นหาเป็น

f(n)=g(n)+h(n)

เมื่อ f(n) เป็นค่าที่พิจารณาของปม n

g(n) เป็นค่าที่ดีที่สุดจากจุดเริ่มจนถึงปม n

h(n) เป็นค่าประมาณที่ใช้จากจุด n ไปจนถึงเป้าหมาย

เพื่อที่จะทำการย้อนรอยได้ จะต้องเก็บค่าของแต่ละชั้นที่ทำการค้นหา โดยจะเก็บปมที่ผ่านการค้นหาลงในกองซ้อน และต้องมีการจำด้วยว่าปมลูกของปมนั้นๆ มีปมใดผ่านการค้นหาแล้ว และปมใดที่ยังไม่ผ่านการค้นหา

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

เมื่อมีการค้นหาไปแล้วมีการเก็บปมมากกว่าความกว้างบีม จะทำการตัดปมที่เก็บออกเพื่อให้สามารถทำงานต่อได้โดยไม่ต้องเก็บปมไว้มากกว่าความกว้างบีม โดยจะเริ่มตัดจากปมที่มีค่า f สูงที่สุด และไปแก้ขอบเขตการหาของปมแม่ของปมนั้น เมื่อมีการย้อนรอยขึ้นไป ปมที่ถูกตัดจะได้ถูกค้นหาอีกรอบ

วิเคราะห์การทำงาน

ความสมบูรณ์ของขั้นตอนวิธี (Completeness)

การค้นหาแบบกองซ้อนบีม มีความสมบูรณ์ กล่าวคือหากมีผลเฉลย การค้นหาแบบกองซ้อนบีมจะหาเจอ และจะหาเจอคำตอบที่ดีที่สุดเท่าที่จะมีเมื่อการค้นหาเสร็จ

การทำงานเชิงหน่วยความจำ (Space Complexity)

การค้นหาแบบกองซ้อนบีม จะใช้หน่วยความจำในการค้นหาขึ้นอยู่กับความกว้างบีม และความสูงของต้นไม้ที่ทำการค้น โดยให้ต้นไม้ที่ค้นสูง d และมีความกว้างบีม w จะใช้พื้นที่หน่วยความจำเป็น O(wd)

เปรียบเทียบการทำงาน

การทำงานของการค้นหาแบบกองซ้อน จะขึ้นอยู่กับการกำหนด ความกว้างบีม โดยเมื่อกำหนดให้เท่ากับ 1 จะทำงานเหมือนกับ การค้นตามแนวลึก และเมื่อกำหนดความกว้างบีมให้ไม่จำกัด จะทำงานเหมือนกับการค้นตามแนวกว้าง

อ้างอิง

• Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005.