เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)

เกี่ยวกับ เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)

เครื่องคำนวณการไหลในเครือข่าย จะคำนวณ การไหลสูงสุด จากแหล่งกำเนิด (source) s ไปยังปลายทาง (sink) t ที่เลือกในเครือข่ายแบบมีทิศทางที่มีความจุ เบื้องหลังการทำงานจะใช้ วิธี Ford-Fulkerson ร่วมกับ การค้นหาเส้นทางที่เพิ่มขึ้นแบบ Breadth-First (อัลกอริทึม Edmonds-Karp) จากนั้นจะบันทึกทุกเส้นทางที่พบเพื่อให้คุณสามารถย้อนดูขั้นตอนการตัดสินใจทั้งหมดได้ทีละรายการ หน้าผลลัพธ์ยังแสดง min-cut ซึ่งเป็นส่วนแบ่งคอขวดที่พิสูจน์ว่าค่าการไหลของคุณนั้นเหมาะสมที่สุดแล้วจริงๆ

ปัญหาการไหลสูงสุดคืออะไร?

เครือข่ายการไหล (flow network) คือกราฟมีทิศทาง G = (V, E) พร้อมกับฟังก์ชันความจุ c: E → ℝ_≥0 โดยมีจุดยอดสองจุดที่แยกกันคือ แหล่งกำเนิด s (จุดที่การไหลเริ่มต้น) และ ปลายทาง t (จุดที่การไหลถูกใช้ไป) การไหล f คือการกำหนดค่า f(u, v) ≥ 0 บนขอบที่เป็นไปตามกฎ:

ปัญหาการไหลสูงสุด คือการหาการไหล f ที่ทำให้ค่า |f| มีค่าสูงสุด เปรียบเทียบได้ง่ายๆ ว่า: หากขอบเป็นท่อน้ำที่มีความจุที่กำหนด คุณจะสามารถส่งน้ำจาก s ไปยัง t ได้กี่ลิตรต่อวินาที?

อัลกอริทึมทำงานอย่างไร — Ford-Fulkerson ด้วย BFS

อัลกอริทึมจะรักษา กราฟส่วนเหลือ (residual graph) ควบคู่ไปกับการไหลปัจจุบัน สำหรับทุกขอบ (u, v) ที่มีความจุ c และการไหลปัจจุบัน f กราฟส่วนเหลือจะประกอบด้วย:

• ขอบส่วนเหลือไปข้างหน้า (u, v) ที่มีความจุ c − f (ยังผลักเพิ่มได้อีกเท่าไหร่) และ
• ขอบส่วนเหลือย้อนกลับ (v, u) ที่มีความจุ f (สามารถยกเลิกการไหลที่ส่งไปแล้วได้เท่าไหร่)

ในการทำซ้ำแต่ละครั้ง จะมีการดำเนินการ Breadth-First Search (BFS) จาก s ไปยัง t บนกราฟส่วนเหลือ หากพบเส้นทาง ความจุที่น้อยที่สุดบนเส้นทางนั้น — หรือ คอขวด — จะถูกนำไปบวกเข้ากับการไหลในทุกขอบไปข้างหน้า และลบออกในทุกขอบย้อนกลับตามเส้นทางนั้น สิ่งนี้เรียกว่า เส้นทางที่เพิ่มขึ้น (augmenting path) เมื่อ BFS ไม่สามารถเข้าถึง t ได้อีกต่อไป การไหลปัจจุบันจะถือว่าเหมาะสมที่สุด

การใช้ BFS (แทนที่จะเป็นกลยุทธ์การหาเส้นทางแบบสุ่ม) จะเปลี่ยน Ford-Fulkerson เป็น Edmonds-Karp โดยรับประกันเวลาการทำงานที่ O(V · E²) นอกจากนี้ยังรับประกันการสิ้นสุดการทำงานในกรณีความจุที่เป็นจำนวนอตรรกยะ ซึ่ง Ford-Fulkerson แบบธรรมดาอาจทำไม่ได้

ทฤษฎีบท Max-Flow Min-Cut

คัต (cut) คือการแบ่งจุดยอดออกเป็นสองเซต (S, T) โดยที่ s ∈ S และ t ∈ T ความจุ ของคัตคือผลรวมของความจุของขอบที่ส่งจาก S ไปยัง T:

ทฤษฎีบท max-flow min-cut (Ford & Fulkerson, 1956) ระบุว่า:

เครื่องมือนี้จะหา min-cut โดยอัตโนมัติ หลังจาก Edmonds-Karp สิ้นสุดลง มันจะรัน BFS อีกหนึ่งครั้งจาก s บนกราฟส่วนเหลือ จุดยอดที่เข้าถึงได้จะรวมเป็นเซต S ส่วนที่เหลือคือ T และทุกขอบที่ข้ามจาก S → T ในกราฟต้นฉบับจะอิ่มตัว ผลรวมความจุของขอบเหล่านี้จะเท่ากับค่าการไหลสูงสุดพอดี — สามารถดูได้ในส่วนผลลัพธ์ที่ระบุว่า "ความจุ Min-cut ✓ ยืนยันความเหมาะสมที่สุด"

คุณสมบัติที่สร้างมาเพื่อการเรียนรู้

• แอนิเมชันทีละขั้นตอน: เล่นซ้ำทุกเส้นทางที่เพิ่มขึ้นพร้อมตัวควบคุมการเล่น หยุดชั่วคราว และเลื่อนทีละขั้น ดูว่า BFS เลือกเส้นทางไหน ขอบไหนเป็นคอขวด และยอดรวมการไหลเพิ่มขึ้นอย่างไร
• เมทริกซ์สามตัวที่ซิงโครไนซ์กัน: สลับระหว่างเมทริกซ์ความจุ C, เมทริกซ์การไหลสุดท้าย f และเมทริกซ์ส่วนเหลือ C − f — ภาพสามภาพที่รวมกันเพื่ออธิบายลักษณะการไหลใดๆ
• มุมมองการแบ่ง Min-cut: รายชื่อจุดยอดฝั่ง S และฝั่ง T จะแสดงเป็นชิป พร้อมเน้นขอบอิ่มตัวที่ข้ามคัตด้วยสีแดง
• ตารางแยกตามขอบ: สำหรับทุกขอบ: แสดงความจุ การไหล ส่วนเหลือ แถบแสดงเปอร์เซ็นต์การใช้งาน และสถานะความอิ่มตัว
• เลย์เอาต์แบบเลเยอร์จากซ้ายไปขวา: การวาดกราฟจะคำนวณจากระยะทาง BFS จากแหล่งกำเนิด เพื่อให้น้ำ "ไหล" จากซ้ายไปขวาอย่างชัดเจน เหมือนที่วาดในตำราเรียน

รูปแบบข้อมูลนำเข้า

1. รายการขอบพร้อมความจุ

หนึ่งขอบต่อหนึ่งบรรทัด รูปแบบลูกศรอ่านง่ายที่สุดแต่รองรับรูปแบบอื่นด้วย:

รูปแบบที่ยอมรับเช่นกัน: A, B, 10 · A B 10 · A -> B , 10 หากมีขอบหลายเส้นระหว่างจุดคู่เดียวกัน ความจุจะถูกนำมารวมกัน

2. เมทริกซ์ความจุ

หนึ่งแถวต่อหนึ่งบรรทัด คั่นค่าด้วยช่องว่างหรือจุลภาค ค่าใน C[i][j] คือความจุของขอบจากจุดยอด i ไปยังจุดยอด j ใช้ 0 สำหรับ "ไม่มีขอบ" เมทริกซ์ต้องเป็นรูปสี่เหลี่ยมจัตุรัสและเส้นทแยงมุมต้องเป็น 0 (ไม่มีลูปกลับเข้าหาตัวเอง)

ป้อนชื่อป้ายกำกับจุดยอดที่ตรงกันในช่อง ป้ายกำกับเมทริกซ์ (คั่นด้วยจุลภาคหรือช่องว่าง) หากละเว้น จะใช้ค่าเริ่มต้นเป็น S, A, B, …, T

การประยุกต์ใช้การไหลสูงสุด

ตัวอย่างการคำนวณ

ตัวอย่างด่วนแบบ "ตำราเรียน" เข้ารหัสเครือข่าย 6 จุดโดยมีแหล่งกำเนิด S และปลายทาง T การรัน Edmonds-Karp จะได้เส้นทางที่เพิ่มขึ้นสี่เส้นทาง:

1. S → A → B → T ด้วยคอขวด 4 (ขอบ A-B เป็นตัวจำกัด) การไหลรวม: 4
2. S → A → D → T ด้วยคอขวด 6 การไหลรวม: 10
3. S → C → D → T ด้วยคอขวด 4 (ตอนนี้ขอบ D-T เป็นตัวจำกัด เหลือเพียง 4) การไหลรวม: 14
4. S → C → D → B → T ด้วยคอขวด 5 การไหลรวม: 19

อัลกอริทึมจะหยุดลงเพราะไม่มีเส้นทางที่เพิ่มขึ้นเหลืออยู่ min-cut คือ (S = {S, C}, T = {A, B, D, T}) โดยมีขอบที่ข้ามคัตคือ S → A (ความจุ 10) และ C → D (ความจุ 9) รวมเป็น 19 ซึ่งเท่ากับค่าการไหลสูงสุดพอดี

วิธีใช้เครื่องคำนวณนี้

1. เลือกรูปแบบข้อมูลนำเข้า โดยใช้แท็บ — รายการขอบ (แนะนำ) หรือเมทริกซ์ความจุ
2. ป้อนเครือข่ายของคุณ คุณสามารถเริ่มจากตัวอย่างด่วนแล้วแก้ไขข้อมูลได้ สำหรับอินพุตเมทริกซ์ โปรดระบุชื่อป้ายกำกับหากคุณต้องการชื่ออื่นนอกเหนือจาก S, A, B, …, T
3. ระบุแหล่งกำเนิดและปลายทาง (หรือปล่อยว่างไว้เพื่อตรวจหา S และ T อัตโนมัติ)
4. คลิก คำนวณการไหลสูงสุด หน้าผลลัพธ์จะแสดงค่าการไหลสูงสุด การแบ่ง min-cut ภาพจำลองกราฟแบบเลเยอร์ ทุกเส้นทางที่เพิ่มขึ้น ตารางการใช้งานขอบ และเมทริกซ์สามตัว (ความจุ, การไหล, ส่วนเหลือ)
5. เล่นแอนิเมชัน ใต้กราฟเพื่อดูการตัดสินใจของอัลกอริทึมซ้ำ คลิกที่ขั้นตอนเส้นทางที่เพิ่มขึ้นใดก็ได้เพื่อข้ามไปยังจุดนั้นโดยตรง

ข้อจำกัด

• จุดยอด: สูงสุด 30 จุด — เพื่อให้การแสดงผลและเมทริกซ์ยังอ่านง่าย
• ขอบ: สูงสุด 200 ขอบ
• ความจุ: ไม่เป็นลบ สูงสุด 10⁹ รองรับความจุที่เป็นทศนิยม
• ไม่มีลูปกลับเข้าหาตัวเอง: Self-loops ไม่มีการไหลในสูตรการไหลสูงสุดมาตรฐานและจะถูกปฏิเสธ

คำถามที่พบบ่อย

ปัญหาการไหลสูงสุดคืออะไร?

กำหนดเครือข่ายแบบมีทิศทางซึ่งแต่ละขอบมีความจุที่ไม่เป็นลบ ปัญหาการไหลสูงสุดถามว่า: สามารถส่งการไหลจากจุดยอดแหล่งกำเนิด s ที่กำหนดไปยังจุดยอดปลายทาง t ที่กำหนดได้มากเพียงใด ภายใต้กฎที่ว่าการไหลในแต่ละขอบต้องไม่เกินความจุ และการไหลที่เข้าสู่จุดยอดทุกจุดที่ไม่ใช่แหล่งกำเนิดหรือปลายทางต้องเท่ากับการไหลที่ออกจากจุดนั้น? คำตอบเรียกว่าค่าการไหลสูงสุด

วิธี Ford-Fulkerson คืออะไร?

Ford-Fulkerson เป็นเทคนิคทั่วไปสำหรับการคำนวณการไหลสูงสุด โดยจะค้นหาเส้นทางที่เพิ่มขึ้น (augmenting path) จากแหล่งกำเนิดไปยังปลายทางในกราฟส่วนเหลือซ้ำๆ และผลักการไหลให้ได้มากที่สุดตามเส้นทางนั้น (ความจุคอขวด) จากนั้นจึงอัปเดตกราฟส่วนเหลือ กระบวนการจะสิ้นสุดลงเมื่อไม่มีเส้นทางที่เพิ่มขึ้นเหลืออยู่ เมื่อนำมาใช้กับ Breadth-First Search สำหรับการเลือกเส้นทาง จะเรียกว่า Edmonds-Karp และรันในเวลา O(V · E²) time

min-cut ของเครือข่ายการไหลคืออะไร?

คัตคือการแบ่งจุดยอดออกเป็นสองเซต S และ T โดยที่แหล่งกำเนิดอยู่ใน S และปลายทางอยู่ใน T ความจุของคัตคือผลรวมของความจุของขอบจาก S ไปยัง T ส่วน min-cut คือคัตที่มีความจุน้อยที่สุด ทฤษฎีบท max-flow min-cut ที่มีชื่อเสียงพิสูจน์ว่าค่าการไหลสูงสุดจะเท่ากับความจุของ min-cut เสมอ ดังนั้นการหาค่าหนึ่งจึงทำให้ได้อีกค่าหนึ่งโดยอัตโนมัติ

กราฟส่วนเหลือคืออะไร?

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

ทำไมเครื่องมือนี้ถึงใช้ BFS สำหรับเส้นทางที่เพิ่มขึ้น?

การเลือกเส้นทางที่เพิ่มขึ้นด้วย Breadth-First Search (Edmonds-Karp) รับประกันการสิ้นสุดในเวลาพหุนามโดยไม่คำนึงถึงความจุของขอบ Ford-Fulkerson แบบธรรมดาที่มีกลยุทธ์การหาเส้นทางแบบสุ่มอาจวนลูปเป็นจำนวนครั้งแบบเอกซ์โพเนนเชียลในข้อมูลนำเข้าที่ซับซ้อน และในกรณีความจุที่เป็นจำนวนอตรรกยะอาจไม่สิ้นสุดเลย นอกจากนี้ BFS ยังสร้างเส้นทางที่เพิ่มขึ้นที่สั้นที่สุด ซึ่งอ่านและทำความเข้าใจได้ง่ายกว่า

ขอบอิ่มตัวหมายถึงอะไร?

ขอบจะอิ่มตัวเมื่อการไหลเท่ากับความจุ ทำให้ไม่สามารถผลักการไหลเพิ่มเติมผ่านขอบนั้นได้ ขอบอิ่มตัวคือคอขวดของเครือข่าย และทุกๆ min-cut จะประกอบด้วยขอบอิ่มตัวทั้งหมดจากฝั่ง S ไปยังฝั่ง T ของคัต เครื่องมือนี้จะเน้นขอบอิ่มตัวด้วยสีแดงเพื่อให้คุณเห็นโครงสร้างคอขวดได้ทันที

อ่านเพิ่มเติม

• ปัญหาการไหลสูงสุด — Wikipedia
• อัลกอริทึม Ford–Fulkerson — Wikipedia
• อัลกอริทึม Edmonds–Karp — Wikipedia
• ทฤษฎีบท Max-flow min-cut — Wikipedia