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

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

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

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

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

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

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

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


 วิถีแต่งเติม (augmenting path) คือวิถีจาก  ภายในกราฟความจุคงเหลิอ 

 ให้  แทนวิถีสั้นสุดจาก  ไป  ในกราฟ 
 จะได้ว่า กราฟระดับ (level graph) ของ  คือกราฟ  ที่มี


 กระแสจำกัดการไหล คือกระแสจาก  ไป   ซึ่งทำให้  มี และไม่มีวิถี  

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

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

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

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

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

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

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

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

 เชิงอรรถ 

 อ้างอิง 

 บรรณานุกรม 

  eISBN . .


หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:การไหลในเครือข่าย