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

ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน (อังกฤษ: 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 ที่เข้าสู่ปมปลายทางด้วยเช่นกัน)

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

เครือข่ายตกค้าง (residual network) คือ เครือข่ายที่มีปมเหมือนเครือข่ายดั้งเดิม และเส้นเชื่อมแต่ละเส้นในเครือข่ายดั้งเดิมจะถูกแทนที่ด้วยเส้นเชื่อมใหม่จำนวนหนึ่งหรือสองเส้นเชื่อม โดยถ้าการไหลของเส้นเชื่อมที่เชื่อมปม x ไปยังปม y (x-y) มีค่าน้อยกว่าความจุ เส้นเชื่อมใหม่เส้นหนึ่งจะเป็นเส้นเชื่อมที่มีทิศเดิมจากปม x ไปยังปม y (x-y) โดยความจุของเส้นเชื่อมใหม่เส้นนี้จะมีค่าเท่ากับผลต่างของความจุและการไหล (เรียกว่า ความจุคงเหลือ (resident capacity)) และถ้าหากการไหลมีค่าไม่เป็น 0 แล้วจะมีเส้นเชื่อมใหม่อีกเส้นหนึ่งมีทิศย้อนกลับ คือจากปม y ไปยังปม x (y-x) โดยความจุของเส้นเชื่อมนี้จะเท่ากับค่าการไหลของ x-y
วิถีแต่งเติม (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) สามารถนำไปเขียนใช้งานจริงได้หลากหลายวิธี

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

ข้อจำกัด

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

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

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

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

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

หากใช้การค้นหาตามแนวลึก (Depth-First Search) ในกรณีที่ถูกต้องตามข้อจำกัด (การทำงานดังกล่าวมีจุดสิ้นสุด) จะได้ประสิทธิภาพเชิงเวลาเป็น O(Ef) โดยที่ E คือจำนวนเส้นเชื่อม และ f คือค่าการไหลมากสุด
หากใช้การค้นหาตามแนวกว้าง (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 ที่ เวย์แบ็กแมชชีน