ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน

ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน (อังกฤษ: Ford–Fulkerson algorithm) เป็นขั้นตอนวิธีสำหรับแก้ปัญหาเรื่องการไหลมากสุด (maximum flow) ของการไหลในเครือข่าย (network flow) ซึ่งขั้นตอนวิธีนี้ถูกพัฒนาขึ้นโดย Lester Randolph Ford และ Delbert Ray Fulkerson ได้รับการตีพิมพ์เผยแพร่ในปี ค.ศ. 1956

อธิบายปัญหา

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

แนวความคิดหลัก

เราสามารถนำปัญหานี้มาเขียนให้อยู่ในรูปของทฤษฎีกราฟได้ โดยการแปลงปัญหาดังกล่าวเป็น กราฟมีทิศทาง (directed graph) ที่ทุกๆเส้นเชื่อม (ท่อน้ำ) จะมีน้ำหนักเป็น ความจุ c (ขนาดของท่อน้ำ) รวมทั้งกราฟจะประกอบด้วยปมต้นทาง X (ต้นน้ำ) และปมปลายทาง Y (อ่างน้ำที่เป็นปลายทางของน้ำ) นอกจากนี้ยังมีค่าพิเศษคือค่าการไหลของเส้นเชื่อม f กำกับในเส้นเชื่อม ซึ่งค่า f<=c สำหรับทุกเส้นเชื่อม และผลรวมของการไหล f จากเส้นเชื่อมใดๆที่เข้าสู่ปมจะมีค่าเท่ากับผลรวมของการไหล f จากเส้นเชื่อมที่ออกจากปมนั้นๆ เป้าหมายที่เราต้องการคือการหาผลรวมที่มากที่สุดที่เป็นไปได้ของการไหล f ที่ออกจากปมต้นทาง (โดยค่านั้นจะเท่ากับผลรวมของการไหล f ที่เข้าสู่ปมปลายทางด้วยเช่นกัน)

สำหรับอัลกอรึทึม จะนิยามถึงคำสองคำที่จะใช้ในการอธิบาย

1. เครือข่ายตกค้าง (residual network) คือ เครือข่ายที่มีปมเหมือนเครือข่ายดั้งเดิม และเส้นเชื่อมแต่ละเส้นในเครือข่ายดั้งเดิมจะถูกแทนที่ด้วยเส้นเชื่อมใหม่จำนวนหนึ่งหรือสองเส้นเชื่อม โดยถ้าการไหลของเส้นเชื่อมที่เชื่อมปม x ไปยังปม y (x-y) มีค่าน้อยกว่าความจุ เส้นเชื่อมใหม่เส้นหนึ่งจะเป็นเส้นเชื่อมที่มีทิศเดิมจากปม x ไปยังปม y (x-y) โดยความจุของเส้นเชื่อมใหม่เส้นนี้จะมีค่าเท่ากับผลต่างของความจุและการไหล (เรียกว่า ความจุคงเหลือ (resident capacity)) และถ้าหากการไหลมีค่าไม่เป็น 0 แล้วจะมีเส้นเชื่อมใหม่อีกเส้นหนึ่งมีทิศย้อนกลับ คือจากปม y ไปยังปม x (y-x) โดยความจุของเส้นเชื่อมนี้จะเท่ากับค่าการไหลของ x-y
2. วิถีแต่งเติม (augmenting path) คือ วิถีจากปมต้นทางถึงปมปลายทางในเครือข่ายตกค้าง (residual network) ที่ทำให้เพิ่มปริมาณการไหลในเครือข่ายให้มากขึ้น ข้อสำคัญของวิถีแต่งเติมนี้คือวิถีนั้นจะสามารถมีท่อน้ำที่ใช้ผิดทางไปจากเครือข่ายดั้งเดิมได้ โดยความจุของวิถีจะเท่ากับความจุของเส้นเชื่อมซึ่งมีความจุที่น้อยที่สุด

หลักการทำงานของขั้นตอนวิธี

• เริ่มต้นการทำงานด้วยกราฟที่ไม่เกิดการไหลใดๆในเครือข่ายเลย
• จากนั้นจะทำการเพิ่มปริมาณการไหลในเครือข่ายขึ้นเรื่อยๆ ตราบใดก็ตามที่ยังมีวิถีแต่งเติมจากปมต้นทางไปยังปมปลายทางในเครือข่ายตกค้าง

โปรแกรมตัวอย่าง

ขั้นตอนวิธีสามารถเขียนอธิบายในรูปแบบของโปรแกรมตัวอย่างได้ ดังนี้

