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

อัลกอริทึม Ford-Fulkerson

ผู้เสนอ
Lester R. Ford and Delbert R. Fulkerson
ปี
1956
ประเภท
algorithm
กลุ่มวิธี
Graph Algorithms

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

อัลกอริทึม Ford-Fulkerson ซึ่งพัฒนาโดย Lester R. Ford และ Delbert R. Fulkerson ในปี 1956 เป็นวิธีการพื้นฐานสำหรับการคำนวณการไหลสูงสุด (maximum flow) ในเครือข่ายการไหล (flow network) อัลกอริทึมนี้หาปริมาณการไหลสูงสุดที่สามารถส่งจากต้นทาง (source) ไปยังปลายทาง (sink) ผ่านกราฟมีทิศทาง (directed graph) ที่มีข้อจำกัดความจุ (capacity constraints) บนเส้นเชื่อม (edges)

แนวคิดเบื้องหลังวิธีการ

อัลกอริทึมทำงานโดยการค้นหาเส้นทางเสริม (augmenting paths) ซ้ำๆ จากต้นทางไปยังปลายทางผ่านเครือข่ายส่วนเหลือ (residual network) ซึ่งแต่ละเส้นเชื่อมมีความจุคงเหลือ เส้นทางแต่ละเส้นจะเพิ่มการไหลอีกเท่ากับความจุคอขวด (bottleneck capacity) ของเส้นทางนั้น (คือเส้นเชื่อมที่มีความจุคงเหลือต่ำสุดบนเส้นทาง) กระบวนการจะดำเนินต่อไปจนกว่าจะไม่พบเส้นทางเสริมอีกต่อไป ณ จุดนั้น จะได้การไหลสูงสุด ทฤษฎีบทสำคัญคือทฤษฎีบทการไหลสูงสุด-การตัดน้อยสุด (max-flow min-cut theorem): การไหลสูงสุดจะเท่ากับความจุของการตัดน้อยสุด (minimum cut capacity) ในเครือข่าย

ประวัติศาสตร์

Ford และ Fulkerson ได้นำเสนอปัญหาการไหลสูงสุดและอัลกอริทึมที่เป็นแบบฉบับของพวกเขาในปี 1956 ผลงานนี้เป็นการปฏิวัติวงการ โดยได้วางรากฐานทั้งวิธีการเชิงอัลกอริทึมและทฤษฎีบทการไหลสูงสุด-การตัดน้อยสุดอันโด่งดัง Edmonds และ Karp (1972) ได้ปรับปรุงความซับซ้อนในกรณีที่แย่ที่สุดโดยใช้การค้นหาเชิงกว้างสำหรับการเลือกเส้นทาง การพัฒนาต่อมาโดย Dinic, Karzanov และคนอื่นๆ ได้นำไปสู่อัลกอริทึมที่เร็วยิ่งขึ้น แต่ระเบียบวิธี Ford-Fulkerson ยังคงเป็นอัลกอริทึมคลาสสิกและมีคุณค่าทางการสอนในวิทยาการคอมพิวเตอร์

ควรใช้เมื่อใด

ใช้อัลกอริทึม Ford-Fulkerson เพื่อหาการไหลสูงสุดในเครือข่ายการไหลแบบมีทิศทางหรือไม่มีทิศทางที่มีความจุเป็นจำนวนเต็มบวก อัลกอริทึมนี้ทำงานได้ดีสำหรับเครือข่ายขนาดเล็กถึงขนาดกลาง และให้ความเข้าใจที่ชัดเจนเกี่ยวกับแนวคิดการไหลในเครือข่าย สำหรับเครือข่ายขนาดใหญ่มากหรือเมื่อต้องการการไหลเป็นจำนวนเต็ม ควรพิจารณา Edmonds-Karp (ใช้ BFS) หรือ Dinic's algorithm เพื่อประสิทธิภาพในกรณีที่แย่ที่สุด (worst-case performance) ควรใช้อัลกอริทึมนี้เมื่อการทำความเข้าใจพฤติกรรมของอัลกอริทึมมีความสำคัญเท่ากับความเร็ว

