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

ขั้นตอนวิธีของดีนิซ (อังกฤษ: Dinic's algorithm) เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด (อังกฤษ: Maximum flow) ในระบบเครือข่ายการไหล (อังกฤษ: Flow network) ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (ฮีบรู: יפים (חיים) א 'דיניץ; อังกฤษ: Yefim (Chaim) A. Dinitz)^[1] นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป (อังกฤษ: Edmonds-Karp algorithm) ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน $O(VE^{2})$ แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ $O(V^{2}E)$ ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง กราฟระดับ และ กระแสที่จำกัดการไหล มาใช้

ประวัติ แก้

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

ดีนิทซ์กล่าวว่าการประดิษฐ์ขั้นตอนวิธีของเขาเกิดขึ้นในเดือนมกราคม พ.ศ. 2512 และได้รับการตีพิมพ์ในปี พ.ศ. 2513 ในวารสาร Доклады Академии Наук СССР (Doklady Akademii Nauk SSSR ) ในปี พ.ศ. 2517 ชิมอน อีเวน (שמעון אבן) และ อลอน อีไต (אלון איתי , ซึ่งกำลังศึกษาปริญญาเอกในขณะนั้น) ที่สถาบันเทคโนโลยีอิสราเอลเทคนิออน (מכון טכנולוגי לישראל - הטכניון) ในไฮฟา มีความสนใจและประทับใจกับขั้นตอนวิธีของดีนิทซ์ รวมถึงแนวคิดที่เกี่ยวข้องกับการปิดกั้นการไหลของอะเลคซันดร์ คาซานอฟ (Александр Викторович Карзанов) อย่างไรก็ตาม มันยากสำหรับพวกเขาที่จะถอดรหัสเอกสารทั้งสองฉบับนี้ โดยแต่ละฉบับมีเพียงสี่หน้าเพื่อให้เป็นไปตามข้อจำกัดของวารสาร 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}

ให้

\operatorname {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}:\operatorname {dist} (v)=\operatorname {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

^[a]^[4]

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

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

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

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

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

s-t

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

f

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

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

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

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

กรณีพิเศษ แก้

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

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

ตัวอย่าง แก้

ให้ G เป็นเน็ตเวิร์กเริ่มต้น ซึ่งแต่ละเส้นเชื่อมจะมีขนาดของกระแสและความจุ $G_{L}$ เป็นกราฟระดับ ปมที่มีเลขเป็นสีแดงคือค่าของ $\operatorname {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 ในทุก ๆ ครั้งที่หากระแสจำกัดการไหล

ดูเพิ่ม แก้

เชิงอรรถ แก้

↑ หมายถึงกราฟย่อยที่เกิดจากการลบวิถีที่อิ่มตัวทั้งหมด (วิถี $(u,v)$ โดย $f'(u,v)=c_{f}|_{E_{L}}(u,v)$ ) ไม่มีวิถีใด ๆ จาก $s$ ถึง $t$ กล่าวอีกนัยหนึ่งคือ การปิดกั้นการไหล นั้นทุกเส้นทางที่เป็นไปได้จาก $s$ ถึง $t$ มีวิถีอิ่มตัว
↑ การค้นหาการปิดกั้นการไหลสามารถทำได้ใน $O(E)$ รายวิถีโดยผ่านลำดับของการดำเนินการเดินหน้าและถอยกลับ (Advance and Retreat operations) ดูเพิ่มเติมที่ Blocking flows in unit-capacity graphs

อ้างอิง แก้

↑ Yefim Dinitz (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation" (PDF). Doklady Akademii Nauk SSSR. 11: 1277–1280.
↑ Ilan Kadar; Sivan Albagli (27 พฤศจิกายน 2009). "Dinitz's algorithm for finding a maximum flow in a network".
↑ Yefim Dinitz. "Dinitz's Algorithm: The Original Version and Even's Version" (PDF). คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.
↑ ^4.0 ^4.1 Tarjan 1983, p. 102.
↑ Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version" (PDF). ใน Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (บ.ก.). Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN 978-3-540-32880-3. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.
↑ Even, Shimon; Tarjan, R. Endre (1975). "Network Flow and Testing Graph Connectivity". SIAM Journal on Computing. 4 (4): 507–518. doi:10.1137/0204043. ISSN 0097-5397.

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

Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". ใน Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (บ.ก.). Theoretical Computer Science: Essays in Memory of Shimon Even (PDF). Springer. pp. 218–240. ISBN 978-3540328803. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.
Tarjan, R. E. (1983). Data structures and network algorithms. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-187-5. eISBN 978-1-61197-026-5. doi:10.1137/1.9781611970265.
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.

[4] หมายถึงกราฟย่อยที่เกิดจากการลบวิถีที่อิ่มตัวทั้งหมด (วิถี $(u,v)$ โดย $f'(u,v)=c_{f}|_{E_{L}}(u,v)$ ) ไม่มีวิถีใด ๆ จาก $s$ ถึง $t$ กล่าวอีกนัยหนึ่งคือ การปิดกั้นการไหล นั้นทุกเส้นทางที่เป็นไปได้จาก $s$ ถึง $t$ มีวิถีอิ่มตัว

[6] การค้นหาการปิดกั้นการไหลสามารถทำได้ใน $O(E)$ รายวิถีโดยผ่านลำดับของการดำเนินการเดินหน้าและถอยกลับ (Advance and Retreat operations) ดูเพิ่มเติมที่ Blocking flows in unit-capacity graphs

[1] Yefim Dinitz (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation" (PDF). Doklady Akademii Nauk SSSR. 11: 1277–1280.

[2] Ilan Kadar; Sivan Albagli (27 พฤศจิกายน 2009). "Dinitz's algorithm for finding a maximum flow in a network".

[3] Yefim Dinitz. "Dinitz's Algorithm: The Original Version and Even's Version" (PDF). คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.

[FOOTNOTETarjan1983102-5] 4.0 ^4.1 Tarjan 1983, p. 102.

[7] Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version" (PDF). ใน Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (บ.ก.). Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN 978-3-540-32880-3. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.

[Even1975-8] Even, Shimon; Tarjan, R. Endre (1975). "Network Flow and Testing Graph Connectivity". SIAM Journal on Computing. 4 (4): 507–518. doi:10.1137/0204043. ISSN 0097-5397.

[1]

[2]

[3]

[a]

[4]

[b]

[5]

[6]