تغطية المشاكل

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

في علم التوافيق وعلوم الحاسوب ، تُعرف مسائل التغطية بأنها مسائل حسابية تتساءل عما إذا كان تركيب توافقي معين "يغطي" تركيبًا آخر، أو ما هو حجم التركيب اللازم لذلك. وتُصنف مسائل التغطية ضمن مسائل التصغير ، وعادةً ما تكون برامج خطية عددية صحيحة ، وتُسمى مسائلها الثنائية مسائل التعبئة .

أبرز الأمثلة على مشاكل التغطية هي مشكلة تغطية المجموعة ، والتي تعادل مشكلة مجموعة الضرب ، وحالاتها الخاصة، مشكلة تغطية الرؤوس ومشكلة تغطية الحواف .

تسمح مشاكل التغطية بتداخل العناصر الأولية للتغطية؛ وتسمى عملية تغطية شيء ما بعناصر أولية غير متداخلة بالتفكيك .

صياغة البرمجة الخطية العامة

في سياق البرمجة الخطية ، يمكن اعتبار أي برنامج خطي للتصغير بمثابة مسألة تغطية إذا كانت معاملات مصفوفة القيود ، ودالة الهدف، والطرف الأيمن غير سالبة. [ 1 ] بتعبير أدق، لننظر إلى برنامج الأعداد الصحيحة العام التالي :

تقليل∑أنا=1نجأناxأنا{\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}
رهناً بـ∑أنا=1نأجأناxأنا≥بج ل ج=1،...،م{\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m}
xأنا∈{0،1،2،...} ل أنا=1،...،ن{\displaystyle x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n}.

يُطلق على هذا النوع من البرامج الخطية الصحيحة اسم مشكلة التغطية إذاأجأنا،بج،جأنا≥0{\displaystyle a_{جي},b_{j},c_{i}\geq 0}للجميعأنا=1،...،ن{\displaystyle i=1,\dots ,n}وج=1،...،م{\displaystyle j=1,\dots ,m}.

الحدس: افترض أن لديكن{\displaystyle n}أنواع الكائنات وكل كائن من النوعأنا{\displaystyle i}وتترتب عليها تكلفة مرتبطة بـجأنا{\displaystyle c_{i}}الرقمxأنا{\displaystyle x_{i}}يشير إلى عدد الكائنات من النوعأنا{\displaystyle i}نشتري. إذا كانت القيودأx≥ب{\displaystyle A\mathbf {x} \geq \mathbf {b} }إذا كانوا راضين، يقال إنx{\displaystyle \mathbf {x} }هي تغطية (تعتمد البنى المغطاة على السياق التوافقي). وأخيرًا، الحل الأمثل لبرنامج البرمجة الخطية الصحيحة المذكور أعلاه هو تغطية بأقل تكلفة.

أنواع تغطية المشاكل

توجد أنواع مختلفة من مسائل التغطية في نظرية المخططات ، والهندسة الحسابية ، وغيرها؛ انظر تصنيف: مسائل التغطية . ويمكن العثور على نسخ أخرى ذات صلة بالمسألة في مجال الاحتمالات. [ 2 ]

تُعرف مسألة التغطية في رادو بأنها مسألة تتطلب تغطية مساحة مقدارها 1 من خلال سلسلة من المربعات ذات الحواف المتوازية. لأي مجموعة تحقق هذه الشروط، يتم اختيار مجموعة فرعية من هذه المربعات (مُشار إليها باللون الأحمر) بحيث لا يتداخل أي مربعين فيها، ويتم تعظيم المساحة الكلية. الهدف هو ترتيب المربعات بحيث تكون المساحة الكلية للمجموعة الفرعية المثلى في أدنى حد . تبلغ المساحة القصوى لكل مثال 1/4، ولكن هناك أمثلة أخرى بمساحات أقل قليلاً. [ 3 ] [ 4 ]
مسألة تغطية القرص ، والتي تسأل عن أصغر عدد حقيقير(ن){\displaystyle r(n)}بحيثن{\displaystyle n}أقراص نصف قطرهار(ن){\displaystyle r(n)}يمكن ترتيبها بطريقة تغطي القرص الصلب.

التغطية بشبكات بتري

في شبكات بتري ، تُعرَّف مسألة التغطية بأنها السؤال عما إذا كان، بالنسبة لعلامة معينة، يوجد تسلسل في الشبكة بحيث يمكن الوصول إلى علامة أكبر (أو مساوية) لها. ويعني مصطلح "أكبر" هنا أن جميع مكونات الشبكة لا تقل عن حجم مكونات العلامة المعطاة، وأن يكون أحدها على الأقل أكبر منها بشكل صحيح.

