อัลกอริทึม 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)
- การวิเคราะห์โปรตีน: การคำนวณการไหลสูงสุดในเครือข่ายชีวภาพเพื่อทำความเข้าใจเส้นทางการปฏิสัมพันธ์
วิธีการทำงาน
วิธีการทำงาน
เริ่มต้นกราฟส่วนเหลือ (residual graph) ด้วยความจุที่เท่ากับความจุของเส้นเชื่อมเดิมและการไหลเป็นศูนย์บนเส้นเชื่อมทั้งหมด
ค้นหาเส้นทางเสริมจากต้นทางไปยังปลายทางในกราฟส่วนเหลือโดยใช้การค้นหาเชิงลึก (depth-first search) หรือการค้นหาเชิงกว้าง (breadth-first search) คำนวณความจุขั้นต่ำตามเส้นทาง และเพิ่มการไหลนี้ไปยังเส้นเชื่อมทั้งหมดบนเส้นทางพร้อมทั้งลดความจุส่วนเหลือของเส้นเชื่อมเหล่านั้น
ทำซ้ำการเสริมจนกว่าจะไม่พบเส้นทางเสริมในกราฟส่วนเหลือ การไหลสะสมทั้งหมดคือการไหลสูงสุด
ข้อผิดพลาดที่พบบ่อย
- การเลือกเส้นทางเสริมที่ไม่ดีซึ่งนำไปสู่การลู่เข้าช้าหรือผลลัพธ์ที่ไม่ถูกต้อง
- การไม่ปรับปรุงความจุส่วนเหลืออย่างถูกต้อง หรือการเพิ่มเส้นเชื่อมย้อนกลับเพื่อยกเลิกการไหล
- การใช้การหารจำนวนเต็มหรือเลขคณิตทศนิยมเมื่อต้องการเลขคณิตที่แม่นยำเพื่อความถูกต้อง
คำถามที่พบบ่อย
ทฤษฎีบทการไหลสูงสุด-การตัดน้อยสุดคืออะไร?
ทฤษฎีบทนี้ระบุว่าการไหลสูงสุดจากต้นทางไปยังปลายทางเท่ากับความจุของการตัดน้อยสุดที่แยกต้นทางออกจากปลายทาง สิ่งนี้ให้ทั้งข้อมูลเชิงลึกทางทฤษฎีและวิธีการตรวจสอบสำหรับอัลกอริทึมการไหล
เหตุใดอัลกอริทึมจึงลู่เข้าช้าในบางครั้ง?
ด้วยการเลือกเส้นทางที่ไม่เหมาะสม อัลกอริทึมอาจเพิ่มการไหลเพียงหนึ่งหน่วยต่อรอบการทำงาน แม้ว่าการเพิ่มที่ใหญ่กว่าจะเป็นไปได้ การใช้การค้นหาเชิงกว้าง (Edmonds-Karp) จะรับประกันการลู่เข้าในเวลาพหุนาม
อัลกอริทึมจัดการกับเส้นเชื่อมที่ไม่มีทิศทางอย่างไร?
แทนที่เส้นเชื่อมที่ไม่มีทิศทางแต่ละเส้นด้วยเส้นเชื่อมมีทิศทางสองเส้นในทิศทางตรงกันข้าม โดยทั้งสองเส้นมีความจุเท่ากัน จากนั้นอัลกอริทึมจะหาการไหลในเครือข่ายมีทิศทาง
ความแตกต่างระหว่างการไหลบนเส้นเชื่อมและความจุส่วนเหลือคืออะไร?
การไหลบนเส้นเชื่อมแสดงถึงปริมาณวัสดุที่ส่งไปตามเส้นนั้น ในขณะที่ความจุส่วนเหลือคือความจุที่เหลืออยู่ ความจุส่วนเหลือจะลดลงเมื่อการไหลเพิ่มขึ้น และเส้นเชื่อมย้อนกลับจะติดตามความสามารถในการยกเลิกการไหล
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว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คัดลอกแล้ว