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

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

ประวัติ

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

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

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

นิยาม

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

กราฟความจุคงเหลิอ (residual capacity) เป็นกราฟที่ได้จาก ${\displaystyle c_{f}:V\times V\to R^{+}}$ นิยามโดย

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

กราฟความจุคงเหลิอ คือกราฟ ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$ ที่มี

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

วิถีแต่งเติม (augmenting path) คือวิถีจาก ${\displaystyle s-t}$ ภายในกราฟความจุคงเหลิอ ${\displaystyle G_{f}}$

ให้ ${\displaystyle \operatorname {dist} (v)}$ แทนวิถีสั้นสุดจาก ${\displaystyle s}$ ไป ${\displaystyle v}$ ในกราฟ ${\displaystyle G_{f}}$

จะได้ว่า กราฟระดับ (level graph) ของ ${\displaystyle G_{f}}$ คือกราฟ ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$ ที่มี

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

กระแสจำกัดการไหล คือกระแสจาก ${\displaystyle s}$ ไป ${\displaystyle t}$ ${\displaystyle f}$ ซึ่งทำให้ ${\displaystyle G'=(V,E_{L}',s,t)}$ มี ${\displaystyle E_{L}'=\{(u,v):f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$และไม่มีวิถี ${\displaystyle s-t}$

ขั้นตอนวิธี

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

อินพุต : เน็ตเวิร์ก ${\displaystyle G=((V,E),c,s,t)}$

เอาต์พุต : กระแส ${\displaystyle s-t}$ ที่มีค่ากระแสสูงสุด ${\displaystyle f}$

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

วิเคราะห์

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

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

กรณีพิเศษ

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

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

ตัวอย่าง

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

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

ดูเพิ่ม

• ขั้นตอนวิธีของฟอร์ด-เฟอลเกอสัน
• ขั้นตอนวิธีของเอ็ดมอนด์-คาป

เชิงอรรถ

1. หมายถึงกราฟย่อยที่เกิดจากการลบวิถีที่อิ่มตัวทั้งหมด (วิถี ${\displaystyle (u,v)}$ โดย ${\displaystyle f'(u,v)=c_{f}|_{E_{L}}(u,v)}$) ไม่มีวิถีใด ๆ จาก ${\displaystyle s}$ ถึง ${\displaystyle t}$ กล่าวอีกนัยหนึ่งคือ การปิดกั้นการไหล นั้นทุกเส้นทางที่เป็นไปได้จาก ${\displaystyle s}$ ถึง ${\displaystyle t}$ มีวิถีอิ่มตัว
2. การค้นหาการปิดกั้นการไหลสามารถทำได้ใน ${\displaystyle 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. (PDF). คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.
4. Tarjan 1983, p. 102.
5. Yefim Dinitz (2006). (PDF). ใน Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (บ.ก.). Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN . คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.
6. 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 (บ.ก.). (PDF). Springer. pp. 218–240. ISBN . คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2016-08-20. สืบค้นเมื่อ 2011-09-08.
• Tarjan, R. E. (1983). Data structures and network algorithms. Society for Industrial and Applied Mathematics. ISBN . . 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 .