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

ขั้นตอนวิธีของดีนิซ (แม่แบบ:Langx) เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด (แม่แบบ:Langx) ในระบบเครือข่ายการไหล (แม่แบบ:Langx) ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (แม่แบบ:Langx; แม่แบบ:Langx)^[1] นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป (แม่แบบ:Langx) ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน $O (V E^{2})$ แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ $O (V^{2} E)$ ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง กราฟระดับ และ กระแสที่จำกัดการไหล มาใช้

ประวัติ

เยฟิม ดีนิทซ์ คิดค้นขั้นตอนวิธีนี้เพื่อตอบโจทย์แบบฝึกหัดก่อนชั้นเรียนในการเรียนขั้นตอนวิธีของอเดลสัน-เวลสกี ในขณะนั้นเขาไม่รู้ข้อเท็จจริงพื้นฐานเกี่ยวกับขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน^[2]

ดีนิทซ์กล่าวว่าการประดิษฐ์ขั้นตอนวิธีของเขาเกิดขึ้นในเดือนมกราคม พ.ศ. 2512 และได้รับการตีพิมพ์ในปี พ.ศ. 2513 ในวารสาร แม่แบบ:Lang (Doklady Akademii Nauk SSSR ) ในปี พ.ศ. 2517 ชิมอน อีเวน (שמעון אבן) และ อลอน อีไต (אלון איתי , ซึ่งกำลังศึกษาปริญญาเอกในขณะนั้น) ที่สถาบันเทคโนโลยีอิสราเอลเทคนิออน (แม่แบบ:Lang - แม่แบบ:Lang) ในไฮฟา มีความสนใจและประทับใจกับขั้นตอนวิธีของดีนิทซ์ รวมถึงแนวคิดที่เกี่ยวข้องกับการปิดกั้นการไหลของอะเลคซันดร์ คาซานอฟ (แม่แบบ:Lang) อย่างไรก็ตาม มันยากสำหรับพวกเขาที่จะถอดรหัสเอกสารทั้งสองฉบับนี้ โดยแต่ละฉบับมีเพียงสี่หน้าเพื่อให้เป็นไปตามข้อจำกัดของวารสาร Doklady Akademii Nauk SSSR โดยไม่ท้อถอยหลังจากสามวันของความพยายามก็สามารถทำความเข้าใจเอกสารทั้งสองฉบับได้ ยกเว้นปัญหาการบำรุงรักษาเครือข่ายแบบชั้น ในอีกสองสามปีต่อมาอีเวน ได้บรรยายเกี่ยวกับ "ขั้นตอนวิธีของ Dinic" โดยออกเสียงชื่อผู้เขียนผิดในขณะที่เผยแพร่ให้เป็นที่รู้จัก อีเวนและอีไตมีส่วนร่วมในขั้นตอนวิธีนี้ด้วยการรวมการค้นหาในแนวกว้าง (BFS) และการค้นหาในแนวลึก (DFS) ซึ่งปัจจุบันเป็นวิธีที่นำเสนอขั้นตอนวิธีนี้โดยทั่วไป^[3]

เป็นเวลาประมาณ 10 ปีหลังจากที่ขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน ถูกประดิษฐ์ขึ้น ไม่มีใครรู้ว่ามันสามารถมีจุดสิ้นสุดในเวลาพหุนามในกรณีทั่วไปของความจุที่มีค่าขอบเป็นจำนวนอตรรกยะได้หรือไม่ สิ่งนี้ทำให้ไม่มีขั้นตอนวิธีเวลาพหุนามที่รู้จักสำหรับการแก้ปัญหาการไหลสูงสุดในกรณีทั่วไป ขั้นตอนวิธีของดีนิทซ์ และขั้นตอนวิธีของเอ็ดมอนด์-คาป (เผยแพร่ในปี พ.ศ. 2515) ทั้งสองแบบต่างแสดงให้เห็นว่าในขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน หากวิถีแต่งเติมแต่ละเส้นสั้นที่สุด ความยาวของวิถีแต่งเติมจะไม่มีการลดลงและขั้นตอนวิธีจะมีจุดสิ้นสุดเสมอ

นิยาม

ให้ $G = ((V, E), c, s, t)$ เป็นเน็ตเวิร์ก มีเส้นเชื่อมจาก $u$ ไป $v$ โดยอนุญาตให้กระแสไหลผ่านได้ $c (u, v)$ และมีกระแสไหลผ่านแล้ว $f (u, v)$

กราฟความจุคงเหลิอ (residual capacity) เป็นกราฟที่ได้จาก

c_{f} : V \times V \to R^{+}

นิยามโดย

เมื่อ $(u, v) \in E$ ,
: $c_{f} (u, v) = c (u, v) - f (u, v)$
: $c_{f} (v, u) = f (u, v)$
นอกเหนือจากนี้ $c_{f} (u, v) = 0$

กราฟความจุคงเหลิอ คือกราฟ

G_{f} = ((V, E_{f}), c_{f} |_{E_{f}}, s, t)

ที่มี

E_{f} = {(u, v) \in V \times V : c_{f} (u, v) > 0}

วิถีแต่งเติม (augmenting path) คือวิถีจาก

s - t

ภายในกราฟความจุคงเหลิอ

G_{f}

ให้

dist (v)

แทนวิถีสั้นสุดจาก

s

ไป

v

ในกราฟ

G_{f}

จะได้ว่า กราฟระดับ (level graph) ของ

G_{f}

คือกราฟ

