หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

Dijkstra สองทิศทาง

ปัญหา

ให้กราฟที่มีน้ำหนักขอบที่ไม่เป็นลบ, จุดสุด ยอด ของแหล่งที่มาและ idertec เป้าหมาย t ค้นหาเส้นทางที่สั้นที่สุดระหว่าง S และ T

แต่ทำไมเราไม่ใช้อัลกอริทึมของ Dijkstra เพื่อแก้ปัญหา?

0 (E + VLOGV) เป็นความซับซ้อนของเวลาที่เลวร้ายที่สุดของอัลกอริทึมของ Dijkstra ซึ่งค่อนข้างเร็ว แต่สำหรับกราฟที่มีจุดยอด 20 ล้านและขอบ 50 ล้านมันจะทำงานเป็นเวลาหลายวินาทีโดยเฉลี่ย ดังนั้นเราต้องการสิ่งที่เร็วขึ้นอย่างมาก

ก่อนที่เราจะเข้าไปดูรายละเอียดของการค้นหาแบบสองทิศทางให้เราสำรวจแนวคิดของ "หกองศาของการแยก"

  • ในปี 1929 นักเขียนชาวฮังการี Frigyes Karinthy เป็นครั้งแรกที่เสนอแนวคิดของ "หกองศาแยก" ในโซ่เรื่องสั้นของเขา
  • การแยกหกองศาเป็นความคิดที่ว่าทุกสิ่งมีชีวิตและทุกอย่างอื่นในโลกอยู่ห่างจากกันหกก้าวหรือน้อยลง

ตอนนี้มาดูเครือข่ายโซเชียลที่ได้รับความนิยมมากที่สุด Facebook สมมติว่าคนทั่วไปบน Facebook มีเพื่อนประมาณ 100 คน ถ้าเราพิจารณาเพื่อนของเพื่อนของบุคคลนั้นมันจะเป็น 100*100 นั่นคือเพื่อน 10,000 คนของเพื่อน หากเราพิจารณา "เพื่อนของเพื่อนเพื่อน" นั่นจะมากกว่า 100 เท่าหรือ 1 ล้าน และถ้าเราดำเนินการต่อไปอีกหกครั้งเราจะมี 1 ล้านล้านคน

แต่ประชากรโลกคือ 7.6 พันล้าน

ตอนนี้เราจะหาเส้นทางที่สั้นที่สุดระหว่างสองคนสุ่ม A และ B ผ่านการเชื่อมต่อบนเครือข่ายสังคมออนไลน์ได้อย่างไร

ให้พิจารณาการค้นหาแบบสองทิศทาง ดังนั้นเราจะพิจารณาเพื่อนของเพื่อนของเพื่อนและเพื่อนของเพื่อนของเพื่อนของ B. หากแนวคิดของการแยกหกองศาเป็นจริงจะมีคนทั่วไปในหมู่เพื่อนของเพื่อนของเพื่อนของ a และเพื่อนของเพื่อนของเพื่อนของ B. จากนั้นเราสามารถค้นหาเส้นทางที่สั้นที่สุดที่เชื่อมต่อ A และ B.

โปรดทราบว่าเราจะมีเพื่อนของเพื่อนประมาณ 1 ล้านคนสำหรับทั้ง A และ B ดังนั้นโดยรวมเราจะพิจารณาเพียง 2 ล้านคนในกรณีนี้

อัลกอริทึมของ Dijkstra ปกติจะต้องดูประมาณ 2 พันล้านคนบนเครือข่ายสังคมเพื่อค้นหาเส้นทางที่สั้นที่สุดระหว่าง A และ B

การค้นหาแบบสองทิศทางคืออะไร

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

Pseudocode สำหรับ dijkstra สองทิศทางบนกราฟ G

  • สร้าง GR (กราฟย้อนกลับ)
  • เริ่ม dijkstra จาก s (แหล่งที่มา) ใน g และจาก t (เป้าหมาย) ใน gr
  • สลับกันระหว่างขั้นตอน dijkstra ใน g และใน gr
  • หยุดเมื่อมีการประมวลผลจุดสุดยอด "V" ทั้งใน G และ GR
  • คำนวณเส้นทางที่สั้นที่สุดระหว่าง S และ T

การคำนวณเส้นทางที่สั้นที่สุดระหว่าง S และ T: ปล่อยให้ Dist [u] เป็นระยะทางไกลใน dijkstra ไปข้างหน้าจาก S ใน G. ให้ Distr [u] เป็นระยะทางที่ประมาณใน dijkstra ย้อนหลังจาก t ใน gr หลังจากบางโหนด "V" ถูกประมวลผลทั้งใน G และ GR เส้นทางที่สั้นที่สุดจาก S ถึง T ผ่านโหนด "U" บางเส้นทางซึ่งถูกประมวลผลใน G, ใน GR หรือทั้งสองและ D (S, T) = Dist [U] + Distr [U]

ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด