خوارزمية كارغر

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 88 صور
الموسوعة الحرة
رسم بياني واثنين من مقاطعه. الخط المنقط باللون الأحمر هو مقطع بثلاثة أضلاع متقاطعة. الخط المتقطع باللون الأخضر هو مقطع أدنى لهذا الرسم البياني، يتقاطع مع ضلعين فقط.

في علوم الحاسوب ونظرية الرسوم البيانية ، تُعد خوارزمية كارغر خوارزمية عشوائية لحساب القطع الأدنى للرسم البياني المتصل . وقد ابتكرها ديفيد كارغر ونُشرت لأول مرة في عام 1993. [ 1 ]

تعتمد فكرة الخوارزمية على مفهوم انكماش الحافة(u،v){\displaystyle (u,v)}في رسم بياني غير موجهجي=(V،هـ){\displaystyle G=(V,E)}بصورة غير رسمية، يؤدي انكماش الحافة إلى دمج العقد.u{\displaystyle u}وv{\displaystyle v}في واحد، مما يقلل العدد الإجمالي لعقد الرسم البياني بمقدار واحد. جميع الحواف الأخرى التي تربط إماu{\displaystyle u}أوv{\displaystyle v}تُعاد وصل الحواف بالعقدة المدمجة، مما يُنتج فعليًا رسمًا بيانيًا متعددًا . تقوم خوارزمية كارغر الأساسية بتقليص الحواف المختارة عشوائيًا بشكل متكرر حتى يتبقى عقدتان فقط؛ تمثل هاتان العقدتان قطعًا في الرسم البياني الأصلي. من خلال تكرار هذه الخوارزمية الأساسية عددًا كافيًا من المرات، يمكن إيجاد القطع الأدنى باحتمالية عالية .

مشكلة القطع الأدنى العالمي

قطع​(S،تي){\displaystyle (S,T)}في رسم بياني غير موجهجي=(V،هـ){\displaystyle G=(V,E)}هو تقسيم للرؤوسV{\displaystyle V}إلى مجموعتين غير فارغتين ومنفصلتينS∪تي=V{\displaystyle S\cup T=V}تتكون مجموعة القطع من الحواف{uv∈هـ:u∈S،v∈تي}{\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}}بين الجزأين. حجم (أو وزن ) القطع في الرسم البياني غير الموزون هو عدد عناصر مجموعة القطع، أي عدد الحواف بين الجزأين.

w(S،تي)=|{uv∈هـ:u∈S،v∈تي}|.{\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}

هناك2|V|{\displaystyle 2^{|V|}}طرق اختيار ما إذا كان كل رأس ينتمي إلىS{\displaystyle S}أو إلىتي{\displaystyle T}لكن اثنين من هذه الخيارات يجعلانS{\displaystyle S}أوتي{\displaystyle T}فارغة ولا تؤدي إلى تخفيضات. من بين الخيارات المتبقية، تبديل أدوارS{\displaystyle S}وتي{\displaystyle T}لا يغير ذلك من القطع، لذلك يتم احتساب كل قطع مرتين؛ وبالتالي، هناك2|V|-1-1{\displaystyle 2^{|V|-1}-1}القطع المتميزة. تكمن مشكلة القطع الأدنى في إيجاد أصغر قطع من بين هذه القطع.

بالنسبة للرسوم البيانية الموزونة ذات أوزان الحواف الموجبةw:هـ→R+{\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}}وزن القطع هو مجموع أوزان الحواف بين الرؤوس في كل جزء

w(S،تي)=∑uv∈هـ:u∈S،v∈تيw(uv)،{\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}

وهو ما يتفق مع التعريف غير المرجح لـw=1{\displaystyle w=1}.

يُطلق على القطع أحيانًا اسم "القطع الشامل" لتمييزه عن "s{\displaystyle s}-ت{\displaystyle t}"قطع" لزوج معين من الرؤوس، والذي يتضمن شرطًا إضافيًا هوs∈S{\displaystyle s\in S}وت∈تي{\displaystyle t\in T}كل تخفيض عالمي هوs{\displaystyle s}-ت{\displaystyle t}قطع لبعضs،ت∈V{\displaystyle s,t\in V}وبالتالي، يمكن حل مشكلة القطع الأدنى في وقت متعدد الحدود عن طريق التكرار على جميع خياراتs،ت∈V{\displaystyle s,t\in V}وحل الحد الأدنى الناتجs{\displaystyle s}-ت{\displaystyle t}تُستخدم نظرية القطع الأدنى للتدفق الأقصى وخوارزمية زمنية متعددة الحدود للتدفق الأقصى ، مثل خوارزمية الدفع وإعادة التسمية ، لحل مشكلة القطع ، على الرغم من أن هذا النهج ليس الأمثل. تشمل الخوارزميات الحتمية الأفضل لحل مشكلة القطع الأدنى العالمي خوارزمية ستوير-فاغنر ، والتي يبلغ زمن تشغيلها 10 ...يا(من+ن2سجل⁡ن){\displaystyle O(mn+n^{2}\log n)}[ 2 ]​

خوارزمية الانكماش

تتمثل العملية الأساسية لخوارزمية كارغر في شكل من أشكال انكماش الحواف . وتكون نتيجة انكماش الحافةهـ={u،v}{\displaystyle e=\{u,v\}}عقدة جديدةuv{\displaystyle uv}كل حافة{w،u}{\displaystyle \{w,u\}}أو{w،v}{\displaystyle \{w,v\}}لw∉{u،v}{\displaystyle w\notin \{u,v\}}يتم استبدال نقاط نهاية الحافة المنكمشة بحافة{w،uv}{\displaystyle \{w,uv\}}إلى العقدة الجديدة. وأخيرًا، العقد المنكمشة u{\displaystyle u}وv{\displaystyle v}تُزال جميع الحواف المتصلة بها. وعلى وجه الخصوص، لا يحتوي الرسم البياني الناتج على أي حلقات ذاتية. نتيجة انكماش الحافةهـ{\displaystyle e}يُشار إليه بـجي/هـ{\displaystyle G/e}.

يتم دمج الحافة المميزة في عقدة واحدة.

تقوم خوارزمية الانكماش بتقليص الحواف العشوائية في الرسم البياني بشكل متكرر، حتى يتبقى عقدتان فقط، وعند هذه النقطة لا يوجد سوى قطع واحد.

تتلخص الفكرة الأساسية للخوارزمية في أن احتمالية اختيار الحواف غير المقطوعة الدنيا عشوائيًا وفقدانها أثناء عملية الانكماش أكبر بكثير من احتمالية اختيار الحواف المقطوعة الدنيا، نظرًا لأن عدد الحواف المقطوعة الدنيا عادةً ما يكون أقل بكثير من عدد الحواف غير المقطوعة الدنيا. وبالتالي، من المعقول أن تبقى الحواف المقطوعة الدنيا سليمة بعد كل عملية انكماش، وأن تتمكن الخوارزمية من تحديدها بدقة.

تم تشغيل خوارزمية كارغر بنجاح على رسم بياني مكون من 10 رؤوس. يبلغ حجم القطع الأدنى 3.
عقد الإجراءات (جي=(V،هـ){\displaystyle G=(V,E)}): بينما|V|>2{\displaystyle |V|>2} يختارهـ∈هـ{\displaystyle e\in E}بشكل عشوائي منتظم جي←جي/هـ{\displaystyle G\leftarrow G/e}إعادة القطع الوحيدجي{\displaystyle G}

عند تمثيل الرسم البياني باستخدام قوائم التجاور أو مصفوفة التجاور ، يمكن تنفيذ عملية انكماش حافة واحدة بعدد خطي من التحديثات على بنية البيانات، ليصبح إجمالي وقت التشغيل 10 ...يا(|V|2){\displaystyle O(|V|^{2})}أو بدلاً من ذلك، يمكن اعتبار الإجراء بمثابة تنفيذ لخوارزمية كروسكال لإنشاء الشجرة الممتدة الدنيا في رسم بياني حيث تكون للحواف أوزان.w(هـأنا)=π(أنا){\displaystyle w(e_{i})=\pi (i)}وفقًا لتبديل عشوائيπ{\displaystyle \pi }يؤدي حذف أثقل حافة في هذه الشجرة إلى مكونين يصفان القطع. وبهذه الطريقة، يمكن تنفيذ إجراء الانكماش مثل خوارزمية كروسكال في وقتيا(|هـ|سجل⁡|هـ|){\displaystyle O(|E|\log |E|)}.

تتوافق خيارات الحواف العشوائية في خوارزمية كارجر مع تنفيذ خوارزمية كروسكال على رسم بياني ذي رتب حواف عشوائية حتى يتبقى مكونان فقط.

تستخدم أفضل التطبيقات المعروفةيا(|هـ|){\displaystyle O(|E|)}الزمان والمكان، أويا(|هـ|سجل⁡|هـ|){\displaystyle O(|E|\log |E|)}الوقت ويا(|V|){\displaystyle O(|V|)}المساحة، على التوالي. [ 1 ]

احتمالية نجاح خوارزمية الانكماش

في الرسم البيانيجي=(V،هـ){\displaystyle G=(V,E)}معن=|V|{\displaystyle n=|V|}بالنسبة للرؤوس، تُعيد خوارزمية الانكماش قطعًا أدنى باحتمالية صغيرة متعددة الحدود(ن2)-1{\displaystyle {\binom {n}{2}}^{-1}}تذكر أن كل رسم بياني يحتوي على2ن-1-1{\displaystyle 2^{n-1}-1}التخفيضات (بحسب المناقشة في القسم السابق)، والتي من بينها على الأكثر(ن2){\displaystyle {\tbinom {n}{2}}}يمكن أن تكون هذه القطع هي الحد الأدنى. لذلك، فإن احتمال نجاح هذه الخوارزمية أفضل بكثير من احتمال اختيار قطع عشوائي، والذي هو على الأكثر(ن2)2ن-1-1{\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}}.

على سبيل المثال، الرسم البياني للدورة علىن{\displaystyle n}الرؤوس لها بالضبط(ن2){\displaystyle {\binom {n}{2}}}الحد الأدنى للقطع، الذي يتم تحديده من خلال كل اختيار لحافتين. يجد إجراء الانكماش كلًا من هذه القطع باحتمالية متساوية.

ولتحديد الحد الأدنى لاحتمالية النجاح بشكل أدق، لنفترضج{\displaystyle C}تشير إلى حواف قطع أدنى محدد بحجمك{\displaystyle k}تُعيد خوارزمية الانكماشج{\displaystyle C}إذا لم تكن أي من الحواف العشوائية التي حذفتها الخوارزمية تنتمي إلى مجموعة القطعج{\displaystyle C}وعلى وجه الخصوص، يتجنب انكماش الحافة الأولج{\displaystyle C}، وهو ما يحدث باحتمالية1-ك/|هـ|{\displaystyle 1-k/|E|}الحد الأدنى من درجةجي{\displaystyle G}هو على الأقلك{\displaystyle k}(وإلا فإن وجود رأس ذي درجة دنيا سيؤدي إلى قطع أصغر حيث يحتوي أحد التقسيمين على الرأس ذي الدرجة الدنيا فقط)، لذلك|هـ|⩾نك/2{\displaystyle |E|\geqslant nk/2}وبالتالي، فإن احتمال أن تختار خوارزمية الانكماش حافة منج{\displaystyle C}يكون

ك|هـ|⩽كنك/2=2ن.{\displaystyle {\frac {k}{|E|}}\leqslant {\frac {k}{nk/2}}={\frac {2}{n}}.}

الاحتماليةصن{\displaystyle p_{n}}أن خوارزمية الانكماش علىن{\displaystyle n}يتجنب الرسم البياني ذو الرؤوسج{\displaystyle C}يلبي شرط التكرارصن⩾(1-2ن)صن-1{\displaystyle p_{n}\geqslant \left(1-{\frac {2}{n}}\right)p_{n-1}}، معص2=1{\displaystyle p_{2}=1}والتي يمكن توسيعها لتصبح

صن⩾∏أنا=0ن-3(1-2ن-أنا)=∏أنا=0ن-3ن-أنا-2ن-أنا=ن-2ن⋅ن-3ن-1⋅ن-4ن-2⋯35⋅24⋅13=(ن2)-1.{\displaystyle p_{n}\geqslant \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\prod _{i=0}^{n-3}{\frac {n-i-2}{n-i}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{3}}={\binom {n}{2}}^{-1}\,.}

تكرار خوارزمية الانكماش

عشر تكرارات لعملية الانقباض. التكرار الخامس يحدد أصغر حجم للقطع وهو 3.

من خلال تكرار خوارزمية الانكماشتي=(ن2)ln⁡ن{\displaystyle T={\binom {n}{2}}\ln n}في حالة الاختيارات العشوائية المستقلة وإعادة أصغر قطع، فإن احتمال عدم العثور على قطع أدنى هو

[1-(ن2)-1]تي≤1هـln⁡ن=1ن.{\displaystyle \left[1-{\binom {n}{2}}^{-1}\right]^{T}\leq {\frac {1}{e^{\ln n}}}={\frac {1}{n}}\,.}

إجمالي وقت التشغيل لـتي{\displaystyle T}تكرارات لرسم بياني معن{\displaystyle n}الرؤوس وم{\displaystyle m}الحواف هييا(تيم)=يا(ن2مسجل⁡ن){\displaystyle O(Tm)=O(n^{2}m\log n)}.

خوارزمية كارغر-شتاين

وقد حقق امتداد لخوارزمية كارغر، من ابتكار ديفيد كارغر وكليفورد شتاين، تحسناً بمقدار عشرة أضعاف. [ 3 ]

الفكرة الأساسية هي تنفيذ عملية الانكماش حتى يصل الرسم البياني إلىت{\displaystyle t}الرؤوس.

عقد الإجراءات (جي=(V،هـ){\displaystyle G=(V,E)}،ت{\displaystyle t}): بينما|V|>ت{\displaystyle |V|>t} يختارهـ∈هـ{\displaystyle e\in E}بشكل عشوائي منتظم جي←جي/هـ{\displaystyle G\leftarrow G/e}يعودجي{\displaystyle G}

الاحتماليةصن،ت{\displaystyle p_{n,t}}أن إجراء الانقباض هذا يتجنب قطعًا محددًاج{\displaystyle C}فين{\displaystyle n}الرسم البياني ذو الرؤوس هو

صن،ت≥∏أنا=0ن-ت-1(1-2ن-أنا)=(ت2)/(ن2).{\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}

هذا التعبير تقريبًات2/ن2{\displaystyle t^{2}/n^{2}}ويصبح أقل من12{\displaystyle {\frac {1}{2}}}حولت=ن/2{\displaystyle t=n/{\sqrt {2}}}. على وجه الخصوص، احتمال وجود حافة منج{\displaystyle C}يتقلص وينمو باتجاه النهاية. وهذا يحفز فكرة التحول إلى خوارزمية أبطأ بعد عدد معين من خطوات التقلص.

إجراء فاستمينكت (جي=(V،هـ){\displaystyle G=(V,E)}): لو|V|≤6{\displaystyle |V|\leq 6}: إرجاع العقد(جي{\displaystyle G}،2{\displaystyle 2}) آخر : ت←⌈1+|V|/2⌉{\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }جي1←{\displaystyle G_{1}\leftarrow }عقد(جي{\displaystyle G}،ت{\displaystyle t}) جي2←{\displaystyle G_{2}\leftarrow }عقد(جي{\displaystyle G}،ت{\displaystyle t}) إرجاع min{fastmincut(جي1{\displaystyle G_{1}}), fastmincut(جي2{\displaystyle G_{2}})}

تحليل

معامل الانكماشت{\displaystyle t}يتم اختيارها بحيث يكون لكل استدعاء للتعاقد احتمال نجاح لا يقل عن 1/2 (أي تجنب انكماش حافة من مجموعة قطع محددة)ج{\displaystyle C}يسمح هذا بنمذجة الجزء الناجح من شجرة الاستدعاء الذاتي كشجرة ثنائية عشوائية يتم توليدها بواسطة عملية غالتون-واتسون الحرجة ، وتحليلها وفقًا لذلك. [ 3 ]

الاحتماليةP(ن){\displaystyle P(n)}أن هذه الشجرة العشوائية من المكالمات الناجحة تحتوي على مسار طويل بما يكفي للوصول إلى قاعدة الاستدعاء الذاتي والعثور علىج{\displaystyle C}يتم تحديدها بواسطة علاقة التكرار

P(ن)=1-(1-12P(⌈1+ن2⌉))2{\displaystyle P(n)=1-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}}

مع الحلP(ن)=Ω(1سجل⁡ن){\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)}مدة تشغيل برنامج فاست مينكت مرضية.

تي(ن)=2تي(⌈1+ن2⌉)+يا(ن2){\displaystyle T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}

مع الحلتي(ن)=يا(ن2سجل⁡ن){\displaystyle T(n)=O(n^{2}\log n)}لتحقيق احتمال الخطأيا(1/ن){\displaystyle O(1/n)}يمكن تكرار الخوارزميةيا(سجل⁡ن/P(ن)){\displaystyle O(\log n/P(n))}مرات، ليصبح إجمالي وقت التشغيلتي(ن)⋅سجل⁡نP(ن)=يا(ن2سجل3⁡ن){\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)}يمثل هذا تحسناً بمقدار عشرة أضعاف مقارنة بالخوارزمية الأصلية لكارجر. [ 3 ]

تحسينات مستهدفة

لتحديد القطع الأدنى، يجب لمس كل حافة في الرسم البياني مرة واحدة على الأقل، وهو ماΘ(ن2){\displaystyle \Theta (n^{2})}الوقت في رسم بياني كثيف . تستغرق خوارزمية القطع الأدنى لكارغر-شتاين وقت التشغيل التالي:يا(ن2lnيا(1)⁡ن){\displaystyle O(n^{2}\ln ^{O(1)}n)}وهو قريب جدًا من ذلك.

مراجع

  1. 1 2 كارغر، ديفيد (1993). "القطع الدنيا العالمية في RNC وتداعيات أخرى لخوارزمية القطع الدنيا البسيطة" . وقائع الندوة السنوية الرابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة .
  2. ↑ ستوير، م.؛ فاغنر، ف. (1997). "خوارزمية بسيطة للقطع الأدنى" . مجلة ACM . 44 (4): 585. doi : 10.1145/263867.263872 . S2CID 15220291 . 
  3. 1 2 3 كارغر، ديفيد ر .؛ شتاين، كليفورد (1996). "نهج جديد لمسألة القطع الأدنى" (ملف PDF) . مجلة ACM . 43 (4): 601. doi : 10.1145/234533.234534 . S2CID 5385337 .