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

ขั้นตอนวิธีของดีนิซ (Dinic's algorithm) เป็นขั้นตอนวิธีสำหรับการแก้ปัญหาการไหลมากสุด ( Maximum flow) ในระบบเครือข่ายการไหล ( Flow network) ถูกคิดขึ้นโดยเยฟิม ดีนิทซ์ (יפים (חיים) א 'דיניץ; Yefim (Chaim) A. Dinitz) นักวิทยาศาสตร์คอมพิวเตอร์ชาวยิว (อดีตเป็นชาวรัสเซีย) ในปี ค.ศ. 1970 ขั้นตอนวิธีนี้จะใกล้เคียงกับขั้นตอนวิธีของเอ็ดมอนด์-คาป (Edmonds-Karp algorithm) ซึ่งใช้หลักการหาวิถีสั้นสุดและมีอัตราการเติบโตเป็นของเวลาทำงาน O(VE^2) แต่ขั้นตอนวิธีของดีนิซจะมีอัตราการเติบโตที่น้อยกว่าคือ O(V^2E) ซึ่งเป็นผลมาจากการนำแนวคิดเรื่อง กราฟระดับ และ กระแสที่จำกัดการไหล มาใช้
== ประวัติ ==
เยฟิม ดีนิทซ์ คิดค้นขั้นตอนวิธีนี้เพื่อตอบโจทย์แบบฝึกหัดก่อนชั้นเรียนในการเรียนขั้นตอนวิธีของอเดลสัน-เวลสกี ในขณะนั้นเขาไม่รู้ข้อเท็จจริงพื้นฐานเกี่ยวกับขั้นตอนวิธีของฟอร์ด-เฟิลเกอร์สัน
ดีนิทซ์กล่าวว่าการประดิษฐ์ขั้นตอนวิธีของเขาเกิดขึ้นในเดือนมกราคม พ.ศ. 2512 และได้รับการตีพิมพ์ในปี พ.ศ. 2513 ในวารสาร Доклады Академии Наук СССР (Doklady Akademii Nauk SSSR&thinsp;) ในปี พ.ศ. 2517 ชิมอน อีเวน (שמעון אבן) และ อลอน อีไต (אלון איתי , ซึ่งกำลังศึกษาปริญญาเอกในขณะนั้น) ที่สถาบันเทคโนโลยีอิสราเอลเทคนิออน (מכון טכנולוגי לישראל - הטכניון) ในไฮฟา มีความสนใจและประทับใจกับขั้นตอนวิธีของดีนิทซ์ รวมถึงแนวคิดที่เกี่ยวข้องกับการปิดกั้นการไหลของอะเลคซันดร์ คาซานอฟ (Александр Викторович Карзанов) อย่างไรก็ตาม มันยากสำหรับพวกเขาที่จะถอดรหัสเอกสารทั้งสองฉบับนี้ โดยแต่ละฉบับมีเพียงสี่หน้าเพื่อให้เป็นไปตามข้อจำกัดของวารสาร Doklady Akademii Nauk SSSR โดยไม่ท้อถอยหลังจากสามวันของความพยายามก็สามารถทำความเข้าใจเอกสารทั้งสองฉบับได้ ยกเว้นปัญหาการบำรุงรักษาเครือข่ายแบบชั้น ในอีกสองสามปีต่อมาอีเวน ได้บรรยายเกี่ยวกับ "ขั้นตอนวิธีของ Dinic" โดยออกเสียงชื่อผู้เขียนผิดในขณะที่เผยแพร่ให้เป็นที่รู้จัก อีเวนและอีไตมีส่วนร่วมในขั้นตอนวิธีนี้ด้วยการรวมการค้นหาในแนวกว้าง (BFS) และการค้นหาในแนวลึก (DFS) ซึ่งปัจจุบันเป็นวิธีที่นำเสนอขั้นตอนวิธีนี้โดยทั่วไป
เป็นเวลาประมาณ 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) และไม่มีวิถี s-t 
== ขั้นตอนวิธี ==
ขั้นตอนวิธีของดีนิซ
อินพุต&thinsp;: เน็ตเวิร์ก G = ((V, E), c, s, t)
เอาต์พุต&thinsp;: กระแส 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)  ดังนั้นขั้นตอนวิธีของดีนิซจึงใช้เวลาในการทำงานเป็น O(V^2 E) 
นอกจากนี้ยังสามารถทำให้ขั้นตอนวิธีของดีนิซมีประสิทธิภาพเพิ่มขึ้นด้วยการใช้โครงสร้างข้อมูลที่เรียกว่า ต้นไม้พลวัต (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) 
ในเน็ตเวิร์กที่เกิดจากปัญหาบบการจับคู่สองส่วน]] จำนวนเฟสจะถูกจำกัดด้วย O(\sqrt{V}) จึงนำไปสู่ขอบเขตเวลา O(\sqrt{V} E) ขั้นตอนวิธีที่ได้นั้นเรียกอีกอย่างว่าขั้นตอนวิธีฮอปครอฟต์-คาป โดยทั่วไป ขอบเขตนี้มีไว้สำหรับเน็ตเวิร์กเอกลักษณ์ใด ๆ — เครือข่ายที่จุดยอดแต่ละจุด ยกเว้นต้นทางและปลายทาง อาจมีวิถีของความจุขาเข้าเดียว หรือวิถีความจุของขาออกเดียว และความจุอื่นทั้งหมดเป็นจำนวนเต็มใด&nbsp;ๆ
== ตัวอย่าง ==
ให้ G เป็นเน็ตเวิร์กเริ่มต้น ซึ่งแต่ละเส้นเชื่อมจะมีขนาดของกระแสและความจุ G_L เป็นกราฟระดับ ปมที่มีเลขเป็นสีแดงคือค่าของ \operatorname{dist}(v) และวิถีสีน้ำเงินคือกระแสจำกัดการไหล
== ดูเพิ่ม ==
ขั้นตอนวิธีของฟอร์ด-เฟอลเกอสัน
ขั้นตอนวิธีของเอ็ดมอนด์-คาป
== เชิงอรรถ ==
== อ้างอิง ==
== บรรณานุกรม ==
eISBN . .
ขั้นตอนวิธีกราฟ
การไหลในเครือข่าย