مشكلة التغطية القصوى

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

يتم تزويدك كمدخلات بعدة مجموعات وعدد${\displaystyle k}$قد تشترك المجموعات في بعض العناصر. يجب عليك اختيار أكثر من${\displaystyle k}$من هذه المجموعات بحيث يتم تغطية أكبر عدد ممكن من العناصر، أي أن اتحاد المجموعات المختارة له أكبر حجم ممكن.

بصورة رسمية، (بدون ترجيح) أقصى تغطية

مثال: رقم${\displaystyle k}$ومجموعة من المجموعات${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$.

الهدف: إيجاد مجموعة جزئية${\displaystyle S'\subseteq S}$من المجموعات، بحيث${\displaystyle \left|S'\right|\leq k}$وعدد العناصر المشمولة${\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}$يتم تحقيق أقصى قدر من الفائدة.

تُعتبر مشكلة التغطية القصوى من المسائل الصعبة من نوع NP ، ولا يمكن تقريبها ضمن${\displaystyle 1-{\frac {1}{e}}+o(1)\approx 0.632}$في ظل الافتراضات القياسية. تتطابق هذه النتيجة بشكل أساسي مع نسبة التقريب التي تحققها الخوارزمية الجشعة العامة المستخدمة لتعظيم الدوال شبه المعيارية مع قيد على عدد العناصر . ^{[ 1 ]}

يمكن صياغة مشكلة التغطية القصوى على النحو التالي كبرنامج خطي صحيح .

أقصى	${\displaystyle \sum _{e_{j}\in E}y_{j}}$	(تعظيم مجموع العناصر المغطاة)
رهناً بـ	${\displaystyle \sum {x_{i}}\leq k}$	(لا يزيد عن)${\displaystyle k}$(تم اختيار المجموعات)
	${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$	(لو${\displaystyle y_{j}>0}$ثم مجموعة واحدة على الأقل${\displaystyle e_{j}\in S_{i}}$(تم اختياره)
	${\displaystyle y_{j}\in \{0,1\}}$	(لو${\displaystyle y_{j}=1}$ثم${\displaystyle e_{j}}$(مشمول بالتغطية)
	${\displaystyle x_{i}\in \{0,1\}}$	(لو${\displaystyle x_{i}=1}$ثم${\displaystyle S_{i}}$(تم اختيارها للغلاف)

تختار الخوارزمية الجشعة لتحقيق أقصى تغطية المجموعات وفقًا لقاعدة واحدة: في كل مرحلة، يتم اختيار مجموعة تحتوي على أكبر عدد من العناصر غير المغطاة. ويمكن إثبات أن هذه الخوارزمية تحقق نسبة تقريبية قدرها${\displaystyle 1-{\frac {1}{e}}}$[ ^{2 ]} تُظهر نتائج التقريب اللوغاريتمي أن الخوارزمية الجشعة هي في الأساس أفضل خوارزمية تقريبية ممكنة في وقت متعدد الحدود لتحقيق أقصى تغطية، ما ^لم${\displaystyle P=NP}$[ ^{3 ]​}

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

يمكن تطبيق مشكلة التغطية القصوى على حالات حركة المرور على الطرق؛ ومن الأمثلة على ذلك اختيار مسارات الحافلات في شبكة النقل العام التي ينبغي تزويدها بأجهزة كشف الحفر لتحقيق أقصى تغطية، عندما يكون عدد أجهزة الاستشعار المتاحة محدودًا. تُعد هذه المشكلة امتدادًا معروفًا لمشكلة التغطية القصوى، وقد تناولها لأول مرة في الأدبيات كل من جوناد علي وفلاديمير ديو. ^{[ 4 ]}

في النسخة الموزونة، كل عنصر${\displaystyle e_{j}}$له وزن ${\displaystyle w(e_{j})}$تتمثل المهمة في إيجاد أقصى تغطية ذات وزن أقصى. النسخة الأساسية هي حالة خاصة عندما تكون جميع الأوزان${\displaystyle 1}$.

أقصى${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$(تعظيم المجموع المرجح للعناصر المغطاة).

رهناً بـ${\displaystyle \sum {x_{i}}\leq k}$؛ (لا يزيد عن${\displaystyle k}$(يتم اختيار المجموعات).

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$؛ (لو${\displaystyle y_{j}>0}$ثم مجموعة واحدة على الأقل${\displaystyle e_{j}\in S_{i}}$(يتم الاختيار).

${\displaystyle y_{j}\in \{0,1\}}$؛ (لو${\displaystyle y_{j}=1}$ثم${\displaystyle e_{j}}$(مشمول بالتغطية)

${\displaystyle x_{i}\in \{0,1\}}$(لو${\displaystyle x_{i}=1}$ثم${\displaystyle S_{i}}$(تم اختيارها للغلاف).

تختار الخوارزمية الجشعة للتغطية القصوى الموزونة في كل مرحلة مجموعة تحتوي على أكبر وزن للعناصر غير المغطاة. تحقق هذه الخوارزمية نسبة تقريبية قدرها${\displaystyle 1-{\frac {1}{e}}}$[ ^{1 ]​}

في النسخة ذات التغطية القصوى المحددة في الميزانية، لا يقتصر الأمر على أن كل عنصر${\displaystyle e_{j}}$لها وزن${\displaystyle w(e_{j})}$ولكن أيضاً كل مجموعة${\displaystyle S_{i}}$له تكلفة${\displaystyle c(S_{i})}$. بدلاً من${\displaystyle k}$يحد ذلك من عدد المجموعات التي تغطي الميزانية${\displaystyle B}$هذه الميزانية مُعطاة.${\displaystyle B}$يحد من التكلفة الإجمالية للتغطية التي يمكن اختيارها.

أقصى${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$(تعظيم المجموع المرجح للعناصر المغطاة).

رهناً بـ${\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B}$لا يمكن أن تتجاوز تكلفة المجموعات المختارة${\displaystyle B}$).

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$؛ (لو${\displaystyle y_{j}>0}$ثم مجموعة واحدة على الأقل${\displaystyle e_{j}\in S_{i}}$(يتم الاختيار).

${\displaystyle y_{j}\in \{0,1\}}$؛ (لو${\displaystyle y_{j}=1}$ثم${\displaystyle e_{j}}$(مشمول بالتغطية)

${\displaystyle x_{i}\in \{0,1\}}$(لو${\displaystyle x_{i}=1}$ثم${\displaystyle S_{i}}$(تم اختيارها للغلاف).

لن تُنتج الخوارزمية الجشعة حلولًا بضمان أداء. بمعنى آخر، قد يكون أسوأ أداء لهذه الخوارزمية بعيدًا جدًا عن الحل الأمثل. يتم توسيع خوارزمية التقريب بالطريقة التالية: أولًا، تعريف خوارزمية جشعة مُعدّلة، تقوم باختيار المجموعة${\displaystyle S_{i}}$التي تتمتع بأفضل نسبة بين العناصر غير المغطاة المرجحة والتكلفة. ثانياً، من بين أغطية العددية${\displaystyle 1,2,...,k-1}$ابحث عن أفضل تغطية تأمينية لا تتجاوز ميزانيتك. سمِّ هذه التغطية${\displaystyle H_{1}}$ثالثًا، ابحث عن جميع أغطية العددية${\displaystyle k}$التي لا تنتهك الميزانية. باستخدام هذه الأغطية من العددية${\displaystyle k}$كنقطة بداية، طبّق خوارزمية الجشع المعدّلة، مع الحفاظ على أفضل غطاء تم العثور عليه حتى الآن. سمِّ هذا الغطاء${\displaystyle H_{2}}$في نهاية العملية، ستكون أفضل تغطية تقريبية إما${\displaystyle H_{1}}$أو${\displaystyle H_{2}}$تحقق هذه الخوارزمية نسبة تقريب تبلغ${\displaystyle 1-{1 \over e}}$بالنسبة لقيم${\displaystyle k\geq 3}$هذه هي أفضل نسبة تقريب ممكنة ما لم${\displaystyle NP\subseteq DTIME(n^{O(\log \log n)})}$[ ^{5 ]​}

في نسخة التغطية القصوى المعممة، كل مجموعة${\displaystyle S_{i}}$له تكلفة${\displaystyle c(S_{i})}$، عنصر${\displaystyle e_{j}}$يختلف وزنها وتكلفتها حسب المجموعة التي تغطيها. أي، إذا${\displaystyle e_{j}}$يشملها الطقم${\displaystyle S_{i}}$وزن${\displaystyle e_{j}}$ يكون${\displaystyle w_{i}(e_{j})}$وتكلفته${\displaystyle c_{i}(e_{j})}$الميزانية${\displaystyle B}$تم تحديد التكلفة الإجمالية للحل.

أقصى${\displaystyle \sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}}$. (تعظيم المجموع المرجح للعناصر المغطاة في المجموعات التي يتم تغطيتها فيها).

رهناً بـ${\displaystyle \sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B}$لا يمكن أن تتجاوز تكلفة المجموعات المختارة${\displaystyle B}$).

${\displaystyle \sum _{i}y_{ij}\leq 1}$؛ (عنصر${\displaystyle e_{j}=1}$لا يمكن تغطيتها إلا بمجموعة واحدة على الأكثر).

${\displaystyle \sum _{S_{i}}x_{i}\geq y_{ij}}$؛ (لو${\displaystyle y_{j}>0}$ثم مجموعة واحدة على الأقل${\displaystyle e_{j}\in S_{i}}$(يتم الاختيار).

${\displaystyle y_{ij}\in \{0,1\}}$؛ (لو${\displaystyle y_{ij}=1}$ثم${\displaystyle e_{j}}$يشملها الطقم${\displaystyle S_{i}}$)

${\displaystyle x_{i}\in \{0,1\}}$(لو${\displaystyle x_{i}=1}$ثم${\displaystyle S_{i}}$(تم اختيارها للغلاف).

• تتمثل مشكلة تغطية المجموعات في تغطية جميع العناصر بأقل عدد ممكن من المجموعات.

• فازيراني، فيجاي ف. (2001). خوارزميات التقريب . سبرينغر-فيرلاغ. رقم ISBN 978-3-540-65367-7.