الضغط التكراري

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
الموسوعة الحرة

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

ابتكر ريد وسميث وفيتا [1] هذه التقنية لإثبات إمكانية حل مسألة اجتياز الدورات الفردية في زمن O (3kkmn ) ،  وذلك لرسم بياني ذي n رأسًا و m ضلعًا وعدد دورات فردية k . وتُعرف مسألة اجتياز الدورات الفردية بأنها إيجاد أصغر مجموعة رؤوس في رسم بياني تتضمن رأسًا واحدًا على الأقل من كل دورة فردية؛ وقد ظل تعقيدها المُعامل سؤالًا مفتوحًا لفترة طويلة. [ 2 ] [ 3 ] وقد أثبتت هذه التقنية لاحقًا فائدتها الكبيرة في إظهار نتائج قابلية المعالجة ذات المعاملات الثابتة . وتُعتبر الآن من التقنيات الأساسية في مجال الخوارزميات المُعاملة.

استُخدم الضغط التكراري بنجاح في العديد من المسائل، على سبيل المثال ، اجتياز الدورة الفردية (انظر أدناه) وتقسيم الحواف إلى قسمين ، ومجموعة رؤوس التغذية الراجعة ، وحذف رؤوس المجموعة. [ 4 ] كما استُخدم بنجاح في خوارزميات الوقت الأسي الدقيق للمجموعات المستقلة . [ 5 ]

تقنية

ينطبق الضغط التكراري، على سبيل المثال، على مسائل الرسوم البيانية ذات المعاملات التي تكون مدخلاتها رسمًا بيانيًا G = ( V , E ) وعددًا طبيعيًا k ، حيث تتمثل المسألة في اختبار وجود حل (مجموعة من الرؤوس) بحجم ≤ k . لنفترض أن المسألة لها الخصائص التالية:

  • وهي مغلقة تحت الرسوم البيانية الفرعية المستحثة : إذا كان هناك حل بحجم ≤ k موجود في رسم بياني معين، فإن حلاً بهذا الحجم أو أصغر موجود أيضًا في كل رسم بياني فرعي مستحث).
  • إذا كان X حلاً، و X' مجموعة من الرؤوس التي تحتوي على X ، فإن X' هو أيضاً حل.
  • توجد خوارزمية فرعية فعّالة، تقوم، عند إعطائها حلاً Y بحجم k  +  1، بتحديد ما إذا كان من الممكن ضغطه إلى حل بحجم k . أي أنها تجد حلاً بحجم k أو تحدد أنه لا يوجد حل من هذا القبيل.

إذا تحققت هذه الافتراضات، فيمكن حل المشكلة عن طريق إضافة الرؤوس واحدًا تلو الآخر إلى الرسم البياني الفرعي المستحث، وإيجاد حل الرسم البياني الفرعي المستحث، على النحو التالي:

  1. ابدأ برسم بياني جزئي ناتج عن مجموعة رؤوس S بحجم k ، وحل X يساوي S نفسها. (إذا لم يكن X حلاً لـ S ، فلا يوجد حل).
  2. طالما أن S ≠ V ، قم بتنفيذ الخطوات التالية:
    • ليكن v أي رأس من V \ S ، وأضف v إلى S
    • اختبر ما إذا كان حل ( k + 1) رأس Y = X ∪ {v } إلى S يمكن ضغطه إلى حل k رأس.
    • إذا تعذر ضغطها، فأوقف الخوارزمية: الرسم البياني المدخل ليس له حل k -vertex.
    • وإلا، فقم بتعيين X إلى الحل المضغوط الجديد واستمر في الحلقة.

تستدعي هذه الخوارزمية روتين الضغط الفرعي عددًا خطيًا من المرات. لذا، إذا كان بالإمكان حل صيغة الضغط في زمن معقول ذي معلمات ثابتة، أي f ( k )  · nc لثابت c ، فإن إجراء الضغط التكراري لحل المسألة بأكملها يستغرق زمنًا قدره f ( k ) · nc + 1. يمكن تطبيق التقنية نفسها لإيجاد مجموعات من الحواف لخصائص الرسم البياني المغلقة تحت الرسوم البيانية الفرعية (بدلاً من الرسوم البيانية الفرعية المستحثة)، أو لخصائص أخرى تتجاوز نظرية الرسوم البيانية. عندما تكون قيمة المعلمة k غير معروفة، يمكن إيجادها باستخدام مستوى خارجي من البحث الأسي أو البحث التسلسلي لاختيار القيمة المثلى لـ k ، حيث تعتمد كل خطوة من خطوات البحث على خوارزمية الضغط التكراري نفسها.   

التطبيقات

يُعرَّف اجتياز الدورة الفردية للرسم البياني بأنه مجموعة من الرؤوس التي يمكن حذفها لجعل الرسم البياني ثنائي الأجزاء. في ورقتهم البحثية الأصلية، قدّم ريد وآخرون خوارزمية ضغط تكرارية لتحديد ما إذا كان الرسم البياني يحتوي على اجتياز دورة فردية بحجم لا يتجاوز k ، وذلك في زمن O (3kkmn ) . لاحقًا، قدّم لوكشستانوف وسوراب وسيكدار خوارزمية أبسط، تستخدم أيضًا الضغط التكراري. [ 6 ] لضغط مجموعة الحذف Y بحجم k + 1 إلى مجموعة حذف X بحجم k ، تختبر خوارزميتهم جميع أقسام Y البالغ عددها 3k + 1 إلى ثلاث مجموعات فرعية: المجموعة الفرعية من Y التي تنتمي إلى مجموعة الحذف الجديدة، والمجموعتان الفرعيتان من Y اللتان تنتميان إلى جانبي الرسم البياني ثنائي الأجزاء المتبقي بعد حذف X. بمجرد اختيار هذه المجموعات الثلاث، يمكن العثور على الرؤوس المتبقية لمجموعة الحذف X (إن وجدت) منها عن طريق تطبيق خوارزمية الحد الأقصى للتدفق والحد الأدنى للقطع . 

يُعدّ غطاء الرؤوس مثالًا آخر يُمكن فيه استخدام الضغط التكراري. في مسألة غطاء الرؤوس، يُؤخذ الرسم البياني G  =  ( V , E ) والعدد الطبيعي k كمدخلات، ويتعين على الخوارزمية تحديد ما إذا كانت هناك مجموعة X من k رأسًا بحيث يكون كل ضلع متصلًا برأس في X. في صيغة الضغط من المسألة، يكون المدخل مجموعة Y من k  +  1 رأسًا متصلة بجميع أضلاع الرسم البياني، ويتعين على الخوارزمية إيجاد مجموعة X بحجم k بنفس الخاصية، إن وُجدت. إحدى طرق القيام بذلك هي اختبار جميع الخيارات البالغ عددها 2k + 1 لتحديد أي مجموعة فرعية من Y يجب إزالتها من الغطاء وإعادتها إلى الرسم البياني. لا يُمكن لهذا الاختيار أن ينجح إلا إذا لم يكن أي رأسين مُزالين متجاورين، ولكل اختيار من هذا القبيل، يجب على الروتين الفرعي تضمين جميع الرؤوس خارج Y المتصلة بضلع أصبح مكشوفًا نتيجةً لهذه الإزالة. إن استخدام هذا الروتين الفرعي في خوارزمية ضغط تكرارية يعطي خوارزمية بسيطة من النوع O (2 k n 2 )  لتغطية الرؤوس.

انظر أيضاً

  • التكويرنلة ، تقنية تصميم مختلفة للخوارزميات القابلة للمعالجة ذات المعلمات الثابتة

مراجع

  1. ↑ ريد، بروس ؛ سميث، كالي؛ فيتا، أدريان (2004)، "إيجاد المستعرضات الدورية الفردية"، رسائل بحوث العمليات ، 32 (4): 299-301 ، doi : 10.1016/j.orl.2003.10.009 ، MR 2057781 .
  2. ^ رولف نيدرماير ، دعوة إلى خوارزميات المعلمات الثابتة ، مطبعة جامعة أكسفورد، ص. 184، ردمك  9780198566076
  3. ^ سيجان ، ماريك. فومين، فيدور الخامس؛ كواليك، لوكاش. لوكشتانوف، دانيال؛ ماركس، دانيال؛ بيليبتشوك، مارسين؛ بيليبتشوك، ميشال؛ سوراب، ساكيت (2015)، خوارزميات ذات معلمات ، سبرينغر، ص. 555، ردمك  978-3-319-21274-6.
  4. ↑ غو، جيونغ؛ موزر، هانز؛ نيدرماير، رولف (2009)، "الضغط التكراري لحل مسائل التصغير الصعبة من نوع NP بدقة"، خوارزميات الشبكات الكبيرة والمعقدة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5515، سبرينغر، الصفحات 65-80 ، doi : 10.1007/978-3-642-02094-0_4 ، ISBN   978-3-642-02093-3.
  5. ↑ فومين، فيدور؛ جاسبرز، سيرج؛ كراتش، ديتر؛ ليدلوف، ماثيو؛ سوراب، ساكيت (2010)، "الضغط التكراري والخوارزميات الدقيقة"، علوم الحاسوب النظرية ، 411 (7): 1045-1053 ، doi : 10.1016/j.tcs.2009.11.012.
  6. ↑ لوكشتانوف، دانيال؛ سوراب، ساكيت؛ سيكدار، سومناث (2009)، "خوارزمية مُعَلمة أبسط لـ OCT"، ورشة العمل الدولية العشرون حول الخوارزميات التوافقية، IWOCA 2009، هراديك ناد مورافيتشي، جمهورية التشيك، 28 يونيو - 2 يوليو 2009، أوراق مختارة منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5874، سبرينغر، الصفحات 380-384 ، doi : 10.1007/978-3-642-10217-2_37 ، ISBN   978-3-642-10216-5.