การค้นหาแบบบีม

การค้นแบบบีม (อังกฤษ: Beam Search) เป็นขั้นตอนวิธีในการค้นหาโดยใช้หลักการศึกษาสำนึก โดยแทนที่จะขยายทุกปมในกราฟ การค้นแบบบีมจะเลือกขยายเฉพาะปมจำนวนหนึ่งที่มีโอกาสนำไปสู่คำตอบมากที่สุดความแตกต่างระหว่างการค้นแบบบีมกับการค้นตามแนวกว้างคือ ถึงแม้ว่าการค้นตามแนวกว้าง รับรองว่าการค้นจะเจอเส้นวิธีที่สั้นที่สุด (shortest path) จากจุดเริ่มต้นไปยังจุดเป้าหมาย แต่การเลือกใช้การค้นตามแนวกว้างกับปริภูมิการค้น (search space) ที่ใหญ่นั้นไม่สะดวก เพราะว่า หน่วยความจำที่ใช้มีอัตราการเติบโดแบบอัตราก้าวหน้า (exponential growth) ดังนั้นการค้นแบบแนวกว้างมักจะใช้หน่วยความจำจนหมดก่อนที่จะเจอคำตอบ ด้วยเหตุผลนี้การค้นแบบบีมจึงถูกสร้างขึ้นมาเพื่อพยายามหาคำตอบที่ดีที่สุดที่ได้จากการค้นตามแนวกว้างโดยไม่ใช้หน่วยความจำมากเกินไปการค้นแบบบีมใช้การค้นตามแนวกว้างในการสร้างต้นไม้ค้นหา ในแต่ละสถานะของการค้น มันจะสร้างปมลูกของปมปัจจุบัน ซึ่งแทนที่จะเก็บทุกปมลูกที่พบ มันจะเรียงลำดับปมลูกจากน้อยไปมากตามจากค่าศึกษาสำนึก (heuristic cost) และเลือกเก็บเฉพาะปมลูกไว้จำนวนหนึ่งตามค่าที่กำหนดไว้ก่อนหน้า ที่เรียกว่าความกว้างของบีม (beam width) ยิ่งค่าความกว้างของบีมมากเท่าไหร่ ปมลูกหรือสถานะ (partial solution state) ก็จะถูกตัดทิ้งน้อยลงเท่านั้น หากค่าความกว้างของบีมมีไม่จำกัด การค้นมีลักษณะเหมือนกับการค้นตามแนวกว้าง กล่าวคือความกว้างของบีมเป็นตัวกำหนดขอบเขตของหน่วยความจำที่ใช้ในการค้นหานั่นเองอย่างไรก็ตามสถานะเป้าหมาย (goal state) อาจถูกตัดทิ้งไปขณะที่ทำการค้นเพราะค่าความกว้างของบีมน้อยเกินไป โดยการค้นแบบบีมแลกความสมบูรณ์ (การรับรองว่าขั้นตอนวิธีจะพบคำตอบ ถ้าสามารถหาคำตอบได้) และคำตอบที่ดีที่สุด (การรับรองว่าขั้นตอนวิธีจะเจอคำตอบที่ดีที่สุด) กับความสามารถในการประหยัดหน่วยความจำ

ใกล้เคียง

การค้าประเวณี การค้าประเวณีเด็ก การค้าประเวณีในประเทศไทย การค้นหาแบบทวิภาค การค้าเครื่องเทศ การค้นหาแบบเอสตาร์ การค้นหาและกู้ภัยในเขตเมือง การค้นหาในแนวกว้าง การค้าระหว่างประเทศ การค้นหาในแนวลึกแบบวนเพิ่มความลึก