G_{L} = (V, E_{L}, c_{f} |_{E_{L}}, s, t)

ที่มี

E_{L} = {(u, v) \in E_{f} : dist (v) = dist (u) + 1}

กระแสจำกัดการไหล คือกระแสจาก

s

ไป

t

f

ซึ่งทำให้

G^{'} = (V, {E_{L}}^{'}, s, t)

มี

{E_{L}}^{'} = {(u, v) : f (u, v) < c_{f} |_{E_{L}} (u, v)}

และไม่มีวิถี

s - t

แม่แบบ:Efn แม่แบบ:Sfn

ขั้นตอนวิธี

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

อินพุต : เน็ตเวิร์ก

G = ((V, E), c, s, t)

เอาต์พุต : กระแส

s - t

ที่มีค่ากระแสสูงสุด

f

กำหนด $f (e) = 0$ สำหรับทุก $e \in E$
สร้าง $G_{L}$ จาก $G_{f}$ ของ $G$ ถ้า $dist (t) = \infty$ ให้หยุดและคืนค่า $f$
หากระแสจำกัดการไหล $f^{'}$ ใน $G_{L}$
ขยายกระแส $f$ ด้วย $f^{'}$ จากนั้นกลับไปทำขั้นตอนที่ 2

วิเคราะห์

จะเห็นได้ว่าจำนวนของเส้นเชื่อมในทุก กระแสจำกัดการไหล จะเพิ่มขึ้นอย่างน้อยที่ละ 1 ในการวน 1 รอบ และจะเพิ่มจนมีค่าไม่เกิน $V - 1$ โดย $V$ เป็นจำนวนปมทั้งหมดในเน็ตเวิร์ก กราฟระดับ $G_{L}$ สามารถสร้างได้จาก การค้นตามแนวกว้าง ในเวลา $O (E)$ โดย $E$ เป็นจำนวนเส้นเชื่อม และกระแสจำกัดการไหลในทุก ๆ กราฟระดับ จะสามารถหาได้ภายในเวลา $O (V E)$ แม่แบบ:Efn ดังนั้นขั้นตอนวิธีของดีนิซจึงใช้เวลาในการทำงานเป็น $O (V^{2} E)$ ^[4]

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

กรณีพิเศษ

ในเน็ตเวิร์กที่มีความจุเอกลักษณ์ จะมีขอบเขตของเวลามากขึ้น แต่ละขั้นตอนการปิดกั้นการไหลสามารถพบได้ในเวลา $O (E)$ และสามารถแสดงให้เห็นว่าจำนวนเฟสไม่เกิน $O (\sqrt{E})$ และ $O (V^{2 / 3})$ ดังนั้นขั้นตอนวิธีจะทำงานในเวลา $O (\min {V^{2 / 3}, E^{1 / 2}} E)$ ^[5]

ในเน็ตเวิร์กที่เกิดจากปัญหาบบการจับคู่สองส่วน]] จำนวนเฟสจะถูกจำกัดด้วย $O (\sqrt{V})$ จึงนำไปสู่ขอบเขตเวลา $O (\sqrt{V} E)$ ขั้นตอนวิธีที่ได้นั้นเรียกอีกอย่างว่าขั้นตอนวิธีฮอปครอฟต์-คาป โดยทั่วไป ขอบเขตนี้มีไว้สำหรับเน็ตเวิร์กเอกลักษณ์ใด ๆ — เครือข่ายที่จุดยอดแต่ละจุด ยกเว้นต้นทางและปลายทาง อาจมีวิถีของความจุขาเข้าเดียว หรือวิถีความจุของขาออกเดียว และความจุอื่นทั้งหมดเป็นจำนวนเต็มใด ๆแม่แบบ:Sfn

ตัวอย่าง

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

	$G$	$G_{f}$	$G_{L}$
1.
	กระแสจำกัดการไหลได้แก่ ${s, 1, 3, t}$ ด้วยกระแสขนาด 4 หน่วย ${s, 1, 4, t}$ ด้วยกระแสขนาด 6 หน่วย และ ${s, 2, 4, t}$ ด้วยกระแสขนาด 4 หน่วย ดังนั้นกระแสจำกัดการไหลมีทั้งหมด 14 หน่วย และ กระแส $\| f \|$ ทีค่าเท่ากับ 14 หมายเหตุ จะเห็นว่าทุก ๆ วิถีแต่งเติม ในกระแสจำกัดการไหลจะมี 3 เส้นเชื่อม
2.
	กระแสจำกัดการไหลได้แก่ ${s, 2, 4, 3, t}$ ด้วยกระแสขนาด 5 หน่วย ดังนั้นกระแสจำกัดการไหลมีทั้งหมด 5 หน่วย และ กระแส $\| f \|$ ทีค่าเท่ากับ 14+5=19 หมายเหตุ จะเห็นว่าทุก ๆ วิถีแต่งเติม ในกระแสจำกัดการไหลจะมี 4 เส้นเชื่อม
3.
	จะเห็นว่าในกราฟ $G_{f}$ ไม่มีวิถีที่จะไปถึง $t$ ได้แล้ว ขั้นตอนวิธีก็จะจบลงและคืนค่ากระแสที่มีค่าสูงสุดนั้นก็คือ 19 หมายเหตุ จะเห็นว่าจำนวนเส้นเชื่อมในวิถีแต่งเติมจะเพิ่มขึ้นอย่างน้อย 1 ในทุก ๆ ครั้งที่หากระแสจำกัดการไหล