วิธีการ Traversal ของกราฟทำให้ฉันรู้สึกทึ่งมาก ตั้งแต่การสื่อสารแบบเพียร์ทูเพียร์ที่มีประสิทธิภาพไปจนถึงการค้นหาร้านอาหารและร้านกาแฟที่ใกล้ที่สุดโดยใช้ GPS วิธีการเดินทางผ่านมีชุดแอปพลิเคชันที่หลากหลายในสถานการณ์จริง ในบล็อกเรื่อง Breadth-First Search Algorithm นี้เราจะพูดถึงตรรกะที่อยู่เบื้องหลังวิธีการสำรวจกราฟและใช้ตัวอย่างเพื่อทำความเข้าใจการทำงานของอัลกอริทึมการค้นหาแบบกว้าง - แรก
หากต้องการรับความรู้เชิงลึกเกี่ยวกับปัญญาประดิษฐ์และการเรียนรู้ของเครื่องคุณสามารถลงทะเบียนเพื่อใช้งานจริงได้ โดย Edureka พร้อมการสนับสนุนตลอด 24 ชั่วโมงทุกวันและการเข้าถึงตลอดชีวิต
นี่คือรายการหัวข้อที่จะเป็น กล่าวถึงในบล็อกนี้:
- ข้อมูลเบื้องต้นเกี่ยวกับกราฟ Traversal
- Breadth-First Search คืออะไร?
- ทำความเข้าใจเกี่ยวกับอัลกอริทึมการค้นหาแบบกว้าง - แรกด้วยตัวอย่าง
- Pseudocode อัลกอริทึมการค้นหาแบบกว้าง - แรก
- การประยุกต์ใช้การค้นหาแบบกว้าง - แรก
ข้อมูลเบื้องต้นเกี่ยวกับกราฟ Traversal
กระบวนการเยี่ยมชมและสำรวจกราฟสำหรับการประมวลผลเรียกว่ากราฟการข้ามผ่าน เพื่อให้เฉพาะเจาะจงมากขึ้นทั้งหมดเกี่ยวกับการเยี่ยมชมและสำรวจจุดยอดและขอบแต่ละจุดในกราฟเพื่อให้มีการสำรวจจุดยอดทั้งหมดเพียงครั้งเดียว
ฟังดูเรียบง่าย! แต่มีสิ่งที่จับได้
มีเทคนิคการข้ามกราฟหลายอย่างเช่นการค้นหาแบบกว้าง - การค้นหาครั้งแรกการค้นหาครั้งแรกเชิงลึกและอื่น ๆ ความท้าทายคือการใช้กราฟ เทคนิคการข้ามผ่านที่เหมาะสมที่สุดสำหรับการแก้ปัญหาเฉพาะ สิ่งนี้นำเราไปสู่เทคนิคการค้นหาแบบกว้าง - แรก
ผลรวมของตัวเลขใน java
Breadth-First Search Algorithm คืออะไร?
อัลกอริทึมการค้นหาแบบกว้าง - แรกเป็นเทคนิคการสำรวจกราฟโดยที่คุณเลือกโหนดเริ่มต้นแบบสุ่ม (โหนดต้นทางหรือรูท) และเริ่มสำรวจเลเยอร์กราฟอย่างชาญฉลาดในลักษณะที่มีการเยี่ยมชมและสำรวจโหนดทั้งหมดและโหนดย่อยตามลำดับ
ก่อนที่เราจะก้าวต่อไปและทำความเข้าใจกับตัวอย่างของ Breadth-First Search เรามาทำความคุ้นเคยกับคำศัพท์สำคัญสองคำที่เกี่ยวข้องกับการข้ามผ่านกราฟ:
- การเยี่ยมชมโหนด: เช่นเดียวกับชื่อที่แนะนำการเยี่ยมชมโหนดหมายถึงการเยี่ยมชมหรือเลือกโหนด
- การสำรวจโหนด: สำรวจไฟล์ โหนดที่อยู่ติดกัน (โหนดลูก) ของโหนดที่เลือก
ดูรูปด้านบนเพื่อทำความเข้าใจสิ่งนี้ให้ดีขึ้น
ทำความเข้าใจเกี่ยวกับอัลกอริทึมการค้นหาแบบกว้างเป็นอันดับแรกด้วยตัวอย่าง
อัลกอริธึมการค้นหาแบบกว้าง - แรกเป็นไปตามแนวทางที่เรียบง่ายตามระดับเพื่อแก้ปัญหา พิจารณาต้นไม้ไบนารีด้านล่าง (ซึ่งเป็นกราฟ) เป้าหมายของเราคือการสำรวจกราฟโดยใช้อัลกอริทึมการค้นหาแบบกว้าง - แรก
ก่อนที่เราจะเริ่มต้นคุณต้องคุ้นเคยกับโครงสร้างข้อมูลหลักที่เกี่ยวข้องในอัลกอริทึมการค้นหาแบบกว้าง - แรก
คิวเป็นโครงสร้างข้อมูลนามธรรมที่เป็นไปตามระเบียบวิธีก่อนเข้า - ออกก่อน (ข้อมูลที่แทรกก่อนจะเข้าถึงก่อน) เปิดอยู่ที่ปลายทั้งสองด้านโดยที่ปลายด้านหนึ่งจะใช้เพื่อแทรกข้อมูล (จัดคิว) เสมอและอีกด้านหนึ่งจะใช้เพื่อลบข้อมูล (dequeue)
ตอนนี้เรามาดูขั้นตอนที่เกี่ยวข้องกับการสำรวจกราฟโดยใช้ Breadth-First Search:
ขั้นตอนที่ 1: ใช้คิวว่าง
ขั้นตอนที่ 2: เลือกโหนดเริ่มต้น (ไปที่โหนด) และแทรกลงในคิว
ขั้นตอนที่ 3: หากคิวไม่ว่างให้แยกโหนดออกจากคิวและแทรกโหนดลูก (สำรวจโหนด) ลงในคิว
ขั้นตอนที่ 4: พิมพ์โหนดที่แยกออกมา
ไม่ต้องกังวลหากคุณสับสนเราจะเข้าใจสิ่งนี้ด้วยตัวอย่าง
ดูกราฟด้านล่างเราจะใช้อัลกอริทึมการค้นหาแบบกว้าง - แรกเพื่อสำรวจผ่านกราฟ
ในกรณีของเราเราจะกำหนดโหนด 'a' เป็นโหนดรูทและเริ่มข้ามลงด้านล่างและทำตามขั้นตอนที่กล่าวไว้ข้างต้น
ภาพด้านบนแสดงให้เห็นกระบวนการ end-to-end ของ Breadth-First Search Algorithm ให้ฉันอธิบายสิ่งนี้ในเชิงลึกมากขึ้น
- กำหนด 'a' เป็นโหนดรากและแทรกลงในคิว
- แยกโหนด 'a' ออกจากคิวและแทรกโหนดลูกของ 'a' เช่น 'b' และ 'c'
- พิมพ์โหนด 'a'
- คิวไม่ว่างและมีโหนด 'b' และ 'c' เนื่องจาก 'b' เป็นโหนดแรกในคิวให้แตกออกและแทรกโหนดลูกของ 'b' นั่นคือโหนด 'd' และ 'e'
- ทำซ้ำขั้นตอนเหล่านี้จนกว่าคิวจะว่างเปล่า โปรดทราบว่าไม่ควรเพิ่มโหนดที่เข้าชมแล้วลงในคิว อีกครั้ง.
ตอนนี้เรามาดูรหัสเทียมของอัลกอริทึมการค้นหาแบบกว้าง - แรกกัน
Pseudocode อัลกอริทึมการค้นหาแบบกว้าง - แรก
นี่คือรหัสเทียมสำหรับใช้อัลกอริทึมการค้นหาแบบกว้าง - แรก:
อินพุต: เป็นโหนดต้นทาง BFS (G, s) ให้ Q เป็นคิว Q.enqueue (s) ทำเครื่องหมาย s ว่าเยี่ยมแล้วในขณะที่ (Q ไม่ว่างเปล่า) v = Q.dequeue () สำหรับเพื่อนบ้านทั้งหมด w ของ v ในกราฟ G ถ้า w ไม่ได้เยี่ยมชม Q.enqueue (w) ทำเครื่องหมาย w as เยี่ยม
ในโค้ดด้านบนขั้นตอนต่อไปนี้จะดำเนินการ:
- (G, s) คืออินพุตที่นี่ G คือกราฟและ s คือโหนดรูท
- คิว 'Q' ถูกสร้างและเริ่มต้นด้วยโหนดต้นทาง 's'
- มีการทำเครื่องหมายโหนดลูกทั้งหมดของ 's'
- แยก 's' ออกจากคิวและไปที่โหนดย่อย
- ประมวลผลโหนดลูกทั้งหมดของ v
- เก็บ w (โหนดลูก) ใน Q เพื่อเยี่ยมชมโหนดลูกเพิ่มเติม
- ดำเนินการต่อจนกว่า 'Q' จะเป็น ว่างเปล่า
ก่อนที่เราจะสรุปบล็อกเรามาดูแอปพลิเคชันบางส่วนของอัลกอริทึมการค้นหาแบบกว้าง - แรก
การประยุกต์ใช้อัลกอริทึมการค้นหาแบบกว้าง - แรก
การค้นหาแบบกว้างเป็นอันดับแรกเป็นวิธีการส่งผ่านกราฟอย่างง่ายที่มีแอปพลิเคชันที่หลากหลาย ต่อไปนี้เป็นวิธีที่น่าสนใจบางประการในการใช้ Bread-First Search:
โปรแกรมรวบรวมข้อมูลในเครื่องมือค้นหา: Breadth-First Search เป็นหนึ่งในอัลกอริทึมหลักที่ใช้ในการสร้างดัชนีหน้าเว็บ อัลกอริทึมเริ่มการสำรวจจากเพจต้นทางและตามลิงค์ทั้งหมดที่เกี่ยวข้องกับเพจ แต่ละหน้าเว็บจะถือเป็นโหนดในกราฟ
ระบบนำทาง GPS: Breadth-First Search เป็นหนึ่งในอัลกอริทึมที่ดีที่สุดที่ใช้ในการค้นหาตำแหน่งใกล้เคียงโดยใช้ระบบ GPS
ค้นหาเส้นทางที่สั้นที่สุดและโครงสร้างช่วงขั้นต่ำสำหรับกราฟที่ไม่ถ่วงน้ำหนัก: เมื่อพูดถึงกราฟแบบไม่ถ่วงน้ำหนักการคำนวณเส้นทางที่สั้นที่สุดนั้นค่อนข้างง่ายเนื่องจากแนวคิดเบื้องหลังเส้นทางที่สั้นที่สุดคือการเลือกเส้นทางที่มีขอบน้อยที่สุด Breadth-First Search สามารถอนุญาตได้โดยการข้ามผ่านจำนวนโหนดขั้นต่ำโดยเริ่มจากโหนดต้นทาง ในทำนองเดียวกันสำหรับต้นไม้ที่ทอดยาวเราสามารถใช้วิธีใดวิธีหนึ่งในสองวิธีการค้นหาแบบกว้าง - แรกหรือวิธีการสำรวจความลึกก่อนเพื่อค้นหาต้นไม้ที่ทอด
การแพร่ภาพ: ระบบเครือข่ายใช้ประโยชน์จากสิ่งที่เราเรียกว่าแพ็กเก็ตเพื่อการสื่อสาร แพ็กเก็ตเหล่านี้ทำตามวิธีการส่งผ่านเพื่อเข้าถึงโหนดเครือข่ายต่างๆ หนึ่งในวิธีการข้ามผ่านที่ใช้บ่อยที่สุดคือการค้นหาแบบกว้าง - แรก กำลังใช้เป็นอัลกอริทึมที่ใช้ในการสื่อสารแพ็กเก็ตที่ออกอากาศผ่านโหนดทั้งหมดในเครือข่าย
Peer to Peer Networking: Breadth-First Search สามารถใช้เป็นวิธีการสำรวจเพื่อค้นหาโหนดใกล้เคียงทั้งหมดในเครือข่าย Peer to Peer ตัวอย่างเช่น BitTorrent ใช้ Breadth-First Search สำหรับการสื่อสารแบบเพียร์ทูเพียร์
นั่นคือทั้งหมดที่เกี่ยวกับการทำงานของอัลกอริทึมการค้นหาแบบกว้าง - แรก ตอนนี้คุณรู้วิธีสำรวจกราฟแล้วฉันแน่ใจว่าคุณอยากเรียนรู้เพิ่มเติม นี่คือบล็อกที่เกี่ยวข้องบางส่วนเพื่อให้คุณสนใจ:
ด้วยเหตุนี้เราจึงมาถึงจุดสิ้นสุดของบล็อกนี้ หากคุณมีข้อสงสัยเกี่ยวกับหัวข้อนี้โปรดแสดงความคิดเห็นไว้ด้านล่างแล้วเราจะติดต่อกลับไป
หากคุณต้องการลงทะเบียนสำหรับหลักสูตรที่สมบูรณ์เกี่ยวกับปัญญาประดิษฐ์และการเรียนรู้ของเครื่อง Edureka มีการดูแลเป็นพิเศษ ที่จะทำให้คุณมีความเชี่ยวชาญในเทคนิคต่างๆเช่นการเรียนรู้ภายใต้การดูแลการเรียนรู้โดยไม่ได้รับการดูแลและการประมวลผลภาษาธรรมชาติ รวมถึงการฝึกอบรมเกี่ยวกับความก้าวหน้าล่าสุดและแนวทางทางเทคนิคในปัญญาประดิษฐ์และการเรียนรู้ของเครื่องเช่นการเรียนรู้เชิงลึกแบบจำลองกราฟิกและการเรียนรู้แบบเสริมกำลัง