BFS — อธิบายอัลกอริทึม Breadth-First Search

Breadth-first search หรือ BFS คืออัลกอริทึมบนกราฟที่เยี่ยมชมโหนดตามลำดับระยะห่างจากโหนดเริ่มต้น มันจะตรวจทุกโหนดที่อยู่ห่างออกไป 1 ขอบก่อน แล้วจึงไปยังโหนดที่ห่าง 2 ขอบ จากนั้น 3 ขอบ และต่อไปเรื่อย ๆ

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

Breadth-First Search ทำอะไร

BFS ใช้ คิว (queue) ซึ่งเป็นรายการแบบเข้าก่อนออกก่อน คิวคือสิ่งที่รักษาลำดับเป็นชั้นไว้: โหนดที่ถูกค้นพบก่อนจะถูกประมวลผลก่อน

รูปแบบที่ใช้กันทั่วไปคือ:

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

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

ทำไมคิวจึงสร้างชั้นได้

สมมติว่าโหนด $A$ เป็นจุดเริ่มต้น เพื่อนบ้านโดยตรงของมันอยู่ห่างจาก $A$ เป็นระยะ $1$ ดังนั้นจึงเข้าคิวก่อน หลังจากประมวลผลโหนดเหล่านั้นแล้วเท่านั้น เพื่อนบ้านที่ยังไม่ถูกเยี่ยมชมของพวกมันจึงจะเข้าคิว ซึ่งหมายความว่าคลื่นถัดไปมีระยะ $2$

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

ตัวอย่าง BFS: หาเส้นทางสั้นที่สุดตามจำนวนขอบ

ใช้กราฟนี้:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

เริ่มที่ $A$ คิวจะเปลี่ยนดังนี้:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

ความหมายคือ:

ขั้นแรก ประมวลผล $A$ แล้วเพิ่ม $B$ และ $C$ จากนั้นประมวลผล $B$ แล้วค่อย $C$ ซึ่งทำให้เพิ่ม $D$ และ $E$ หลังจากนั้นประมวลผล $D$ และ $E$ ซึ่งไปถึง $F$

ดังนั้นลำดับการเยี่ยมชมของ BFS คือ:

$$A,\ B,\ C,\ D,\ E,\ F$$

ระยะจาก $A$ คือ:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

สิ่งนี้แสดงให้เห็นประโยชน์หลัก BFS ไปถึง $F$ ที่ระยะ $3$ ดังนั้นเส้นทางสั้นที่สุดจาก $A$ ไป $F$ ใช้ $3$ ขอบ เส้นทางสั้นที่สุดเส้นทางหนึ่งคือ $A \to B \to D \to F$ อีกเส้นทางหนึ่งคือ $A \to C \to E \to F$

ข้อผิดพลาดที่พบบ่อยใน BFS

คิดว่า BFS หาเส้นทางที่ถูกที่สุดได้เสมอ

สิ่งนี้เป็นจริงก็ต่อเมื่อทุกขอบมีต้นทุนเท่ากัน หรือเมื่อมองกราฟเป็นกราฟไม่มีน้ำหนักเท่านั้น หากขอบมีน้ำหนักต่างกัน BFS อาจหาเส้นทางที่มีจำนวนขอบน้อยกว่า แต่มีต้นทุนรวมสูงกว่าได้

ทำเครื่องหมายโหนดช้าเกินไป

ใน BFS มาตรฐาน มักจะทำเครื่องหมายว่าโหนดถูกเยี่ยมชมแล้วตอนที่มันถูก นำเข้าคิว ไม่ใช่ตอนที่ถูกนำออกในภายหลัง วิธีนี้ช่วยป้องกันไม่ให้โหนดเดียวกันถูกเพิ่มเข้าคิวหลายครั้ง

สับสนระหว่าง BFS กับ DFS

BFS สำรวจเป็นชั้น ๆ ส่วน depth-first search หรือ DFS จะตามไปตามกิ่งหนึ่งให้ลึกก่อนแล้วค่อยย้อนกลับ ทั้งสองแบบเหมาะกับการตอบคำถามคนละประเภท

ลืมว่าลำดับอาจขึ้นอยู่กับลำดับของเพื่อนบ้าน

ลำดับการเยี่ยมชมที่แน่นอนภายในชั้นเดียวกันอาจเปลี่ยนไปตามวิธีการเรียงรายชื่อเพื่อนบ้าน การรับประกันเรื่องระยะทางยังคงเหมือนเดิม แต่ลำดับการท่องกราฟอาจต่างกันได้

Breadth-First Search ใช้เมื่อใด

BFS มีประโยชน์เมื่อคุณสนใจเรื่องการเข้าถึงได้ การท่องต้นไม้แบบตามระดับ หรือความยาวของเส้นทางสั้นที่สุดที่วัดด้วยจำนวนขอบ

มันยังปรากฏในปัญหา state-space ที่ทุกการเคลื่อนที่มีต้นทุนเท่ากัน ภายใต้เงื่อนไขนั้น BFS มักเป็นวิธีที่ชัดเจนที่สุดในการหาจำนวนการเคลื่อนที่น้อยที่สุด

วิธีง่าย ๆ ในการจำ BFS

ให้นึกถึง BFS เหมือนระลอกคลื่นที่แผ่ออกจากโหนดเริ่มต้น ทุกครั้งที่คลื่นขยายออกไป ระยะทางจะเพิ่มขึ้นอีก 1 ขอบ

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