تحليل مزيج من خوارزمية بحث النقر الجشع مع التعداد الجزئي لرؤوس الرسم البياني

يوم جيد.

في وقت فراغي قمت ببعض البحث.

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

يعرض العمود "الأكثر شهرة" في الجدول 1 أحجام الحد الأقصى للنقرات المعروفة حاليًا للرسومات البيانية المشار إليها. يعرض عمود "Greedy" الحد الأقصى لأحجام النقرات التي تم العثور عليها بواسطة خوارزمية الجشع. تعطي الخوارزمية الجشعة الجواب الصحيح فقط في 3 حالات من أصل 35.

ملاحظة - في كود البرنامج الذي تم تنفيذه ، تقوم الخوارزمية الجشعة باختيار قمة أعلى قيمة متجاورة. إذا تم العثور على العديد من القمم المتشابهة ، فسيتم تحديد أول رأس تم العثور عليه. سوف نسمي إجراء الخوارزمية الجشع Greedy (A) ، حيث A هو رقم المصفوفة (مصفوفة المجاورة) التي يتم تطبيق الخوارزمية عليها. قم بفهرسة المصفوفة الأولية كـ A0.

, : N , . m, m – . DelNotAdj(m).

Greedy(m). ( ) «1c-Greedy». , , 8 35.

. , DelNotAdj(m). 0, m. mx. Greedy(mx). ( ) «2-Greedy».

3- (3c-Greedy) C500.9 C1000.9 ω(C500.9)=57, ω(C1000.9)=66.

.

Pascal Greedy(A) O(n²), n – . n , 2- – $$$n!/(2!∙(n-2)!)=(n∙(n-1))/2≈n^2$.. $$$n!/(ω(G)!∙(n-ω(G))!)$, ω(G) – () . .

, , ? 1 , .

( 1). O(n), – ω 1 ω(G) – , ω_GR – , .

«Position» 1 . ꞷ(G) , . «» , .

«B» , 2- .

«*» , «», .. 2, 3 . ω. ω_GRCFG.

, , , , . .. , , , 2- .

«» , :

1. 0 «» . ω_GR.
2. «» m, m . m , . ωGR+1.
3. «» mn, m- n- 0. mn , n- m- . ω_GR+2.
4. 3-, 4-,…, y- ω_GR+3, ω_GR+4,…, ω_GR+y .
5. 0 — ω(G).

. «» «B» :

, , ω_GR. ω_GR+1 ω_GR, , K – .

«*» :

«» ω_GR, ω_GR+1, ω_GR+2,…, ω(G) . , , . , ω_GR.

: ω_GR, ω_GR+1, ω_GR+2,… , « » ( ω_GRCDE 1).

:

1. «» ω_GR+y,
ω_GR+y-1, , K – .

.

2. y- ω_GR+y, , .. ω_GR+y=ω_GR+y-1, , ω_GR+y ω(G) .

إذا كان ما سبق يكرر عمل شخص آخر ، فأنا لست على الرغم من ذلك ، فسأكون سعيدًا لرؤية الرابط. سأكون أكثر سعادة إذا تمكن شخص من الناحية النظرية من إثبات أو دحض الفرضيات المقترحة.