การค้นหาในแนวกว้าง

ในทฤษฎีกราฟ การค้นหาตามแนวกว้าง () คือขั้นตอนวิธีในการท่องกราฟอย่างหนึ่ง โดยในขณะที่กำลังท่องกราฟมายังจุดยอดหนึ่ง ๆ นั้น จะมีการกระทำสองอย่างคือ: (ก) เข้าเยี่ยมและตรวจสอบจุดยอดดังกล่าว (ข) เข้าถึงจุดยอดข้างเคียงของจุดยอดดังกลาว การท่องกราฟจะเริ่มต้นที่จุดยอดรากที่กำหนดและไปยังจุดยอดอื่น ๆ จนเกิดเป็นต้นไม้แบบทอดข้าม การท่องกราฟอีกรูปแบบที่คล้ายคลึงกันคือการค้นหาในแนวลึก

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

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

ลักษณะโดยทั่วไป 

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

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

ขั้นตอนวิธี 

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

codes 

 เมื่อกำหนดสถานะของปมดังนี้
 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) คำตอบที่ได้อาจไม่ใช่ระยะทางสั้นสุด ซึ่งสามารถแก้ไขได้โดยการใช้การค้นหาตามค่าทุนอย่างมีเอกรูป

การประยุกต์ใช้งาน 
การค้นตามแนวกว้างสามารถใช้ในการแก้ปัญหาต่างๆของทฤษฏีกราฟได้เช่น
 การหาจุดยอดภายในส่วนประกอบที่เชื่อมกัน
 หาวงจรอย่างง่าย ในกราฟ
 หาป่าไม้แผ่ขยาย ในกราฟ
 หาระยะทางสั้นสุดระหว่างสองปม เช่นขั้นตอนวิธีของพริมและขั้นตอนวิธีของไดค์สตรา
 ตรวจสอบความเป็นกราฟสองส่วน (Bipartiteness)
 ใช้ในขั้นตอนวิธีของเชนีย์
 ใช้ในขั้นตอนวิธีของฟอร์ด-เฟอลเกอสัน (Ford–Fulkerson method) ในการคำนวณการไหลสูงสุด (Maximum Flow) ในเครือข่ายการไหล (Flow Network)

อ้างอิง 

 
 
 http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm
 http://intelligence.worldofcomputing.net/ai-search/breadth-first-search.html

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

 Breadth-First Search in JAVA
 JAWAA Animation: Breadth-First Search
 http://www.cp.eng.chula.ac.th/~somchai/ULearn/Algorithms/index.htm
 http://ww3.algorithmdesign.net/handouts/BFS.pdf
 Edmonds’s Non-Bipartite Matching Algorithm

ขั้นตอนวิธีการค้นหา