อัลกอริทึม Push-Relabel
- ผู้เสนอ
- Andrew V. Goldberg and Robert E. Tarjan
- ปี
- 1988
- ประเภท
- algorithm
- กลุ่มวิธี
- Graph Algorithms
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
อัลกอริทึม Push-Relabel ซึ่งพัฒนาโดย Andrew V. Goldberg และ Robert E. Tarjan ในปี 1988 เป็นวิธีการที่มีประสิทธิภาพสูงในการคำนวณการไหลสูงสุดในเครือข่าย แตกต่างจากวิธีการแบบเส้นทางเสริม (augmenting path methods) อัลกอริทึมนี้จะรักษา preflow และใช้การดำเนินการ push และ relabel ในระดับท้องถิ่นและระดับโลกเพื่อขับเคลื่อนการไหลไปยัง sink ทำให้ได้ความซับซ้อนในกรณีที่แย่ที่สุด (worst-case complexity) ที่เหนือกว่า
แนวคิดเบื้องหลังวิธีการ
อัลกอริทึมจะรักษา 'ความสูง' หรือ 'ป้ายระยะทาง' (distance label) สำหรับแต่ละโหนด และใช้ preflow (ซึ่งโหนดสามารถมีปริมาณเกินความต้องการของ sink ได้ชั่วคราว) โดยจะผลักดันการไหลส่วนเกินจากโหนดที่มีป้ายสูงกว่าไปยังเพื่อนบ้านที่มีป้ายต่ำกว่า และกำหนดป้ายโหนดใหม่ (relabel) เพื่อสร้างเส้นทางไปยัง sink แนวคิดสำคัญคือการรักษาคุณสมบัติความสูง (height invariants) และการใช้โครงสร้างข้อมูลที่มีประสิทธิภาพ ทำให้อัลกอริทึมหลีกเลี่ยงการสำรวจกราฟทั้งหมดซ้ำๆ เหมือนที่วิธีการแบบเส้นทางเสริมต้องทำ อัลกอริทึมจะสิ้นสุดเมื่อการไหลส่วนเกินทั้งหมดไปถึง sink
ประวัติศาสตร์
Goldberg และ Tarjan ได้เผยแพร่อัลกอริทึม push-relabel ของพวกเขาในปี 1988 โดยนำเสนอแนวคิดที่แตกต่างออกไปอย่างสิ้นเชิงสำหรับการคำนวณการไหลสูงสุด อัลกอริทึมของพวกเขาให้ความซับซ้อนในกรณีที่แย่ที่สุดที่ O(V³) ซึ่งเป็นการปรับปรุงจาก O(VE²) ของ Edmonds-Karp ตลอดหลายทศวรรษต่อมา มีการพัฒนาอัลกอริทึมรูปแบบต่างๆ มากมาย รวมถึง gap heuristics (Goldberg และ Tarjan, 1990), กฎ highest-label และรูปแบบล่าสุดที่ให้ประสิทธิภาพเชิงประจักษ์ใกล้เคียงเชิงเส้นบนเครือข่ายจริง
ควรใช้เมื่อใด
ใช้อัลกอริทึม push-relabel สำหรับการคำนวณการไหลสูงสุดในเครือข่ายขนาดใหญ่ที่มีความหนาแน่นสูง (dense networks) ซึ่งวิธีการแบบเส้นทางเสริมจะไม่มีประสิทธิภาพ เหมาะอย่างยิ่งสำหรับเครือข่ายที่มีขอบหลายพันหรือหลายล้านเส้น ใช้เมื่อต้องการประสิทธิภาพเวลาพหุนามที่รับประกัน (guaranteed polynomial-time performance) และต้องการใช้ประโยชน์จากโครงสร้างข้อมูลสมัยใหม่ สำหรับเครือข่ายเบาบาง (sparse networks) หรือเพื่อการศึกษา วิธีการแบบเส้นทางเสริมอาจเข้าใจและนำไปใช้งานได้ง่ายกว่า
ข้อจำกัดและข้อควรพิจารณา
- ซับซ้อนกว่าในการทำความเข้าใจและนำไปใช้งานเมื่อเทียบกับวิธีการแบบเส้นทางเสริม
- ต้องจัดการโครงสร้างข้อมูลอย่างระมัดระวัง (discharge lists, gap heuristics) เพื่อประสิทธิภาพสูงสุด
- ความซับซ้อนในกรณีที่แย่ที่สุดยังคงสูงกว่าอัลกอริทึมเฉพาะทางบางตัวสำหรับกราฟประเภทพิเศษ
- ความเข้าใจกระบวนการแก้ปัญหาไม่ตรงไปตรงมาเท่ากับการใช้เส้นทางเสริม
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ความซับซ้อนในกรณีที่แย่ที่สุดที่เหนือกว่า: O(V³) หรือ O(V²√E) พร้อมกับ gap heuristic
- มีประสิทธิภาพสูงในทางปฏิบัติ โดยเฉพาะอย่างยิ่งสำหรับเครือข่ายขนาดใหญ่และหนาแน่น
- ความเป็นท้องถิ่นของการดำเนินการ (push/relabel) ช่วยให้มีประสิทธิภาพของแคชที่ดี
- สามารถนำไปใช้กับการประมวลผลแบบขนานและการกระจายได้
- มีรูปแบบการนำไปใช้งานหลายแบบสำหรับโครงสร้างปัญหาที่แตกต่างกัน
การประยุกต์ใช้
- การกำหนดเส้นทางเครือข่าย: การคำนวณปริมาณการส่งข้อมูลสูงสุดในเครือข่ายการสื่อสารขนาดใหญ่
- การประมวลผลภาพ: การใช้ max-flow สำหรับการแบ่งส่วนภาพและการสร้างภาพ (image matting)
- การเพิ่มประสิทธิภาพสายการบิน: การกำหนดปริมาณการไหลของผู้โดยสารสูงสุดผ่านเครือข่ายเส้นทางที่ซับซ้อน
- การวิเคราะห์โครงข่ายไฟฟ้า: การคำนวณความจุการส่งกำลังไฟฟ้าสูงสุดในเครือข่ายไฟฟ้า
- การจัดการห่วงโซ่อุปทาน: การเพิ่มประสิทธิภาพการไหลของผลิตภัณฑ์ผ่านเครือข่ายการกระจายหลายระดับ
- เครือข่ายชีวภาพ: การวิเคราะห์การไหลสูงสุดในเครือข่ายเมแทบอลิซึมและปฏิสัมพันธ์ของโปรตีน
วิธีการทำงาน
วิธีการทำงาน
กำหนดความสูงของ source ให้เท่ากับจำนวนจุดยอด (vertices) และความสูงอื่นๆ ทั้งหมดให้เป็นศูนย์ ทำให้ขอบทั้งหมดที่ออกจาก source อิ่มตัว (saturate) เพื่อสร้าง preflow เริ่มต้น (มีปริมาณเกินที่โหนดข้างเคียง)
เลือกโหนดที่มีปริมาณเกิน (active node) ซ้ำๆ และทำการ push ปริมาณเกินไปยังเพื่อนบ้านที่มีความสูงต่ำกว่า หรือกำหนดป้ายโหนดใหม่ (relabel) เพื่อเพิ่มความสูง ใช้กลยุทธ์การเลือกที่มีประสิทธิภาพและการดำเนินการ discharge เพื่อลดจำนวนรอบให้น้อยที่สุด
ดำเนินการต่อไปจนกว่าจะไม่มีโหนดที่มีปริมาณเกินเหลืออยู่ ซึ่ง ณ จุดนั้น preflow ทั้งหมดจะถูกแปลงเป็นการไหลสูงสุดจาก source ไปยัง sink
ข้อผิดพลาดที่พบบ่อย
- การนำการอัปเดตความสูงหรือการดำเนินการ push ไปใช้อย่างไม่ถูกต้อง ซึ่งนำไปสู่การไหลที่ไม่ใช่ค่าสูงสุด
- การละเลยการใช้ gap heuristics และการเลือกโหนดที่มีประสิทธิภาพ ส่งผลให้ประสิทธิภาพในทางปฏิบัติไม่ดี
- การไม่รักษาคุณสมบัติ preflow (ปริมาณเกินที่โหนดและข้อจำกัดความจุที่ขอบ) อย่างถูกต้อง
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่าง preflow และ flow?
Preflow อนุญาตให้โหนดเก็บการไหลส่วนเกินได้ชั่วคราว (ปริมาณการไหลเข้าลบปริมาณการไหลออกสามารถเป็นบวกได้) ในขณะที่การไหลที่แท้จริงจะต้องมีการอนุรักษ์ที่ทุกโหนด ยกเว้น source และ sink อัลกอริทึมจะสิ้นสุดเมื่อ preflow กลายเป็น flow ที่ถูกต้อง
วัตถุประสงค์ของฟังก์ชันความสูงคืออะไร?
ความสูงสร้างการวัดระยะทางเสมือน: การไหลสามารถผลักลงเท่านั้น (จากความสูงที่สูงกว่าไปยังความสูงที่ต่ำกว่า) ป้องกันวงจรที่ไม่จำเป็นและรับประกันการสิ้นสุด ความสูงจะเพิ่มขึ้นผ่านการ relabel เพื่อสร้างเส้นทางใหม่เมื่อจำเป็น
gap heuristic คืออะไรและทำไมจึงมีความสำคัญ?
gap heuristic ตรวจจับเมื่อไม่มีโหนดใดมีความสูงในช่วงที่กำหนด ซึ่งบ่งชี้ว่าโหนดบางโหนดไม่สามารถเข้าถึง sink ได้ โหนดเหล่านั้นและการไหลส่วนเกินของมันจะถูกระบุและประมวลผลอย่างรวดเร็ว ซึ่งช่วยปรับปรุงประสิทธิภาพในทางปฏิบัติได้อย่างมาก
Push-relabel เปรียบเทียบกับ Edmonds-Karp ในทางปฏิบัติอย่างไร?
Push-relabel มีความซับซ้อนในกรณีที่แย่ที่สุดที่ดีกว่า และโดยทั่วไปมีประสิทธิภาพเหนือกว่า Edmonds-Karp ในเครือข่ายขนาดใหญ่ แต่สำหรับเครือข่ายขนาดเล็กหรือกราฟเบาบาง Edmonds-Karp อาจนำไปใช้งานได้ง่ายกว่าโดยมีประสิทธิภาพที่แข่งขันได้
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วGoldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว