ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน (อังกฤษ: 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(VE2) โดยที่ 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 ที่ เวย์แบ็กแมชชีน