ผู้ใช้:Ready1412/ทดลองเขียน
การค้นตามแนวกว้าง (อังกฤษ: Breadth-first search : BFS) หมายถึงอัลกอริทึมในการค้นหาในกราฟ โดยเริ่มต้นที่ปมที่กำหนดไปยังปมอื่นๆ เกิดเป็นต้นไม้แผ่ขยาย (Spanning Tree) ของปมเชื่อมถึงกัน (Connected Component)
เนื่องจากมีลักษณะของการแวะผ่านปมไปทีละระดับ จึงเรียกอีกอย่างว่า การค้นทีละระดับ (Level-order search)
ลักษณะโดยทั่วไป
[แก้]การค้นตามแนวกว้าง มีลักษณะการค้นลงไปทีละระดับ โดยการตรวจสอบระดับลูกทั้งหมดก่อน จึงลงไประดับถัดไป
เนื่องจากการค้นแบบนี้เป็นการค้นที่มีระบบ กล่าวคือไม่มีการตัดสินใจเลือกเส้นทางระหว่างการค้น แต่จะทำการค้นไปเรื่อยๆ ตามรูปแบบจนเจอคำตอบ จึงจัดอยู่ในกลุ่มของการค้นแบบ Blind Search
ขั้นตอนวิธี
[แก้]- เพิ่มปมเริ่มต้นลงในแถวคอย
- นำปมออกจากแถวคอย ทำสัญลักษณ์แสดงการแวะผ่านแล้ว จากนั้นตรวจสอบดังนี้
- ถ้าเป็นปมที่สนใจหรือคำตอบ ให้ยุติการค้นหาและส่งคืนค่าผลลัพธ์
- ทำการเพิ่มปมลูกที่ยังไม่เคยแวะผ่านทุกปมลงในแถวคอย
- หากแถวคอยว่าง แสดงว่าจบการค้นหา
- หากแถวคอยไม่ว่าง ให้กลับไปขั้นตอนที่ 2
รหัสเทียม
[แก้] 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;
}
}
}
}
คุณสมบัติ
[แก้]ความซับซ้อนด้านพื้นที่
[แก้]- เมื่อกำหนดให้หนึ่งปมมีปมลูก b และกราฟมีความสูง h จะพบว่าในแต่ละระดับจะมีจำนวนปมทั้งสิ้น bh
- ดังนั้นสามารถวิเคราะห์ความซับซ้อนของพื้นที่ได้เป็น O(bh)
- นอกจากนี้ยังสามารถแทนความซับซ็อนของพื้นที่ในรูปของจำนวนปมคือ O(|V|) เมื่อ V แทนเซ็ตของปมในกราฟ
ความซับซ้อนด้านเวลา
[แก้]- พิจารณาลำดับการผ่านปมของการค้นตามแนวกว้างจะพบว่าในแต่ละครั้งของการค้นหา จะผ่านปมหนึ่งๆเพียงหนึ่งครั้งเท่านั้น ดังนั้นจึงใช้เวลาไม่เกิน O(|V|)
- ในขณะเดียวกัน การผ่านเส้นเชื่อมในแต่ละครั้งของการค้นจะผ่านเพียงเส้นละหนึ่งครั้งเช่นกัน ดังนั้นจึงใช้เวลาไม่เกิน O(|E|)
- ดังนั้นในกรณีเลวร้ายที่สุดของการค้นตามแนวกว้างที่ต้องผ่านทุกปมและทุกเส้นเชื่อม จะสามารถวิเคราะห์เวลาของการทำงานได้เป็น O(|V| + |E|)
ความสมบูรณ์
[แก้]- หากมีคำตอบหรือปมที่สนใจอยู่ในกราฟ ไม่ว่ากราฟนั้นจะเป็นกราฟอนันต์หรือไม่ การค้นตามแนวกว้างจะสามารถการันตีได้ว่าจะต้องเจอคำตอบเสมอ
การได้คำตอบเหมาะสมที่สุด
[แก้]- คำตอบแรกที่ได้จากการค้นหาตวามแนวกว้าง จะมีระยะห่างจากปมเริ่มต้นเป็นระยะทางสั้นที่สุดเสมอ (เมื่อวัดจากจำนวนเส้นเชื่อม)
- แต่ในกรณีที่เป็นกราฟมีน้ำหนัก (Weighted Graph) คำตอบที่ได้อาจไม่ใช่ระยะทางสั้นสุด ซึ่งสามารถแก้ไขได้โดยการใช้ uniform-cost search
การประยุกต์ใช้งาน
[แก้]การค้นตามแนวกว้างสามารถใช้ในการแก้ปัญหาต่างๆของทฤษฏีกราฟได้เช่น
- การหาปมภายในส่วนประกอบที่เชื่อมกัน (อังกฤษ: Connected Component)
- หาระยะทางสั้นสุดระหว่างสองปม เช่นอัลกอริทึมของพริม (Prim's Algorithm) และอัลกอริทึมของดิสตราส์ (Dijkstra's Algorithm)
- ตรวจสอบความเป็นกราฟสองส่วน (Bipartiteness)
- ใช้ในอัลกอริทึมของเชนีย์ (อังกฤษ: Cheney's algorithm)
- ใช้ในวิธีการของฟอร์ด-ฟูลเกอร์สัน (Ford–Fulkerson method) ในการคำนวณการไหลสูงสุด (Maximum Flow) ในเครือข่ายการไหล (Flow Network)
อ้างอิง
[แก้]
วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับ Breadth-first search