غطاء قوس قزح

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

  • توجد مجموعة J من n فترات ملونة على خط الأعداد الحقيقية ، ومجموعة P من النقاط على خط الأعداد الحقيقية.
  • تُسمى المجموعة الجزئية Q من J مجموعة قوس قزح إذا كانت تحتوي على فترة واحدة على الأكثر من كل لون.
  • تُسمى مجموعة الفترات J تغطية لـ P إذا كانت كل نقطة في P موجودة في فترة واحدة على الأقل من Q.
  • مشكلة تغطية قوس قزح هي مشكلة إيجاد مجموعة قوس قزح Q التي تمثل تغطية للمجموعة P.

المشكلة صعبة من نوع NP (عن طريق الاختزال من SAT الخطي ).

غطاء خالٍ من النزاعات

المفهوم الأكثر عمومية هو التغطية الخالية من التعارض . [ 6 ] في هذه المسألة:

  • هناك مجموعة O من m كائنات ، ورسم بياني للصراع G O على O.
  • تُسمى المجموعة الجزئية Q من O خالية من التعارض إذا كانت مجموعة مستقلة في G O ، أي أنه لا يوجد كائنان في Q متصلان بحافة في G O.
  • مجموعة قوس قزح هي مجموعة خالية من التعارض في الحالة الخاصة التي تتكون فيها G O من زمر منفصلة، ​​حيث تمثل كل زمرة لونًا.

تُعرف مشكلة تغطية المجموعة الخالية من التعارض بأنها إيجاد مجموعة فرعية خالية من التعارض من O تُغطي P. وقد أثبت كل من بانيك، وبانولان، ورامان، وساهلوت، وسوراب [ 7 ] ما يلي للحالة الخاصة التي يكون فيها للرسم البياني للتعارض عدد محدود من التشعبات :

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

مراجع

  1. ^ وزيراني، فيجاي ف. (2001). خوارزميات التقريب . سبرينغر-فيرلاغ. رقم ISBN 3-540-65367-8.112​
  2. ↑ دوك-بينكوفيتش، ي.، بن-غال، إ.، ورافيف، ت. (2022). "مشكلة جمع الاختبارات العشوائية: النماذج، ونهج الحلول الدقيقة والاستدلالية" (ملف PDF) . المجلة الأوروبية لبحوث العمليات، 299 (2022)، 945-959.{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط ) صيانة CS1: أسماء رقمية: قائمة المؤلفين ( رابط )
  3. ^ أجتاي، ميكلوس (1973)، “حل مشكلة ت. رادو”، نشرة الأكاديمية البولونية للعلوم، سلسلة علوم الرياضيات والفلك والفيزياء ، 21 : 61– 63، MR 0319053 
  4. ↑ بيريج، سيرجي؛ دوميتريسكو، أدريان؛ جيانغ، مينغهوي (2010)، "حول مسائل التغطية في رادو"، Algorithmica ، 57 (3): 538-561 ، doi : 10.1007/s00453-009-9298-z ، MR 2609053 إعلان أولي في مؤتمر SWAT 2008 ، doi : 10.1007/978-3-540-69903-3_27
  5. ↑ أركين، إستر م.؛ بانيك، أريترا؛ كارمي، باز؛ سيتوفسكي، غوي؛ كاتز، ماثيو ج.؛ ميتشل، جوزيف س.ب.؛ سيماكوف، مارينا (11-12-2018). "اختيار وتغطية النقاط الملونة" . الرياضيات التطبيقية المنفصلة . 250 : 75-86 . doi : 10.1016/j.dam.2018.05.011 . ISSN 0166-218X . 
  6. ↑ بانيك، أريترا؛ ساهلوت، فيبها؛ سوراب، ساكيت (2020-08-01). "خوارزميات تقريبية لمسائل التغطية الهندسية الخالية من التعارض" . الهندسة الحسابية . 89 101591. doi : 10.1016/j.comgeo.2019.101591 . ISSN 0925-7721 . S2CID 209959954 .  
  7. ^ بانيك، أريترا؛ بانولان، فهد؛ رامان، فينكاتيش؛ سهلوت، فيبها؛ سوراب ، ساكيت (2020-01-01). “التعقيد المحدد لمشاكل التغطية الهندسية التي لها صراعات”. خوارزمية . 82 (1): 1– 19. دوى : 10.1007/s00453-019-00600-w . ردمك 1432-0541 . S2CID 254027914 .