خوارزمية دينيك

خوارزمية دينيتش أو خوارزمية دينيتز هي خوارزمية متعددة الحدود قوية لحساب أقصى تدفق في شبكة تدفق ، وقد ابتكرها عالم الحاسوب الإسرائيلي (السوفيتي سابقًا) يفيم دينيتز عام 1970. ^[ 1 ^{] تعمل} الخوارزمية في${\displaystyle O(|V|^{2}|E|)}$وهي مشابهة لخوارزمية إدموندز-كارب ، التي تعمل في${\displaystyle O(|V||E|^{2})}$يعتمد هذا الأسلوب على استخدام أقصر المسارات الإضافية. وقد مكّن إدخال مفاهيم الرسم البياني للمستوى وتدفق الحجب خوارزمية دينيك من تحقيق هذا الأداء.

ابتكر دينيتز الخوارزمية في يناير 1969، عندما كان طالب ماجستير في مجموعة جورجي أديلسون-فيلسكي . وبعد بضعة عقود، تذكر قائلاً: ^{[ 2 ]}

في محاضرة أديلسون-فيلسكي عن الخوارزميات، اعتاد المحاضر أن يُعطي الطلاب المسألة التي ستُناقش في الجلسة التالية كتمرين. وقد تم ابتكار خوارزمية DA استجابةً لهذا التمرين. في ذلك الوقت، لم يكن المؤلف على دراية بالحقائق الأساسية المتعلقة بخوارزمية فورد-فولكرسون .

⋮ قد يكون للجهل أحيانًا مزاياه. على الأرجح، لم يكن ليتم اختراع تقنية DA آنذاك، لو كانت فكرة إمكانية إزالة تشبع الحواف معروفة للمؤلف.

في عام ١٩٧٠، نشر دينيتز وصفًا للخوارزمية في مجلة "دوكلادي أكاديميي ناوك إس إس إس آر" . وفي عام ١٩٧٤، أبدى شيمون إيفن وطالبه آنذاك في الدكتوراه، ألون إيتاي، في معهد التخنيون بحيفا، فضولًا كبيرًا وانبهارًا بخوارزمية دينيتز، فضلًا عن فكرة ألكسندر ف. كارزانوف المتعلقة بتدفق الحظر. إلا أنهما واجها صعوبة في فهم هاتين الورقتين البحثيتين، إذ اقتصرت كل منهما على أربع صفحات فقط التزامًا بقيود مجلة " دوكلادي أكاديميي ناوك إس إس إس آر" . لم يستسلم إيفن، وبعد ثلاثة أيام من الجهد، تمكن من فهم الورقتين باستثناء مسألة صيانة الشبكة متعددة الطبقات. وعلى مدى العامين التاليين، ألقى إيفن محاضرات حول "خوارزمية دينيتز"، مُخطئًا في نطق اسم المؤلف أثناء الترويج لها. كما ساهم إيفن وإيتاي في تطوير هذه الخوارزمية من خلال دمج خوارزميتي البحث في العرض أولًا (BFS) والبحث في العمق أولًا (DFS) ، وهي الطريقة الشائعة لعرض الخوارزمية اليوم. ^{[ ٢ ]}

لعشر سنوات تقريبًا بعد ابتكار خوارزمية فورد-فولكرسون، ظلّ من غير المعروف ما إذا كان بالإمكان جعلها تنتهي في زمن متعدد الحدود في الحالة العامة لسعات الحواف غير النسبية. وقد أدّى ذلك إلى عدم وجود أي خوارزمية معروفة تعمل في زمن متعدد الحدود لحلّ مشكلة التدفق الأقصى في الحالات العامة. أظهرت خوارزمية دينيتز وخوارزمية إدموندز-كارب (المنشورة عام ١٩٧٢) بشكل مستقل أنه في خوارزمية فورد-فولكرسون، إذا كان كل مسار مُعزِّز هو الأقصر، فإن طول المسارات المُعزِّزة لا يتناقص، وتنتهي الخوارزمية دائمًا.

يترك${\displaystyle G=((V,E),c,f,s,t)}$كن شبكة مع${\displaystyle c(u,v)}$و${\displaystyle f(u,v)}$سعة وتدفق الحافة${\displaystyle (u,v)}$، على التوالى.

السعة المتبقية هي عملية رسم خرائط${\displaystyle c_{f}\colon V\times V\to R^{+}}$يُعرَّف بأنه،

1. لو${\displaystyle (u,v)\in E}$،

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

2. لو${\displaystyle (v,u)\in E}$،

   ${\displaystyle c_{f}(u,v)=f(v,u)}$

3. ${\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\colon \;c_{f}(u,v)>0\}}$.

المسار المعزز هو${\displaystyle s}$–${\displaystyle t}$المسار في الرسم البياني المتبقي${\displaystyle G_{f}}$.

