ขั้นตอนวิธีเบลล์แมน-ฟอร์ด
- ผู้เสนอ
- Richard Bellman and Lester R. Ford
- ปี
- 1956
- ประเภท
- algorithm
- กลุ่มวิธี
- Graph Algorithms
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ขั้นตอนวิธีเบลล์แมน-ฟอร์ด (Bellman-Ford Algorithm) ซึ่งพัฒนาโดย Richard Bellman และ Lester R. Ford ในทศวรรษ 1950 เป็นขั้นตอนวิธีพื้นฐานสำหรับการคำนวณเส้นทางที่สั้นที่สุดในกราฟถ่วงน้ำหนักที่อาจมีน้ำหนักขอบเป็นลบ ต่างจากขั้นตอนวิธีของ Dijkstra ตรงที่สามารถจัดการกับน้ำหนักที่เป็นลบได้อย่างถูกต้อง และสามารถตรวจจับการมีอยู่ของวงจรน้ำหนักลบได้
แนวคิดเบื้องหลังวิธีการ
ขั้นตอนวิธีนี้ทำงานโดยการผ่อนคลายขอบซ้ำ ๆ: สำหรับแต่ละขอบ จะตรวจสอบว่าการผ่านขอบนั้นให้เส้นทางที่สั้นกว่าไปยังปลายทางหรือไม่ เมื่อเทียบกับเส้นทางที่ดีที่สุดที่ทราบในปัจจุบัน ด้วยการทำซ้ำกระบวนการนี้สำหรับขอบทั้งหมด V-1 ครั้ง โดยที่ V คือจำนวนจุดยอด ขั้นตอนวิธีนี้รับประกันว่าจะพบเส้นทางที่สั้นที่สุดแม้จะมีน้ำหนักที่เป็นลบ แนวคิดหลักคือเส้นทางที่สั้นที่สุดในกราฟที่มี V จุดยอด จะมีขอบไม่เกิน V-1 ขอบ หากระยะทางยังคงดีขึ้นหลังจากการวนซ้ำ V-1 ครั้ง จะต้องมีวงจรลบอยู่
ประวัติศาสตร์
Richard Bellman พัฒนาขั้นตอนวิธีนี้ในปี 1958 โดยใช้หลักการเขียนโปรแกรมเชิงพลวัต (dynamic programming) ในขณะที่ Lester R. Ford ค้นพบแนวทางที่คล้ายกันสำหรับกระแสในเครือข่าย (network flows) โดยอิสระในปี 1956 ขั้นตอนวิธีนี้ได้รับการพัฒนาและปรับปรุงเพิ่มเติมในทศวรรษ 1960 โดยมีการประยุกต์ใช้กับการกำหนดเส้นทางเครือข่าย (network routing) และแอปพลิเคชันทางเศรษฐกิจ ตัวแปรสมัยใหม่รวมถึงขั้นตอนวิธีเส้นทางที่สั้นที่สุดที่เร็วขึ้น (Shortest Path Faster Algorithm - SPFA) และการปรับปรุงประสิทธิภาพต่าง ๆ สำหรับโครงสร้างกราฟเฉพาะ แม้ว่าแนวทางพื้นฐานของ Bellman-Ford ยังคงเป็นข้อมูลอ้างอิงคลาสสิกในการออกแบบขั้นตอนวิธี
ควรใช้เมื่อใด
ใช้ขั้นตอนวิธีเบลล์แมน-ฟอร์ดเมื่อคำนวณเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักขอบเป็นลบ มีความสำคัญสำหรับการตรวจจับการเก็งกำไรค่าเงิน (currency arbitrage detection) โปรโตคอลเครือข่ายที่น้ำหนักอาจเป็นลบ และแอปพลิเคชันใด ๆ ที่ต้นทุนหรือน้ำหนักที่เป็นลบมีความหมาย ใช้ขั้นตอนวิธีของ Dijkstra หากน้ำหนักทั้งหมดไม่เป็นลบ เนื่องจากมีประสิทธิภาพมากกว่า สำหรับการตรวจจับวงจรลบโดยไม่ต้องคำนวณเส้นทาง ขั้นตอนวิธีนี้ก็เหมาะสมเช่นกัน
ข้อจำกัดและข้อควรพิจารณา
- ช้ากว่า Dijkstra สำหรับน้ำหนักที่ไม่เป็นลบ: O(VE) เทียบกับ O((V+E)logV)
- มีประสิทธิภาพน้อยกว่าสำหรับกราฟแบบเบาบาง (sparse graphs) เมื่อเทียบกับขั้นตอนวิธีอื่น ๆ
- ต้องระบุขอบทั้งหมดอย่างชัดเจน ทำให้ไม่เหมาะสำหรับกราฟแบบปริยาย (implicit) หรือแบบพลวัต (dynamic)
- ไม่มีคำแนะนำเชิงฮิวริสติก (heuristic guidance) ที่จะช่วยเร่งการคำนวณ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จัดการกับกราฟที่มีน้ำหนักขอบเป็นลบได้อย่างถูกต้อง
- ตรวจจับวงจรน้ำหนักลบ ป้องกันผลลัพธ์เส้นทางที่สั้นที่สุดที่ผิดพลาด
- เข้าใจและนำไปใช้งานได้ง่ายกว่าขั้นตอนวิธีเส้นทางที่สั้นที่สุดขั้นสูงบางตัว
- รับประกันว่าจะพบเส้นทางที่สั้นที่สุดในเวลา O(VE)
- ทำงานได้ทั้งบนกราฟมีทิศทางและไม่มีทิศทาง (โดยต้องระมัดระวังในกราฟไม่มีทิศทาง)
การประยุกต์ใช้
- การตรวจจับการเก็งกำไรค่าเงิน: การระบุวงจรที่ทำกำไรได้ในกราฟอัตราแลกเปลี่ยน
- โปรโตคอลการกำหนดเส้นทางเครือข่าย: การคำนวณเส้นทางที่สั้นที่สุดที่ต้นทุนลิงก์สามารถเปลี่ยนแปลงหรือเป็นลบได้
- ทฤษฎีเกม: การแก้ปัญหาเส้นทางที่สั้นที่สุดด้วยขอบค่าปรับหรือปัจจัยส่วนลด
- วิทยาการหุ่นยนต์: การวางแผนเส้นทางในสภาพแวดล้อมที่มีแรงผลัก (น้ำหนักลบ)
- การจัดสรรพลังงานทางเศรษฐกิจ: การเพิ่มประสิทธิภาพการผลิตพลังงานด้วยฟังก์ชันต้นทุนรวมถึงพจน์ลบ
- โทรคมนาคม: การค้นหาเส้นทางที่เหมาะสมที่สุดเมื่อน้ำหนักลิงก์แสดงถึงความล่าช้าหรือเมตริกคุณภาพ
วิธีการทำงาน
วิธีการทำงาน
กำหนดระยะทางไปยังแหล่งกำเนิดเป็นศูนย์ และระยะทางอื่น ๆ ทั้งหมดเป็นอนันต์ อาจกำหนดตัวก่อนหน้าทั้งหมดเป็น null
ทำซ้ำ V-1 ครั้ง: สำหรับแต่ละขอบ (u, v) ที่มีน้ำหนัก w หาก distance[u] + w น้อยกว่า distance[v] ให้อัปเดต distance[v] และตัวก่อนหน้าของ v
ตรวจสอบขอบทั้งหมดอีกครั้ง; หากระยะทางใด ๆ ดีขึ้น แสดงว่ามีวงจรน้ำหนักลบอยู่ ส่งคืนข้อผิดพลาดหรือระบุวงจรตามความเหมาะสม
ข้อผิดพลาดที่พบบ่อย
- ลืมทำการวนซ้ำเพิ่มเติมเพื่อตรวจจับวงจรลบ
- สมมติว่าขั้นตอนวิธีทำงานได้อย่างถูกต้องในกราฟไม่มีทิศทางที่มีขอบเป็นลบ (อาจสร้างวงจรลบเสมือนได้)
- ใช้ขั้นตอนวิธีนี้เมื่อ Dijkstra เพียงพอแล้ว ส่งผลให้ประสิทธิภาพลดลงโดยไม่จำเป็น
คำถามที่พบบ่อย
เหตุใดขั้นตอนวิธีจึงต้องมีการวนซ้ำ V-1 ครั้งพอดี?
เส้นทางใด ๆ ในกราฟที่มี V จุดยอดจะมีขอบไม่เกิน V-1 ขอบ ด้วยการวนซ้ำ V-1 ครั้ง ขั้นตอนวิธีจะช่วยให้ข้อมูลระยะทางแพร่กระจายไปทั่วทั้งกราฟ การวนซ้ำครั้งที่ V จะช่วยปรับปรุงระยะทางก็ต่อเมื่อมีวงจรลบอยู่เท่านั้น
ขั้นตอนวิธีสามารถตรวจจับวงจรลบได้อย่างไร?
หลังจากเสร็จสิ้นการวนซ้ำ V-1 ครั้ง ให้ทำการผ่อนคลายอีกครั้ง หากระยะทางใด ๆ ลดลง แสดงว่ามีวงจรลบอยู่ โหนดที่เกี่ยวข้องในวงจรสามารถระบุได้โดยการย้อนรอยโดยใช้ตัวชี้ตัวก่อนหน้า
ความซับซ้อนของเวลาคืออะไร และเปรียบเทียบกับ Dijkstra อย่างไร?
Bellman-Ford ทำงานในเวลา O(VE) โดยที่ V คือจุดยอด และ E คือขอบ Dijkstra ทำงานใน O((V+E)logV) ด้วยฮีปไบนารี Bellman-Ford ช้ากว่าแต่จัดการกับน้ำหนักลบได้; Dijkstra เร็วกว่าแต่ต้องใช้น้ำหนักที่ไม่เป็นลบ
Bellman-Ford สามารถทำงานบนกราฟไม่มีทิศทางที่มีน้ำหนักลบได้หรือไม่?
ในทางเทคนิคแล้วทำได้ แต่สามารถสร้างวงจรลบปลอมได้เนื่องจากลักษณะสองทิศทางของขอบ ต้องใช้ความระมัดระวังเป็นพิเศษในการตีความผลลัพธ์อย่างถูกต้อง สำหรับกราฟไม่มีทิศทาง ให้พิจารณาแนวทางอื่น ๆ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วFord, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว