Skip to content
กลับไปยังผลการค้นหา

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

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดความสูงของ source ให้เท่ากับจำนวนจุดยอด (vertices) และความสูงอื่นๆ ทั้งหมดให้เป็นศูนย์ ทำให้ขอบทั้งหมดที่ออกจาก source อิ่มตัว (saturate) เพื่อสร้าง preflow เริ่มต้น (มีปริมาณเกินที่โหนดข้างเคียง)

2

เลือกโหนดที่มีปริมาณเกิน (active node) ซ้ำๆ และทำการ push ปริมาณเกินไปยังเพื่อนบ้านที่มีความสูงต่ำกว่า หรือกำหนดป้ายโหนดใหม่ (relabel) เพื่อเพิ่มความสูง ใช้กลยุทธ์การเลือกที่มีประสิทธิภาพและการดำเนินการ discharge เพื่อลดจำนวนรอบให้น้อยที่สุด

3

ดำเนินการต่อไปจนกว่าจะไม่มีโหนดที่มีปริมาณเกินเหลืออยู่ ซึ่ง ณ จุดนั้น 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 อาจนำไปใช้งานได้ง่ายกว่าโดยมีประสิทธิภาพที่แข่งขันได้

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว