การค้นตามแนวกว้าง

ภาพแสดงลำดับการค้นของการค้นตามแนวกว้าง

การค้นตามแนวกว้าง (อังกฤษ: Breadth-first search : BFS) หมายถึงอัลกอริทึมในการค้นหาในกราฟ โดยเริ่มต้นที่ปมที่กำหนดไปยังปมอื่นๆ เกิดเป็นต้นไม้แผ่ขยาย (Spanning Tree) ของปมเชื่อมถึงกัน (Connected Component)

การค้นในลักษณะนี้ถูกใช้เป็นแนวคิดพื้นฐานในการแก้ปัญหาทฤษฏีกราฟรวมถึงการค้นในปริภูมิสถานะ (อังกฤษ: State Space Search)

เนื่องจากมีลักษณะของการแวะผ่านปมไปทีละระดับ จึงเรียกอีกอย่างว่า การค้นทีละระดับ (Level-order search)

[แก้] ลักษณะโดยทั่วไป

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

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

ภาพแสดงลำดับการค้นของการค้นตามแนวกว้าง

[แก้] ขั้นตอนวิธี

เพิ่มปมเริ่มต้นลงในแถวคอย
นำปมออกจากแถวคอย ทำสัญลักษณ์แสดงการแวะผ่านแล้ว จากนั้นตรวจสอบดังนี้
- ถ้าเป็นปมที่สนใจหรือคำตอบ ให้ยุติการค้นหาและส่งคืนค่าผลลัพธ์
- ทำการเพิ่มปมลูกที่ยังไม่เคยแวะผ่านทุกปมลงในแถวคอย
หากแถวคอยว่าง แสดงว่าจบการค้นหา
หากแถวคอยไม่ว่าง ให้กลับไปขั้นตอนที่ 2

[แก้] รหัสเทียม

ภาพแสดงการเปลี่ยนสถานะของปมตามรหัสเทียม

เมื่อกำหนดสถานะของปมดังนี้

WHITE ปมยังไม่เคยถูกค้น
GRAY ปมอยู่ในแถวคอย
BLACK ปมถูกค้นเรียบร้อยแล้ว

       BFS(G(V,E), s) {
           for each v in V {
               color[v] <- WHITE;
           }

           Q = an empty queue;
           Q.enqueue(s);

           color[s] <- GRAY

           while (Q is not an empty queue) {
               u <- Q.dequeue();
               color[u] <- BLACK;

               for(each v that adjacent with u) {
                   if(color[v]=WHITE) {
                       Q.enqueue(v);
                       color[v] = GRAY;
                   }
               }
           }
       }

[แก้] ตัวอย่าง

ภาพตัวอย่างแสดงการเชื่อมโยงของเมืองในประเทศโรมาเนีย

เมื่อใช้การค้นตามแนวกว้างกับกราฟนี้ จะได้ลำดับการค้นดังนี้

       Arad > Timisora > Zerind > Sibiu > Craivora > Oradea > Rimnicu > Fagaras > Pitesti > Bucharest

[แก้] คุณสมบัติ

[แก้] ความซับซ้อนด้านพื้นที่

เมื่อกำหนดให้หนึ่งปมมีปมลูก b และกราฟมีความสูง h จะพบว่าในแต่ละระดับจะมีจำนวนปมทั้งสิ้น bh

ดังนั้นสามารถวิเคราะห์ความซับซ้อนของพื้นที่ได้เป็น O(bh)

นอกจากนี้ยังสามารถแทนความซับซ็อนของพื้นที่ในรูปของจำนวนปมคือ O(|V|) เมื่อ V แทนเซ็ตของปมในกราฟ

[แก้] ความซับซ้อนด้านเวลา

พิจารณาลำดับการผ่านปมของการค้นตามแนวกว้างจะพบว่าในแต่ละครั้งของการค้นหา จะผ่านปมหนึ่งๆเพียงหนึ่งครั้งเท่านั้น ดังนั้นจึงใช้เวลาไม่เกิน O(|V|)

ในขณะเดียวกัน การผ่านเส้นเชื่อมในแต่ละครั้งของการค้นจะผ่านเพียงเส้นละหนึ่งครั้งเช่นกัน ดังนั้นจึงใช้เวลาไม่เกิน O(|E|)

ดังนั้นในกรณีเลวร้ายที่สุดของการค้นตามแนวกว้างที่ต้องผ่านทุกปมและทุกเส้นเชื่อม จะสามารถวิเคราะห์เวลาของการทำงานได้เป็น O(|V| + |E|)

[แก้] ความสมบูรณ์

หากมีคำตอบหรือปมที่สนใจอยู่ในกราฟ ไม่ว่ากราฟนั้นจะเป็นกราฟอนันต์หรือไม่ การค้นตามแนวกว้างจะสามารถการันตีได้ว่าจะต้องเจอคำตอบเสมอ

[แก้] การได้คำตอบเหมาะสมที่สุด

คำตอบแรกที่ได้จากการค้นหาตวามแนวกว้าง จะมีระยะห่างจากปมเริ่มต้นเป็นระยะทางสั้นที่สุดเสมอ (เมื่อวัดจากจำนวนเส้นเชื่อม)

แต่ในกรณีที่เป็นกราฟมีน้ำหนัก (Weighted Graph) คำตอบที่ได้อาจไม่ใช่ระยะทางสั้นสุด ซึ่งสามารถแก้ไขได้โดยการใช้ uniform-cost search

[แก้] การประยุกต์ใช้งาน

การค้นตามแนวกว้างสามารถใช้ในการแก้ปัญหาต่างๆของทฤษฏีกราฟได้เช่น

การหาปมภายในส่วนประกอบที่เชื่อมกัน (อังกฤษ: Connected Component)
หาวงจรอย่างง่าย (อังกฤษ: Simple Cycle) ในกราฟ
หาป่าไม้แผ่ขยาย (อังกฤษ: Spanning Forest) ในกราฟ
หาระยะทางสั้นสุดระหว่างสองปม เช่นอัลกอริทึมของพริม (Prim's Algorithm) และอัลกอริทึมของดิสตราส์ (Dijkstra's Algorithm)
ตรวจสอบความเป็นกราฟสองส่วน (Bipartiteness)
ใช้ในอัลกอริทึมของเชนีย์ (อังกฤษ: Cheney's algorithm)
ใช้ในวิธีการของฟอร์ด-ฟูลเกอร์สัน (Ford–Fulkerson method) ในการคำนวณการไหลสูงสุด (Maximum Flow) ในเครือข่ายการไหล (Flow Network)

[แก้] สรุป

การค้นตามแนวกว้างสามารถใช้การปัญหาการค้นในกราฟได้โดยสามารถการันตีได้ว่าจะพบผลลัพธ์แน่นอน แตกต่างจากการค้นตามแนวลึก ซึ่งอาจไม่พบคำตอบหากกราฟที่ค้นเป็นกราฟอนันต์

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

[แก้] ดูเพิ่มเติม

[แก้] อ้างอิง

คอมมอนส์ มีภาพและสื่ออื่น ๆ เกี่ยวกับ:
การค้นตามแนวกว้าง

[แก้] แหล่งข้อมูลอื่น

การค้นตามแนวกว้าง

เนื้อหา

[แก้] ลักษณะโดยทั่วไป

[แก้] ขั้นตอนวิธี

[แก้] รหัสเทียม

[แก้] ตัวอย่าง

[แก้] คุณสมบัติ

[แก้] ความซับซ้อนด้านพื้นที่

[แก้] ความซับซ้อนด้านเวลา

[แก้] ความสมบูรณ์

[แก้] การได้คำตอบเหมาะสมที่สุด

[แก้] การประยุกต์ใช้งาน

[แก้] สรุป

[แก้] ดูเพิ่มเติม

[แก้] อ้างอิง

[แก้] แหล่งข้อมูลอื่น

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

การกระทำ

สืบค้น

ป้ายบอกทาง

มีส่วนร่วม

พิมพ์/ส่งออก

เครื่องมือ

ภาษาอื่น