ข้อจำกัดและข้อควรพิจารณา

  • ความซับซ้อนด้านเวลาขึ้นอยู่กับค่าความจุ (โดยทั่วไปไม่เป็นพหุนาม อาจเป็นเลขชี้กำลังสำหรับความจุที่เป็นจำนวนอตรรกยะ)
  • อาจไม่สิ้นสุดหากความจุเป็นจำนวนอตรรกยะ (ต้องมีการดำเนินการอย่างระมัดระวังด้วยเลขคณิตตรรกยะ)
  • มีประสิทธิภาพน้อยกว่าอัลกอริทึมเฉพาะทาง เช่น Edmonds-Karp หรือ Dinic สำหรับเครือข่ายขนาดใหญ่
  • ไวต่อลำดับการเลือกเส้นทางเสริม

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

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

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

  • การจัดเส้นทางเครือข่าย: การเพิ่มปริมาณข้อมูลสูงสุดจากต้นทางไปยังปลายทางในเครือข่ายการสื่อสาร
  • เครือข่ายการขนส่ง: การกำหนดความจุสัมภาระสูงสุดระหว่างเมืองโดยพิจารณาข้อจำกัดของถนนและราง
  • การจับคู่แบบสองส่วน (Bipartite matching): การหาการจับคู่สูงสุดในกราฟแบบสองส่วนโดยการสร้างเครือข่ายการไหล
  • การแบ่งส่วนภาพ (Image segmentation): การใช้อัลกอริทึมการไหลสูงสุดเพื่อแบ่งภาพออกเป็นส่วนหน้าและส่วนหลัง
  • การจัดตารางการบิน: การเพิ่มประสิทธิภาพการจัดเส้นทางเครื่องบินเพื่อเพิ่มการไหลของผู้โดยสารผ่านเครือข่ายแบบฮับแอนด์สโปค (hub-and-spoke networks)
  • การวิเคราะห์โปรตีน: การคำนวณการไหลสูงสุดในเครือข่ายชีวภาพเพื่อทำความเข้าใจเส้นทางการปฏิสัมพันธ์

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

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

1

เริ่มต้นกราฟส่วนเหลือ (residual graph) ด้วยความจุที่เท่ากับความจุของเส้นเชื่อมเดิมและการไหลเป็นศูนย์บนเส้นเชื่อมทั้งหมด

2

ค้นหาเส้นทางเสริมจากต้นทางไปยังปลายทางในกราฟส่วนเหลือโดยใช้การค้นหาเชิงลึก (depth-first search) หรือการค้นหาเชิงกว้าง (breadth-first search) คำนวณความจุขั้นต่ำตามเส้นทาง และเพิ่มการไหลนี้ไปยังเส้นเชื่อมทั้งหมดบนเส้นทางพร้อมทั้งลดความจุส่วนเหลือของเส้นเชื่อมเหล่านั้น

3

ทำซ้ำการเสริมจนกว่าจะไม่พบเส้นทางเสริมในกราฟส่วนเหลือ การไหลสะสมทั้งหมดคือการไหลสูงสุด

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

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

คำถามที่พบบ่อย

ทฤษฎีบทการไหลสูงสุด-การตัดน้อยสุดคืออะไร?

ทฤษฎีบทนี้ระบุว่าการไหลสูงสุดจากต้นทางไปยังปลายทางเท่ากับความจุของการตัดน้อยสุดที่แยกต้นทางออกจากปลายทาง สิ่งนี้ให้ทั้งข้อมูลเชิงลึกทางทฤษฎีและวิธีการตรวจสอบสำหรับอัลกอริทึมการไหล

เหตุใดอัลกอริทึมจึงลู่เข้าช้าในบางครั้ง?

ด้วยการเลือกเส้นทางที่ไม่เหมาะสม อัลกอริทึมอาจเพิ่มการไหลเพียงหนึ่งหน่วยต่อรอบการทำงาน แม้ว่าการเพิ่มที่ใหญ่กว่าจะเป็นไปได้ การใช้การค้นหาเชิงกว้าง (Edmonds-Karp) จะรับประกันการลู่เข้าในเวลาพหุนาม

อัลกอริทึมจัดการกับเส้นเชื่อมที่ไม่มีทิศทางอย่างไร?

แทนที่เส้นเชื่อมที่ไม่มีทิศทางแต่ละเส้นด้วยเส้นเชื่อมมีทิศทางสองเส้นในทิศทางตรงกันข้าม โดยทั้งสองเส้นมีความจุเท่ากัน จากนั้นอัลกอริทึมจะหาการไหลในเครือข่ายมีทิศทาง

ความแตกต่างระหว่างการไหลบนเส้นเชื่อมและความจุส่วนเหลือคืออะไร?

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

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

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

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    คัดลอกแล้ว