الفصل 10: المشاكل العصية على الحل والخوارزميات التقريبية
في الفصول السابقة، استكشفنا مجموعة واسعة من الخوارزميات لحل المشاكل بكفاءة. ومع ذلك، هناك العديد من المشاكل التي لا يوجد لها خوارزمية كفؤة معروفة. في هذا الفصل، سنناقش نظرية اكتمال NP، والتي توفر طريقة لإظهار أن مشكلة ما من المرجح أن تكون عصية على الحل، مما يعني أنه من المرجح ألا يكون هناك خوارزمية كفؤة لحلها. سنستكشف أيضًا تقنيات للتعامل مع مشاكل اكتمال NP، بما في ذلك الخوارزميات التقريبية وخوارزميات البحث المحلي.
فئتا P و NP
لفهم اكتمال NP، نحتاج أولاً إلى تعريف فئتين مهمتين من المشاكل: P و NP.
تتكون الفئة P (الوقت متعدد الحدود) من جميع مشاكل القرار التي يمكن حلها بواسطة خوارزمية تعمل في وقت متعدد الحدود. مشكلة القرار هي مشكلة لها إجابة نعم أو لا. على سبيل المثال، مشكلة تحديد ما إذا كان لدى رسم بياني دورة هاملتونية (دورة تزور كل رأس مرة واحدة فقط) هي مشكلة قرار. إذا كانت مشكلة القرار في P، فهناك خوارزمية يمكنها حل أي مثال من المشكلة في عدد من الخطوات محدود بدالة متعددة الحدود لحجم الإدخال.
تتكون الفئة NP (الوقت غير الحتمي متعدد الحدود) من جميع مشاكل القرار التي يمكن التحقق من حلها في وقت متعدد الحدود. على سبيل المثال، مشكلة دورة هاملتون موجودة في NP لأنه، بمجرد إعطاء رسم بياني ودورة هاملتونية مقترحة، يمكننا بسهولة التحقق في وقت متعدد الحدود ما إذا كانت الدورة المقترحة هي فعلاً دورة هاملتونية.
من الواضح أن P هي مجموعة فرعية من NP، لأن أي مشكلة يمكن حلها في وقت متعدد الحدود يمكن أيضًا التحقق منها في وقت متعدد الحدود. ومع ذلك، فإن السؤال عما إذا كان P = NP هو سؤال مفتوح. يعتقد معظم الخبراء أن P ≠ NP، مما يعني أن هناك مشاكل في NP ليست في P. ومع ذلك، إثبات ذلك سيكون اختراقًا كبيرًا في علم الحاسوب النظري.
اكتمال NP
مشكلة قرار X هي NP-كاملة إذا:
1هنا هو الترجمة العربية للملف:
. X موجود في NP، و 2. كل مشكلة في NP قابلة للتقليص إلى X في وقت متعدد.
مشكلة Y قابلة للتقليص إلى مشكلة X إذا كان أي مثال من Y يمكن تحويله إلى مثال من X في وقت متعدد، بحيث أن الإجابة على مثال Y هي "نعم" إذا وفقط إذا كانت الإجابة على المثال المحول من X هي "نعم".
تم تقديم مفهوم NP-كاملة بواسطة ستيفن كوك وليونيد ليفين بشكل مستقل في عام 1971. كانت المشكلة الأولى التي تم إثبات أنها NP-كاملة هي مشكلة إرضاء المنطق البولي (SAT). تم إثبات العديد من المشاكل الأخرى على أنها NP-كاملة عن طريق تقليص SAT أو مشاكل NP-كاملة أخرى معروفة إليها.
بعض المشاكل NP-كاملة المعروفة تشمل:
- مشكلة البائع المتجول (TSP): إعطاء مجموعة من المدن والمسافات بينها، ابحث عن أقصر جولة تزور كل مدينة مرة واحدة فقط.
- مشكلة الحقيبة: إعطاء مجموعة من العناصر مع أوزان وقيم، وحقيبة مع حد وزن، ابحث عن مجموعة الأشياء ذات القيمة الإجمالية القصوى التي تناسب في الحقيبة.
- مشكلة تلوين الرسم البياني: إعطاء رسم بياني، ابحث عن أقل عدد من الألوان المطلوبة لتلوين الرؤوس بحيث لا يكون لأي رأسين متجاورين نفس اللون.
أهمية NP-كاملة هي أنه إذا تم حل أي مشكلة NP-كاملة في وقت متعدد، فإنه يمكن حل جميع المشاكل في NP في وقت متعدد (أي P = NP). ومع ذلك، على الرغم من عقود من الجهود، لم يتم العثور على خوارزمية في وقت متعدد لأي مشكلة NP-كاملة. هذا يقترح (ولكن لا يثبت) أن المشاكل NP-كاملة صعبة بطبيعتها ومن غير المرجح أن تكون لها خوارزميات فعالة.
خوارزميات التقريب
نظرًا لأن المشاكل NP-كاملة يُعتقد أنها غير قابلة للحل، فإننا غالبًا ما نلجأ إلى خوارزميات التقريب عندما نواجه مثل هذه المشاكل في الممارسة العملية. خوارزمية التقريب هي خوارزمية تجد حلاً مضمونًا أن يكون ضمن عامل معين من الحل الأمثل.
على سبيل المثال، انظر إلى مشكلة الغطاء الرأسي: إعطاء رسم بياني، ابحث عن أصغرهنا ترجمة الملف إلى اللغة العربية مع الحفاظ على الرموز البرمجية دون ترجمتها:
أصغر مجموعة من الرؤوس بحيث أن كل حافة مرتبطة بواحد على الأقل من الرؤوس في المجموعة. هذه المشكلة هي NP-كاملة. ومع ذلك، هناك خوارزمية تقريب بسيطة تجد غطاء رؤوس لا يزيد عن ضعف حجم الغطاء الأمثل:
- قم بتهيئة مجموعة فارغة C.
- بينما هناك حواف غير مغطاة في الرسم البياني:
- اختر حافة غير مغطاة عشوائية (u, v).
- أضف كل من u و v إلى C.
- أزل جميع الحواف المرتبطة بـ u أو v من الرسم البياني.
- أعد C.
تعمل هذه الخوارزمية في وقت متعدد الحدود وتجد دائمًا غطاء رؤوس لا يزيد عن ضعف حجم الغطاء الأمثل. لرؤية ذلك، لاحظ أن في كل تكرار، تختار الخوارزمية رأسين لتغطية حافة، بينما يجب على الحل الأمثل اختيار واحد على الأقل من هذين الرأسين. وبالتالي، تختار الخوارزمية ما يصل إلى ضعف عدد الرؤوس مقارنة بالحل الأمثل.
غالبًا ما تُستخدم خوارزميات التقريب في الممارسة العملية لأنها توفر مستوى مضمون من الجودة مع العمل في وقت متعدد الحدود. نسبة التقريب لخوارزمية هي أسوأ حالة من نسبة حجم الحل الذي وجدته الخوارزمية إلى حجم الحل الأمثل.
خوارزميات البحث المحلي
نهج آخر للتعامل مع المشاكل NP-كاملة هو استخدام خوارزميات البحث المحلي. تبدأ خوارزمية البحث المحلي بحل أولي وتحسنه تدريجيًا من خلال إجراء تغييرات محلية صغيرة حتى لا يمكن إجراء مزيد من التحسينات.
على سبيل المثال، انظر إلى مشكلة البائع المتجول (TSP). تعمل خوارزمية بحث محلي بسيطة لـ TSP كما يلي:
- ابدأ بجولة عشوائية.
- بينما يمكن إجراء تحسينات:
- انظر في جميع الاحتمالات لتبديل مدينتين في الجولة الحالية.
- إذا أدى أي تبديل إلى تحسين طول الجولة، فقم بإجراء التبديل.
- أعد الجولة الحالية.
تبدأ هذه الخوارزمية بجولة عشوائية وتحسنها بشكل متكرر من خلال تبديل أزواج من المدن حتى لا يمكن إجراء مزيد من التحسينات من خلال التبديل. الجولة الناتجة هي حل محلي أمثل، مما يعني أنه لا يمكن تحسينههنا الترجمة العربية للملف:
البحث المحلي يمكن أن يجد حلولاً جيدة بسرعة ، ولكن ليس مضمونًا أن يجد الحد الأقصى العالمي. يمكن أن يعلق في الحد الأقصى المحلي البعيد عن الحد الأقصى العالمي. للتخفيف من هذا ، يمكن استخدام تقنيات مختلفة ، مثل:
- تشغيل البحث المحلي عدة مرات مع حلول أولية مختلفة.
- السماح للبحث المحلي بإجراء تحركات تؤدي مؤقتًا إلى إساءة الحل ، للمساعدة في الهروب من الحد الأقصى المحلي.
- استخدام هياكل جوار أكثر تعقيدًا تأخذ في الاعتبار تغييرات أكبر في الحل الحالي.
يُستخدم البحث المحلي على نطاق واسع في الممارسة لحل حالات كبيرة من المشاكل الكاملة NP ، غالبًا بالاقتران مع تقنيات أخرى مثل خوارزميات التقريب والحدسيات.
الخاتمة
توفر نظرية اكتمال NP إطارًا لفهم صعوبة المشاكل الحسابية المعينة. يُعتقد أن المشاكل الكاملة NP غير قابلة للحل ، مما يعني أنه من غير المرجح أن تكون لديها خوارزميات فعالة.
عندما نواجه مشاكل كاملة NP في الممارسة ، غالبًا ما نلجأ إلى خوارزميات التقريب والبحث المحلي. توفر خوارزميات التقريب مستوى مضمون من جودة الحل مع العمل في الوقت البولينومي. يمكن لخوارزميات البحث المحلي غالبًا العثور على حلول جيدة بسرعة من خلال تحسين حل أولي بشكل متكرر.
فهم نظرية اكتمال NP والتقنيات للتعامل مع المشاكل الكاملة NP أمر أساسي لأي شخص يعمل على مشاكل تحسين في العالم الحقيقي. بينما قد لا نتمكن من حل المشاكل الكاملة NP بشكل مثالي ، غالبًا ما نتمكن من العثور على حلول جيدة بما فيه الكفاية باستخدام خوارزميات التقريب وخوارزميات البحث المحلي.
مع استمرار نمو حجم وتعقيد المشاكل التي نواجهها ، ستزداد أهمية فهم اكتمال NP والتعامل معه. من خلال إتقان التقنيات الموضحة في هذا الفصل ، ستكون مجهزًا جيدًا لمواجهة بعض المشاكل الأكثر تحديًا وأهمية في علوم الكمبيوتر.Here is the Arabic translation of the provided Markdown file, with the code comments translated:
العلوم والما وراءها
مقدمة
هذا الملف هو مثال على كيفية استخدام Markdown لإنشاء محتوى منسق. Markdown هو لغة ترميز بسيطة تسمح لك بتنسيق النص بطريقة سهلة وقابلة للقراءة.
الأقسام
القسم الأول
هذا هو القسم الأول من المحتوى. يمكنك إضافة نص وتنسيقه باستخدام عناوين وقوائم وغير ذلك.
# هذا هو تعليق باللغة العربية
# يشرح ما يفعله هذا الكود
print("مرحبا بالعالم!")القسم الثاني
هذا هو القسم الثاني من المحتوى. يمكنك إضافة المزيد من النص والتنسيق هنا.
// هذا هو تعليق باللغة العربية
// يشرح ما يفعله هذا الكود
console.log("مرحبا بالعالم!");القسم الثالث
هذا هو القسم الثالث من المحتوى. يمكنك إضافة المزيد من النص والتنسيق هنا.
الخاتمة
هذا هو ملخص للمحتوى الذي تم تقديمه في هذا الملف. شكرًا لك على القراءة!