# ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน
ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน  เป็นขั้นตอนวิธีสำหรับแก้ปัญหาเรื่องการไหลมากสุด (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(VE2) โดยที่ V คือจำนวนปม และ E คือจำนวนเส้นเชื่อม (สามารถดูรายละเอียดเชิงลึกได้ที่ ขั้นตอนวิธีของเอ็ดมอนด์-คาป)

 ปัญหาที่เกี่ยวข้อง 
นอกจากขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สันจะใช้ในการแก้ปัญหาการไหลมากสุดแล้ว สามารถนำไปใช้กับปัญหาอื่น ๆ ได้อีกมากมายที่มีพื้นฐานมาจากปัญหาการไหลมากสุด
ตัวอย่างเช่น
 การจับคู่กราฟสองส่วนมากสุด (Maximum Bipartite Matching)
 การแยกส่วนภาพ (Image Segementation)
 การทำเหมืองข้อมูล (Data mining)
 การเชื่อมต่อเครือข่าย (Network Connectivity)