يُعرِّف${\displaystyle \operatorname {dist} (v)}$ليكون طول أقصر مسار من${\displaystyle s}$ل${\displaystyle v}$في${\displaystyle G_{f}}$ثم الرسم البياني للمستوى لـ${\displaystyle G_{f}}$الرسم البياني${\displaystyle G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)}$، أين

${\displaystyle E_{L}=\{(u,v)\in E_{f}\colon \;\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)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}}$لا يحتوي على${\displaystyle s}$–${\displaystyle t}$المسار. ^{[ ملاحظة 1 ] [ 3 ]}

خوارزمية دينيتش

المدخلات : شبكة${\displaystyle G=((V,E),c,s,t)}$.

الناتج :${\displaystyle s}$–${\displaystyle 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'}$ثم ارجع إلى الخطوة الثانية.

يمكن إثبات أن عدد الطبقات في كل تدفق حاجب يزداد بمقدار طبقة واحدة على الأقل في كل مرة، وبالتالي يوجد على الأكثر${\displaystyle |V|-1}$حجب التدفقات في الخوارزمية. لكل منها:

• الرسم البياني للمستوى${\displaystyle G_{L}}$يمكن بناؤها عن طريق البحث بالعرض أولاً في${\displaystyle O(E)}$وقت
• تدفق معيق في الرسم البياني للمستوى${\displaystyle G_{L}}$يمكن العثور عليها في${\displaystyle O(VE)}$الوقت ^{[ ملاحظة 2 ]}

مع إجمالي وقت التشغيل${\displaystyle O(E+VE)=O(VE)}$لكل طبقة. ونتيجة لذلك، فإن وقت تشغيل خوارزمية دينيك هو${\displaystyle O(V^{2}E)}$[ ^{2 ]​}

باستخدام بنية بيانات تسمى الأشجار الديناميكية ، يمكن تقليل وقت تشغيل عملية إيجاد تدفق معيق في كل مرحلة إلى${\displaystyle O(E\log V)}$وبالتالي يمكن تحسين وقت تشغيل خوارزمية دينيك إلى${\displaystyle O(VE\log V)}$.

فيما يلي محاكاة لخوارزمية دينيك. في الرسم البياني للمستويات${\displaystyle G_{L}}$الرؤوس التي تحمل تسميات باللون الأحمر هي القيم${\displaystyle \operatorname {dist} (v)}$تشكل المسارات باللون الأزرق تدفقًا يعيق الحركة.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	يتكون التدفق المعيق من ${\displaystyle \{s,1,3,t\}}$بأربع وحدات تدفق، ${\displaystyle \{s,1,4,t\}}$بست وحدات تدفق، و ${\displaystyle \{s,2,4,t\}}$بأربع وحدات تدفق. وبالتالي، فإن التدفق المعاق يبلغ 14 وحدة وقيمة التدفق${\displaystyle |f|}$14. لاحظ أن كل مسار معزز في التدفق المانع له 3 حواف.
2.
	يتكون التدفق المعيق من ${\displaystyle \{s,2,4,3,t\}}$بمعدل تدفق 5 وحدات. لذلك، يبلغ التدفق المعاق 5 وحدات وقيمة التدفق${\displaystyle |f|}$14 + 5 = 19. لاحظ أن كل مسار معزز يحتوي على 4 حواف.
3.
	منذ${\displaystyle t}$لا يمكن الوصول إليه في${\displaystyle G_{f}}$، تنتهي الخوارزمية وتعيد تدفقًا بقيمة قصوى تبلغ 19. لاحظ أنه في كل تدفق حجب، يزداد عدد الحواف في المسار المعزز بمقدار 1 على الأقل.

• خوارزمية فورد-فولكرسون
• مشكلة التدفق الأقصى

• دينيتز، يفيم (2006). "خوارزمية دينيتز: النسخة الأصلية ونسخة إيفن" . في: عوديد غولدريتش ؛ أرنولد ل. روزنبرغ ؛ آلان ل. سيلمان (محررون). علوم الحاسوب النظرية: مقالات في ذكرى شيمون إيفن . سلسلة محاضرات في علوم الحاسوب. المجلد  3895. سبرينغر. الصفحات 218-240 . doi : 10.1007/11685654_10 . ISBN  978-3-540-32880-3.
• كادار، إيلان؛ الباجلي، سيفان (18 أبريل 2019). خوارزمية دينيتز لإيجاد التدفق الأقصى في الشبكة . جامعة بن غوريون. مؤرشف من الأصل في 22 ديسمبر 2023.
• كورت، ب.هـ؛ فيجن، ينس (2008). "8.4 تدفقات الحجب وخوارزمية فوجيشيغي". التحسين التوافقي: النظرية والخوارزميات (الخوارزميات والتوافقية، 21) . سبرينغر برلين هايدلبرغ. ص 174-176 . ISBN  978-3-540-71844-4.
• تارجان، ر. إي. (1983). هياكل البيانات وخوارزميات الشبكة .