Skip to content
กลับไปยังผลการค้นหา

ขั้นตอนวิธีเบลล์แมน-ฟอร์ด

ผู้เสนอ
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)
  • ทำงานได้ทั้งบนกราฟมีทิศทางและไม่มีทิศทาง (โดยต้องระมัดระวังในกราฟไม่มีทิศทาง)

การประยุกต์ใช้

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

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดระยะทางไปยังแหล่งกำเนิดเป็นศูนย์ และระยะทางอื่น ๆ ทั้งหมดเป็นอนันต์ อาจกำหนดตัวก่อนหน้าทั้งหมดเป็น null

2

ทำซ้ำ V-1 ครั้ง: สำหรับแต่ละขอบ (u, v) ที่มีน้ำหนัก w หาก distance[u] + w น้อยกว่า distance[v] ให้อัปเดต distance[v] และตัวก่อนหน้าของ v

3

ตรวจสอบขอบทั้งหมดอีกครั้ง; หากระยะทางใด ๆ ดีขึ้น แสดงว่ามีวงจรน้ำหนักลบอยู่ ส่งคืนข้อผิดพลาดหรือระบุวงจรตามความเหมาะสม

ข้อผิดพลาดที่พบบ่อย

  • ลืมทำการวนซ้ำเพิ่มเติมเพื่อตรวจจับวงจรลบ
  • สมมติว่าขั้นตอนวิธีทำงานได้อย่างถูกต้องในกราฟไม่มีทิศทางที่มีขอบเป็นลบ (อาจสร้างวงจรลบเสมือนได้)
  • ใช้ขั้นตอนวิธีนี้เมื่อ 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 สามารถทำงานบนกราฟไม่มีทิศทางที่มีน้ำหนักลบได้หรือไม่?

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

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว