CoE KKU

ถ้ากำหนดให้มี directed graph $G = (V, E)$ ที่มี edge capacities $c_{v,w}$ โดยที่ขีดจำกัดของ edge นี้อาจหมายถึงจำนวนปริมาณน้ำที่สามารถจะไหลผ่านท่อได้เต็มที่หรืออาจจะหมายถึงจำนวนยานพาหนะที่ถนนระหว่างจุดตัด 2 จุดสามารถรองรับได้เต็มที่ก็ได้ ถ้าเรามีสอง vertices ที่ vertex แรกคือ s เรียกว่า source และ vertex ที่สองคือ t เรียกว่า sink และถ้าให้ใน edge (v, w) ใด ๆ จะมีของไหลผ่านได้สูงสุดเป็นจำนวน $c_{v,w}$ หน่วย กำหนดให้ที่ vertex v ใด ๆ ที่ไม่ใช่ s หรือ t จะมีของไหลทั้งหมดที่ไหลเข้ายัง vertex นั้นต้องเท่ากับของไหลทั้งหมดที่ไหลออกจากมัน ปัญหาที่เรียกว่า maximum flow problem คือปัญหาในการหาจำนวนสูงสุดของของไหลที่สามารถจะไหลจาก vertex s ไปยัง vertex t ได้ เช่นกราฟในรูปซ้ายมือของรูปที่ 9.37 มี maximum flow คือ 5 หน่วย ดังแสดงในรูปทางขวามือ

ดังที่กล่าวมาแล้วว่า แต่ละ edge ไม่สามารถรับของไหลได้เกินกว่าขีดจำกัดของมัน Vertex a ที่มีของเหลวไหลเข้าจำนวน 3 หน่วย ซึ่งจะแยกกระจายไปใน c และ d มีของเหลวไหลเข้า vertex d จำนวน 3 หน่วยจาก a และ b รวมกัน และไหลออกจาก d ไปยัง t จะเห็นได้ที่ vertex หนึ่งจะรับของเหลวเข้าจาก vertex อื่นและกระจายส่งออกในรูปแบบอย่างไรก็ได้ตราบเท่าที่การไหลของมันใน edge ไม่เกินขีดจำกัดและยังคงรักษา flow conservation ไว้ได้ (คือของไหลเข้าเท่ากับของไหลออก)

วิธีการแรกเพื่อแก้ปัญหา maximum flow ที่จะกล่าวถึงคือการแก้ปัญหาเป็น stages โดยเริ่มด้วยกราฟ $G$ ที่มีอยู่ และให้สร้างกราฟ $G_f$ และกราฟ $G_r$ กราฟ $G_f$ ที่สร้างขึ้นนี้เรียกว่า flow graph เพื่อใช้ระบุจำนวนปริมาณของของไหลที่เกิดใน stage หนึ่ง ๆ ของอัลกอริทึม ในตอนเริ่มต้นนั้น edges ทั้งหมดในกราฟ $G_f$ ยังไม่มีของไหลเลยและเราหวังว่าหลังจบอัลกอริทึมแล้วจะได้ $G_f$ ที่มี maximum flow กราฟ $G_r$ เรียกว่า residual graph เป็นกราฟที่บอกให้ทราบว่าจะสามารถเพิ่มการไหลในแต่ละ edge ได้อีกเท่าไหร่ ซึ่งสามารถคำนวณหาได้โดยลบจำนวนการไหลในแต่ละ edge ขณะนั้น ๆ ออกจากขีดจำกัดของ edge และเรียก edge ใน $G_r$ ว่า residual edge

ในแต่ละ stage ของการทำงานเราจะทำการหาเส้นทางใน $G_r$ จาก s ไป t และเรียกเส้นทางนี้ว่า augmenting path ค่าขีดจำกัดต่ำสุดของ edge บนเส้นทางที่เลือกนี้ก็คือจำนวนการไหลที่สามารถเพิ่มขึ้นได้ในทุก ๆ edge บนเส้นทาง เราทำโดยปรับเปลี่ยน $G_f$ และคำนวณ $G_r$ ใหม่ เมื่อไม่สามารถหาเส้นทางจาก s ไป t ใน $G_r$ ได้อีกต่อไป ก็เป็นอันจบการทำงาน อัลกอริทึมนี้เป็นแบบ nondeterministic คือเรามีอิสระที่จะเลือกเส้นทางใดก็ได้จาก s ไป t ซึ่งแน่นอนว่าบางเส้นทางที่เลือกอาจจะดีหรือไม่ดีกว่าเส้นทางอื่น ๆ ที่อาจเป็นไปได้ก็ได้และจะกล่าวถึงประเด็นนี้อีกครั้งข้างหน้า ต่อไปจะแสดงการใช้อัลกอริทึมนี้กับกราฟ รูปที่ 9.38 แสดงกราฟเริ่มต้นของ $G, G_f, G_r$ ตามลำดับ

มีเส้นทางหลายเส้นทางที่เราสามารถเลือกได้ใน residual graph สมมติถ้าเราเลือก s, b, d, t เราก็สามารถส่งของเหลวได้ 2 หน่วยไหลในเส้นทางนี้และถ้ามี edge ใดที่มีอัตราการไหลผ่านเท่ากับขีดจำกัดของมัน edge นั้นก็จะถูกเอาออกจาก residual graph ไปดังแสดงในรูปที่ 9.39

จากนั้นเลือกเส้นทาง s, a, c, t ซึ่งก็สามารถส่งของเหลวในเส้นทางนี้ได้จำนวน 2 หน่วยและทำการปรับปรุงกราฟดังในรูปที่ 9.40 เส้นทางที่เหลือให้เลือกได้ขณะนี้มีเพียงเส้นทางเดียว คือ s, a, d, t ซึ่งสามารถรับของเหลวได้ 1 หน่วย ดังรูปที่ 9.41 เป็นอันสิ้นสุดการทำงานของอัลกอริทึม เนื่องจากไม่สามารถหาเส้นทางจาก s ไปยัง t ได้อีกต่อไป ค่าสูงสุดของอัตราการไหลที่ได้คือ 5 หน่วย

ปัญหาของอัลกอริทึมนี้คือถ้าเราเลือกเส้นทาง s, a, d, t ในตั้งแต่ครั้งแรกจะได้อัตราการไหลในเส้นทางนี้ 3 หน่วยซึ่งสูงกว่า 2 หน่วยในการเลือกครั้งแรกที่กล่าวข้างบน อย่างไรก็ตามการเลือกคราวนี้ของเราทำให้เราไม่สามารถเลือกเส้นทางการไหลต่อไปได้อีกใน residual graph นั่นคือเราไม่สามารถหาเส้นทางที่เหมาะสมของการไหลในกราฟนี้ได้ นี่เป็นตัวอย่างหนึ่งของความล้มเหลวในการใช้ greedy algorithm รูปที่ 9.42 แสดงให้เห็นสิ่งที่เกิดขึ้น

เพื่อแก้ปัญหาดังกล่าวเราต้องให้อัลกอริทึมของเราเปลี่ยนใจได้ในระหว่างการทำงาน โดยที่เมื่อ edge (v, w) ใด ๆ ที่มีการไหล fv,w ใน edge นั้นที่ปรากฏใน flow graph ก็ให้ทำการเพิ่ม edge ลงใน residual graph (w, v) ด้วยอัตราการไหล fv,w เช่นกัน ผลก็คืออัลกอริทึมจะสามารถเปลี่ยนการตัดสินใจโดยส่งของไหลกลับในทิศทางตรงกันข้ามได้ ตัวอย่างจากกราฟเดิม เริ่มต้นจากกราฟเดิม และเลือก augmenting path s, a, d, t, จะได้กราฟในรูปที่ 9.43

จะเห็นว่าใน residual graph นั้นมี edge ระหว่าง a และ d ทั้งสองทิศทางซึ่งสามารถส่งผ่านหนึ่งหน่วยของไหลจาก a ไป d หรือได้ 3 หน่วยในทางตรงข้าม จากนั้นเลือก augmenting path s, b, d, a, c, t ด้วยขนาด 2 หน่วยของไหล โดยไหลจาก d ไป a จำนวน 2 หน่วยซึ่งเป็นการลดการไหลลงสองหน่วยใน edge (a, d) ซึ่งก็คือการเปลี่ยนใจนั่นเอง รูปที่ 9.44 แสดงกราฟใหม่ที่ได้ อัลกอริทึมจะหยุดการทำงานเพราะไม่มีเส้นทางให้เลือกอีกแล้ว เคยมีการพิสูจน์มาแล้วว่าถ้าค่าขีดจำกัดทั้งหมดของ edge เป็น rational number อัลกอริทึมนี้ก็จะสามารถให้คำตอบที่เป็นอัตราการไหลสูงสุดได้เสมอ (ไม่แสดงในที่นี้เนื่องจากซับซ้อนมาก)

ถ้าค่าขีดจำกัดการไหลของ edge ทั้งหมดเป็นเลขจำนวนเต็มและถ้ากราฟมีอัตราการไหลสูงสุดเป็น f ก็จะใช้จำนวน stage ในการทำงานเพียง f stage เนื่องจากแต่ละ augmenting path จะสามารถเพิ่มค่าการไหลได้อย่างน้อย 1 หน่วย และดังนั้น running time ที่ใช้ คือ O(f · |E|), เนื่องจากว่าเราสามารถตรวจหา augmenting path ได้ในเวลา O(|E|) หน่วยเวลาโดยการใช้อัลกอริทึมของ unweighted shortest-path algorithm ตัวอย่างคลาสสิกของภาวะที่ก่อให้เกิด running time ที่ไม่ดีแสดงในรูปที่ 9.45 ด้วยการสังเกตจากรูป จะพบว่าการไหลสูงสุดคือ 2,000,000 หน่วย โดยการส่งของเหลว 1,000,000 หน่วยลงในแต่ละข้าง แต่ในการเลือกแบบสุ่มอาจเป็นได้ที่จะมีการเลือกที่จะส่งผ่านของเหลวตามเส้นทาง a , b ซึ่งต้องทำงานถึง 2,000,000 ครั้ง

วิธีการง่าย ๆ เพื่อไม่ให้เกิดปัญหาที่กล่าวข้างบน เราจึงต้องทำการเลือก augmenting path ที่สามารถเพิ่มการไหลได้สูงสุดเสมอ การค้นหาเส้นทางดังกล่าวนี้ก็คล้ายกันกับการแก้ปัญหา weighted shortest-path และเพียงแก้ไขอัลกอริทึมของ Dijktra เล็กน้อยเท่านั้น ถ้าให้ $cap_{max}$ เป็นขีดจำกัดสูงสุดของ edge แล้วก็จะได้ว่าเราจะต้องใช้จำนวนครั้ง $O(|E|\ log(cap_{max}))$ เพื่อหาการไหลสูงสุด เนื่องจากต้องใช้เวลา $O(|E|\ log\ |V|)$ สำหรับการคำนวณของ augmenting path หนึ่ง ๆ นั่นคือขอบเขตเวลาที่ใช้จะเป็น $O(|E|^2\ log\ |V|\ log(cap_{max}))$ และถ้าหากว่าขีดจำกัดของ edge เป็นเพียงเลขจำนวนเต็มขนาดเล็ก ๆ แล้วก็จะได้ขอบเขตเวลาเป็น $O(|E|^2\ log\ |V|)$

อีกวิธีการหนึ่งที่อาจจะใช้ได้ในการเลือก augmenting paths คือจะเลือกเส้นทางที่ประกอบด้วยจำนวน edge ที่น้อยที่สุดเสมอด้วยหวังว่าการเลือกเช่นนี้จะทำให้ได้ edge ที่มีขีดจำกัดน้อย ๆ มีจำนวนน้อยลงนั่นเอง กรณีเช่นนี้ต้องใช้การเลือกเส้นทาง augmenting path เป็นจำนวน $O(|E|·|V|)$ ครั้ง โดยที่แต่ละครั้งใช้เวลา $O(|E|)$ และด้วยการใช้ unweighted shortest-path algorithm จะทำให้ได้ขอบเขตของ running time เป็น $O(|E|^2|V|)$ ยังมีหนทางอื่น ๆ ในการปรับปรุงอัลกอริทึมนี้ด้วยการใช้โครงสร้างข้อมูลอื่น ๆ ที่ซับซ้อนมากขึ้น