Algorithm Ford–Fulkerson
   input: กราฟ G ที่ต้องการหาค่าการไหลมากสุด พร้อมทั้งค่าความจุ C, ปมเริ่มต้น
   result=0     //ตั้งค่าผลลัพธ์เริ่มต้นให้เป็น 0
   for each edge (u,v) in G
      f(u,v) = 0        //ตั้งค่าเริ่มต้นค่าการไหลของเส้นเชื่อมเป็น 0 ให้ทุกเส้นเชื่อมในกราฟ G 
   while(true)
      P = findPath( )	     //ทำการหาวิถีแต่งเติม (คำสั่ง findPath จะคืนวิถีแต่งเติมที่พบ)
      pathCapacity = min(c) in path P	     //ให้ pathCapacity เป็นค่าความจุที่น้อยสุดของค่าความจุ c ของทุกเส้นเชื่อมในวิถี P (ซึ่งก็คือปริมาณการไหลในวิถีนั้น)
      if (pathCapacity <= 0) exit while	     //ถ้าไม่สามารถหาวิถีแต่งเติมได้อีกแล้ว ให้หยุดการทำงานออกจากวงวน
      else result += pathCapacity	     //ผลลัพธ์ใหม่เท่ากับผลรวมของผลลัพธ์เดิมและความจุของวิถีแต่งเติม
      for each edge (u,v) in P	     //วนทำงานทุกเส้นเชื่อมในวิถี P เพื่อปรับปรุงเครือข่ายตกค้าง
            f(u,v) = f(u,v) + pathCapacity        //เพิ่มค่าการไหลของเส้นเชื่อมให้กับเส้นเชื่อมที่มีทิศทางเดียวกับการไหลในวิถีแต่งเติม 
            f(v,u) = f(v,u) - pathCapacity        //เพิ่มค่าการไหลของเส้นเชื่อมให้กับเส้นเชื่อมที่มีทิศทางตรงข้ามกับการไหลในวิถีแต่งเติม 
   end while
return result      //คืนค่าผลลัพธ์ที่ต้องการ (ค่าการไหลมากสุด)

สำหรับขั้นตอนในการหาวิถีแต่งเติม (คำสั่ง findPath) สามารถนำไปเขียนใช้งานจริงได้หลากหลายวิธี

1. การค้นหาตามแนวลึก (Depth-First Search)
2. การค้นหาตามแนวกว้าง (Breadt-First Search) หากใช้ BFS ในการหาวิถีแต่งเติมจะเรียกว่า ขั้นตอนวิธีของเอ็ดมอนด์-คาป

ข้อจำกัด

ขั้นตอนวิธีนี้จะสามารถรับประกันได้ว่าการทำงานดังกล่าวมีจุดสิ้นสุด ก็ต่อเมื่อ

1. ค่าความจุ c และการไหล f ของเส้นเชื่อมมีค่าเป็นจำนวนเต็ม
2. ค่าความจุรวมของทั้งวิถีมีค่าเป็นจำนวนบวก ซึ่งจะทำให้การทำงานในแต่ละขั้นตอนได้ผลลัพธ์ที่ใกล้เคียงกับ คำตอบที่ต้องการมากขึ้นเรื่อยๆ

ถ้าหากไม่เป็นไปตามเงื่อนไขดังกล่าว จะไม่สามารถรับประกันได้ว่าการทำงานมีจุดสิ้นสุด (อาจเกิดการการทำงานไปเรื่อยๆ ไม่สามารถหาที่สิ้นสุดได้ ไม่สามารถใช้ในการหาคำตอบได้) อย่างไรก็ตามหากเราใช้ ขั้นตอนวิธีของเอ็ดมอนด์-คาป จะสามารถแก้ไขข้อจำกัดดังกล่าวในขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สันได้

ประสิทธิภาพเชิงเวลา

จะขึ้นกับวิธีที่ใช้ในการหาวิถีแต่งเติม

1. หากใช้การค้นหาตามแนวลึก (Depth-First Search) ในกรณีที่ถูกต้องตามข้อจำกัด (การทำงานดังกล่าวมีจุดสิ้นสุด) จะได้ประสิทธิภาพเชิงเวลาเป็น O(Ef) โดยที่ E คือจำนวนเส้นเชื่อม และ f คือค่าการไหลมากสุด
2. หากใช้การค้นหาตามแนวกว้าง (Breadt-First Search) สามารถรับประกันการทำงานดังกล่าวมีจุดสิ้นสุด จะได้ประสิทธิภาพเชิงเวลาเป็น O(VE²) โดยที่ V คือจำนวนปม และ E คือจำนวนเส้นเชื่อม (สามารถดูรายละเอียดเชิงลึกได้ที่ ขั้นตอนวิธีของเอ็ดมอนด์-คาป)

ปัญหาที่เกี่ยวข้อง

นอกจากขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สันจะใช้ในการแก้ปัญหาการไหลมากสุดแล้ว สามารถนำไปใช้กับปัญหาอื่นๆได้อีกมากมายที่มีพื้นฐานมาจากปัญหาการไหลมากสุด ตัวอย่างเช่น

• การจับคู่กราฟสองส่วนมากสุด (Maximum Bipartite Matching)
• การแยกส่วนภาพ (Image Segementation)
• การทำเหมืองข้อมูล (Data mining)
• การเชื่อมต่อเครือข่าย (Network Connectivity)

อ้างอิง

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26.2". Introduction to Algorithms (second ed.). MIT Press and McGraw–Hill. หน้า 660–663. ISBN 0-262-53196-8.
• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
• http://aduni.org/courses/algorithms/courseware/handouts/Reciation_09.html เก็บถาวร 2011-08-07 ที่ เวย์แบ็กแมชชีน