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

การค้นแบบบีม (Beam Search) เป็นขั้นตอนวิธีในการค้นหาโดยใช้หลักการศึกษาสำนึก โดยแทนที่จะขยายทุกปมในกราฟ การค้นแบบบีมจะเลือกขยายเฉพาะปมจำนวนหนึ่งที่มีโอกาสนำไปสู่คำตอบมากที่สุด
ความแตกต่างระหว่างการค้นแบบบีมกับการค้นตามแนวกว้างคือ ถึงแม้ว่าการค้นตามแนวกว้าง รับรองว่าการค้นจะเจอเส้นวิธีที่สั้นที่สุด (shortest path) จากจุดเริ่มต้นไปยังจุดเป้าหมาย แต่การเลือกใช้การค้นตามแนวกว้างกับปริภูมิการค้น (search space) ที่ใหญ่นั้นไม่สะดวก เพราะว่า หน่วยความจำที่ใช้มีอัตราการเติบโดแบบอัตราก้าวหน้า (exponential growth) ดังนั้นการค้นแบบแนวกว้างมักจะใช้หน่วยความจำจนหมดก่อนที่จะเจอคำตอบ ด้วยเหตุผลนี้การค้นแบบบีมจึงถูกสร้างขึ้นมาเพื่อพยายามหาคำตอบที่ดีที่สุดที่ได้จากการค้นตามแนวกว้างโดยไม่ใช้หน่วยความจำมากเกินไป
การค้นแบบบีมใช้การค้นตามแนวกว้างในการสร้างต้นไม้ค้นหา ในแต่ละสถานะของการค้น มันจะสร้างปมลูกของปมปัจจุบัน ซึ่งแทนที่จะเก็บทุกปมลูกที่พบ มันจะเรียงลำดับปมลูกจากน้อยไปมากตามจากค่าศึกษาสำนึก (heuristic cost) และเลือกเก็บเฉพาะปมลูกไว้จำนวนหนึ่งตามค่าที่กำหนดไว้ก่อนหน้า ที่เรียกว่าความกว้างของบีม (beam width) ยิ่งค่าความกว้างของบีมมากเท่าไหร่ ปมลูกหรือสถานะ (partial solution state) ก็จะถูกตัดทิ้งน้อยลงเท่านั้น หากค่าความกว้างของบีมมีไม่จำกัด การค้นมีลักษณะเหมือนกับการค้นตามแนวกว้าง กล่าวคือความกว้างของบีมเป็นตัวกำหนดขอบเขตของหน่วยความจำที่ใช้ในการค้นหานั่นเอง
อย่างไรก็ตามสถานะเป้าหมาย (goal state) อาจถูกตัดทิ้งไปขณะที่ทำการค้นเพราะค่าความกว้างของบีมน้อยเกินไป โดยการค้นแบบบีมแลกความสมบูรณ์ (การรับรองว่าขั้นตอนวิธีจะพบคำตอบ ถ้าสามารถหาคำตอบได้) และคำตอบที่ดีที่สุด (การรับรองว่าขั้นตอนวิธีจะเจอคำตอบที่ดีที่สุด) กับความสามารถในการประหยัดหน่วยความจำ
== ชื่อ ==
คำว่า "การค้นแบบบีม" ถูกตั้งโดย ราจ เรดดี้ แห่งมหาวิทยาลัยคาร์เนกี้เมลอนในปี 1976 เนื่องจากคำว่า บีม (beam) ในภาษาอังกฤษแปลว่าคานซึ่งคือโครงสร้างตามแนวกว้างที่ใช้ในการรับน้ำหนัก จึงใช้แทนคำว่าช่วงกว้าง โดยแตกต่างจากการค้นตามแนวกว้าง ตรงที่การค้นตามแนวกว้างจะขยายปมลูกในแต่ละสถานะการค้นทุกปม แต่การค้นแบบบีมจะขยายปมลูกเพียงบางส่วนเท่านั้น
== การใช้งาน ==
การใช้งาน
การค้นแบบบีมถูกใช้ระบบขนาดใหญ่ที่ต้องการความสามารถในการจัดการ โดยมีหน่วยความจำหลักไม่พอที่จะเก็บต้นไม้ค้นหาทั้งต้น เช่น การใช้การค้นหาแบบบีมในระบบการแปลด้วยเครื่อง เพื่อที่จะเลือกแปลให้ดีที่สุด ขณะที่ประมวลผลแต่ละส่วน ก็จะมีคำแปลหลายๆแบบเกิดขึ้นมา คำแปลที่ดีที่สุดจะถูกเก็บไปใช้และทิ้งส่วนที่เหลือไป หลังจากนั้นตัวแปลจะทำการวิเคราะห์ประโยคที่เหลือโดยคิดคะแนนตามข้อกำหนด และเลือกคำแปลที่ดีที่สุดไว้
== รหัสเทียม ==
ขั้นตอนวิธี การค้นแบบบีม
ข้อมูลรับเข้า:
กราฟ G,
โหนด s คือ โหนดที่ต้องการเริ่มต้นการค้น,
โหนด g คือ โหนดเป้าหลายที่ต้องการค้น,
ค่าความกว้างของบีม 'w'
สร้างแถวคอย Q โดยเริ่มต้นให้แถวคอยว่าง
สร้างรายการ Visited สำหรับบอกว่าปมไหนเคยเจอแล้ว โดยเริ่มค้นให้รายการ Visited ว่าง
เพิ่มปมเริ่มต้น s เข้าที่ Q
จนกว่า Q จะว่าง หรือ เจอ g
ให้ u เป็น ปมหน้าสุดในแถวคอย
เอาปม u ออกจากแถวคอย
ถ้า v เป็นปมที่ไม่อยู่ในรายการ Visited
สำหรับทุกปม v ที่เชื่อมกับ u ให้เลือกเพิ่มปม v ที่มีค่าศึกษาสำนึกดีที่สุดจำนวน w ปมต่อที่แถวคอย Q
เพิ่ม u เข้าในรายการ Visited
ถ้า เจอปม g
การค้นหาสำเร็จ
ถ้า ไม่เจอปม g
ค้นหาไม่สำเร็จ
=== ตัวอย่างการทำงาน ===
BeamSearch
==== แบบที่ 1 ====
ให้หาปม H โดยเริ่มจาก A และกำหนดให้ค่าความกว้างของบีม = 2
{|class="wikitable"
|-
! รอบที่
! ปมหน้าสุดของแถวคอย(u)
! ปมที่มีเส้นเชื่อมต่อกับ u เรียงตามค่าศึกษาสำนึก
! ปมที่ในแถวคอย Q หลังจากเพิ่มปมลูกใหม่เข้าไปแล้ว
! ปมในรายการ Visited
! หมายเหตุ
|-
| 0
| -
| -
| {A}
| {}
| -
|-
| 1
| A
| C,D,B
| {C,D}
| {A}
| ปม B ถูกตัดออกเนื่องจากค่าความกว้างของบีม = 2 จึงเลือกเก็บได้ 2 ปมคือปม C,D
|-
| 2
| C
| G
| {D,G}
| {A,C}
| -
|-
| 3
| D
| H
| {G,H}
| {A,C,D}
| -
|-
| 4
| G
| I
| {G,H,I}
| {A,C,D,G}
| -
|-
| 5
| H
| เจอปมเป้าหมายจบการทำงาน
| เจอปมเป้าหมายจบการทำงาน
| เจอปมเป้าหมายจบการทำงาน
| -
|}
คำตอบ คือ เจอปม H
==== แบบที่ 2 ====
ให้หาปม H โดยเริ่มจาก A และกำหนดให้ค่าความกว้างของบีม = 1
{|class="wikitable"
|-
! รอบที่
! ปมหน้าสุดของแถวคอย(u)
! ปมที่มีเส้นเชื่อมต่อกับ u เรียงตามค่าศึกษาสำนึก
! ปมที่ในแถวคอย Q หลังจากเพิ่มปมลูกใหม่เข้าไปแล้ว
! ปมในรายการ Visited
! หมายเหตุ
|-
| 0
| -
| -
| {A}
| {}
| -
|-
| 1
| A
| C,D,B
| {C}
| {A}
| ปม D,B ถูกตัดออกเพราะค่าความกว้างของบีม = 1 ซึ่งเลือกเก็บได้ปมเดียวซึ่งก็คือ C
|-
| 2
| C
| G
| {G}
| {A,C}
| -
|-
| 3
| G
| I
| {}
| {A,C,G}
| -
|-
| 4
| ไม่มีปมเหลือใน Q จบการทำงาน
| ไม่มีปมเหลือใน Q จบการทำงาน
| ไม่มีปมเหลือใน Q จบการทำงาน
| ไม่มีปมเหลือใน Q จบการทำงาน
| -
|}
คำตอบ คือ ไม่เจอปมเป้าหมาย H ดังนั้นจะเห็นว่าการค้นแบบบีมไม่มีความสมบูรณ์ของขั้นตอนวิธีถึงแม้ว่าจะมีปมเป้าหมาย (H) ในปริภูมิการค้นหา เนื่องจากค่าความกว้างของบีมที่น้อยเกินไปทำให้ปม D ซึ่งเป็นวิถีย่อยเดียวที่นำไปสู่ปมเป้าหมาย (H) ถูกตัดออกไป
== วิเคราะห์การทำงาน ==
=== ความสมบูรณ์ของขั้นตอนวิธี (Completeness) ===
โดยทั่วไปการค้นแบบบีมจะไม่มีความสมบูรณ์ คือ ขั้นตอนวิธีนี้มีจะไม่เจอปมที่ค้นหาถึงแม้ว่าจะมีวิธี(path)จากปมเริ่มต้นไปยังปมทีต้องการค้นหาก็ตาม เพราะปมที่นำไปสู่ปมเป้าหมายอาจโดนตัดทิ้งระหว่างการค้นเนื่องจากค่าความกว้างของบีมน้อยเกินไป การขาดความสมบูรณ์ของขั้นตอนวิธีเป็นข้อเสียหนึ่งของการค้นแบบบีม
ซึ่งเราสามารถเพิ่มโอกาสให้เจอปมเป้าหมายได้โดยการ ขยายความกว้างของบีมหรือปรับฟังก์ชันศึกษาสำนึกให้แม่นยำมากขึ้น
ซึ่งทั่วไปที่นิยมทำกันคือเวลาค้นจะไม่จำหนดความกว้างของบีมตายตัวแต่กำหนดเป็นช่วงแทน โดยจะกำหนดค่าเริ่มค้นให้ เมื่อการค้นครั้งแรกไม่สำเร็จก็จะขยายความกว้างให้มากขึ้น
=== ความตอบที่ดีที่สุดที่ได้จากขั้นตอนวิธี (Optimality) ===
เนื่องจากการค้นไม่มีความสมบูรณ์ของขั้นตอนวิธี จึงไม่ยืนยันว่าจะได้คำตอบที่ดีที่สุด เนื่องจากวิถีย่อยของวิถีที่ดีที่สุดอาจโดนตัดออกไปจากการค้นเนื่องจากค่าความกว้างของบีมน้อยเกินไปเช่นกัน
=== ประสิทธิภาพเชิงเวลา (Time Complexity) ===
ถ้าต้นไม้มีความสูงมากสุดไม่เกิน h หน่วย การทำงานเชิงเวลาจะเป็น O(wh) เนื่องจากในแต่ละชั้นของต้นไม้ค้นหามีปมไม่เกิน w ปม ดังนั้นจะมีปมให้ค้นทั้งหมดไม่เกิน wh ปม ทำให้การค้นแบบบีมมีการทำงานเชิงเวลาเป็นแบบเชิงเส้น ซึ่งเป็นจุดเด่นของการค้นแบบบีมที่ขั้นตอนวิธีแบบอื่นที่มีอัตราการเติบโดแบบแบบอัตราก้าวหน้า (exponential growth) ไม่สามารถทำได้ในปริภูมิการค้นหาขนาดใหญ่ได้
=== ประสิทธิภาพเชิงหน่วยความจำ (Space Complexity) ===
ถ้าต้นไม้มีความสูงมากสุดไม่เกิน h หน่วย การทำงานเชิงเวลาจะเป็น O(wh) เนื่องจากในแต่ละชั้นของต้นไม้ค้นหามีปมไม่เกิน w ปม ดังนั้นจะมีปมให้ค้นทั้งหมดไม่เกิน wh ปม ทำให้การค้นแบบบีมมีการทำงานเชิงเวลาเป็นแบบเชิงหน่วยความจำ ซึ่งเป็นจุดเด่นของการค้นแบบบีมที่ขั้นตอนวิธีแบบอื่นที่มีอัตราการเติบโดแบบแบบอัตราก้าวหน้า (exponential growth) ไม่สามารถทำได้ในปริภูมิการค้นหาขนาดใหญ่ได้
== อ้างอิง ==
http://jhave.org/algorithms/graphs/beamsearch/beamsearch.shtml 
http://ai-depot.com/Tutorial/PathFinding-Heuristics.html 
== ศึกษาเพิ่มเติม ==
โครงสร้างข้อมูล (ฉบับวาจาจาวา) โดยสมชาย ประสิทธิ์จูตระกูล
การออกแบบอัลกอริทึม (Algorithm Design) โดยสมชาย ประสิทธิ์จูตระกูล
ขั้นตอนวิธีการค้นหา
การค้นในต้นไม้ค้นหา