ขั้นตอนวิธีของดีนิซ

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

ขั้นตอนวิธีของดีนิซ (อังกฤษ: Dinic's algorithm) เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด (อังกฤษ: Maximum flow) ในระบบเครือข่ายการไหล (อังกฤษ: Flow network) ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (อังกฤษ: Yefim Dinitz) นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป (อังกฤษ: Edmonds-Karp algorithm) ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง กราฟระดับ และ กระแสที่จำกัดการไหล มาใช้

นิยาม[แก้]

ให้ เป็นเน็ตเวิร์ก มีเส้นเชื่อมจาก ไป โดยอนุญาตให้กระแสไหลผ่านได้ และมีกระแสไหลผ่านแล้ว

กราฟความจุคงเหลิอ (residual capacity) เป็นกราฟที่ได้จาก นิยามโดย
  1. เมื่อ ,
  2. :
  3. :
  4. นอกเหนือจากนี้
กราฟความจุคงเหลิอ คือกราฟ ที่มี
.
วิถีแต่งเติม (augmenting path) คือวิถีจาก ภายในกราฟความจุคงเหลิอ .
ให้ แทนวิถีสั้นสุดจาก ไป ในกราฟ
จะได้ว่า กราฟระดับ (level graph) ของ คือกราฟ ที่มี
.
กระแสจำกัดการไหล คือกระแสจาก ไป ซึ่งทำให้ มี และไม่มีวิถี

ขั้นตอนวิธี[แก้]

ขั้นตอนวิธีของดีนิซ

อินพุท: เน็ตเวิร์ค .
เอาต์พุต: กระแส ที่มีค่ากระแสสูงสุด
  1. กำหนด สำหรับทุก .
  2. สร้าง จาก ของ ถ้า ให้หยุดและคืนค่า .
  3. หากระแสจำกัดการไหล ใน .
  4. ขยายกระแส ด้วย จากนั้นกลับไปทำขั้นตอนที่ 2

วิเคราะห์[แก้]

จะเห็นได้ว่าจำนวนของเส้นเชื่อมในทุก กระแสจำกัดการไหล จะเพิ่มขึ้นอย่างน้อยที่ละ 1 ในการวน 1 รอบ และจะเพิ่มจนมีค่าไม่เกิน โดย เป็นจำนวนปมทั้งหมดในเน็ตเวิร์ค กราฟระดับ สามารถสร้างได้จาก การค้นตามแนวกว้าง ในเวลา โดย เป็นจำนวนเส้นเชื่อม และกระแสจำกัดการไหลในทุก ๆ กราฟระดับ จะสามารถหาได้ภายในเวลา ดังนั้นขั้นตอนวิธีของดีนิซจึงใช้เวลาในการทำงานเป็น

นอกจากนี้ยังสามารถทำให้ขั้นตอนวิธีของดีนิซมีประสิทธิภาพเพิ่มขึ้นด้วยการใช้โครงสร้างข้อมูลที่เรียกว่า ต้นไม้พลวัต (dynamic trees) ซึ่งจะทำให้เวลาการหากระแสจำกัดการไหลลดลงเป็น ทำให้ขั้นตอนวิธีโดยรวมใช้ทำงานเพียง

ตัวอย่าง[แก้]

ให้ G เป็นเน็ตเวิร์คเริ่มต้น ซึ่งแต่ละเส้นเชื่อมจะมีขนาดของกระแสและความจุ เป็นกราฟระดับ ปมที่มีเลขเป็นสีแดงคือค่าของ และวิถีสีน้ำเงินคือกระแสจำกัดการไหล

1. Dinic algorithm G1.svg Dinic algorithm Gf1.svg Dinic algorithm GL1.svg

กระแสจำกัดการไหลได้แก่

  1. ด้วยกระแสขนาด 4 หน่วย
  2. ด้วยกระแสขนาด 6 หน่วย และ
  3. ด้วยกระแสขนาด 4 หน่วย

ดังนั้นกระแสจำกัดการไหลมีทั้งหมด 14 หน่วย และ กระแส ทีค่าเท่ากับ 14 หมายเหตุ จะเห็นว่าทุก ๆ วิถีแต่งเติม ในกระแสจำกัดการไหลจะมี 3 เส้นเชื่อม

2. Dinic algorithm G2.svg Dinic algorithm Gf2.svg Dinic algorithm GL2.svg

กระแสจำกัดการไหลได้แก่

  1. ด้วยกระแสขนาด 5 หน่วย

ดังนั้นกระแสจำกัดการไหลมีทั้งหมด 5 หน่วย และ กระแส ทีค่าเท่ากับ 14+5=19 หมายเหตุ จะเห็นว่าทุก ๆ วิถีแต่งเติม ในกระแสจำกัดการไหลจะมี 4 เส้นเชื่อม

3. Dinic algorithm G3.svg Dinic algorithm Gf3.svg Dinic algorithm GL3.svg

จะเห็นว่าในกราฟ ไม่มีวิถีที่จะไปถึง ได้แล้ว ขั้นตอนวิธีก็จะจบลงและคืนค่ากระแสที่มีค่าสูงสุดนั้นก็คือ 19 หมายเหตุ จะเห็นว่าจำนวนเส้นเชื่อมในวิถีแต่งเติมจะเพิ่มขึ้นอย่างน้อย 1 ในทุก ๆ ครั้งที่หากระแสจำกัดการไหล

ดูเพิ่ม[แก้]

บรรณานุกรม[แก้]

  • Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". ใน Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (บ.ก.). Theoretical Computer Science: Essays in Memory of [[Shimon Even]] (PDF). Springer. pp. 218–240. ISBN 978-3540328803. URL–wikilink conflict (help)CS1 maint: multiple names: editors list (link)
  • Tarjan, R. E. (1983). Data structures and network algorithms.CS1 maint: ref=harv (link)
  • B. H. Korte, Jens Vygen (2008). "8.4 Blocking Flows and Fujishige's Algorithm". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174–176. ISBN 978-3-540-71844-4.