على الأرجح ، واجه الجميع حقيقة أنه كان عليهم مواجهة بعض المهام الصعبة ، والتي لا يمكن إيجاد حل لها ، ليس فقط على الفور - ولكن حتى بعد ساعات طويلة من العمل أو أيام عنيدة. اليوم سنتحدث عن إحدى فئات هذه المشاكل - NP-complete.
بشكل عام ، هل من الواقعي القيام بمثل هذه المهام في الحياة اليومية؟ في الواقع ، تنشأ في عدد كبير من الحالات: التوافقيات والرسوم البيانية والشبكات وتنفيذ الصيغ المنطقية والعمل مع الخرائط والتحميلات المثلى والخرائط ومشكلات التحسين المنفصلة وإيجاد أطول التسلسلات وإيجاد مبالغ متساوية والعديد من المشاكل المحددة! وهذه ليست قائمة كاملة.
يوجد تحت الخفض دليل غير رسمي - كيف تفهم أنه قد يكون لديك مشكلة NP أمامك وماذا تفعل إذا كان الأمر كذلك. اليوم نواجه هذه المسألة من الناحية العملية.
تأكد من أنها حقًا أمامك
كيف تعرف أنك تواجه مشكلة NP كاملة؟ أولاً ، إن أبسط طريقة للكشف هي البحث من خلال مشاكل NP الكاملة المعروفة بالفعل من أجل تحديد شيء مشابه ، فهناك العديد من هذه القوائم ، على سبيل المثال .
ثانيًا ، ضع في اعتبارك خصائص المهام التالية:
- نحتاج إلى اختيار حل يكون فيه n من العناصر من الفضاء exp (n)
- إذا كان لديك بالفعل حل للطول n من هذه المساحة ، فيمكن التحقق منه بسهولة (متعدد الحدود)
- (قد) يؤثر اختيار أحد عناصر الحل على اختيار جميع العناصر الأخرى (وليس بالضرورة جميعها).
- في أسوأ الحالات ، يمكن دائمًا تعداد الخيارات ، مع الأخذ في الاعتبار المساحة الأسية بأكملها بالتعداد البسيط.
- المعلمات n - طول الحل أو المساحة نفسها ليس لها قيمة ثابتة ، أي أننا لا نتحدث عن رقعة الشطرنج 8 × 8 الثابتة دائمًا ، ولكن عن الشكل العام لمسألة N-by-N.
قراءة المزيد عن خصائص مشاكل NP-كاملة هنا و هنا .
مثال على العمل في هذه القائمة
دعنا نعطي مثالاً بسيطًا على مشكلة تمت الموافقة عليها مؤخرًا على أنها NP كاملة!
بناء على مواد المقال. تحتاج إلى وضع N ملكات على لوحة بحجم N × N ، بشرط أن يتم بالفعل وضع K <= N على السبورة (صورة من المقالة العلمية الأصلية)
أولاً ، لاحظ أن مشكلة مشابهة جدًا للمربعات اللاتينية المقيدة جزئيًا NP قد اكتملت.
ثم ننتقل إلى القائمة:
- تحتاج إلى العثور على N ملكات من الفضاء exp (N) (= N ^ 2 * (N ^ 2-1) * ....).
- يتم فحص حل N queens بشكل تافه - لكل ملكة ، تحتاج إلى التحقق من الأقطار والخطوط الرأسية والأفقية.
- الإعداد يجعل اختيار عدد من الآخرين باطلاً - أي هناك تبعيات بين عناصر الحل (لا يمكنك ترتيب الملكات بشكل مستقل).
- هنا يمكنك حل المشكلة بالقوة الغاشمة للوحة تم اختيارها عشوائيًا في exp (N) - نضع الأول في الأول في الموضع (i ، j) ، والثاني على أي لوحة أخرى غير مشغولة ، وهكذا. التراجع مضمون لإيجاد حل.
- لا تحتوي المشكلة على معلمات ثابتة - أي أنها تمت صياغتها في شكل عام ومع نمو N ، يزداد التعقيد أيضًا.
لاحظ أن أحد العناصر الموجودة في القائمة يفشل إذا كان من المعروف دائمًا أن اللوحة نظيفة وأصبحت المهمة تافهة.
علاوة على ذلك ، إنه نهج عملي مشروط - إرشادي للكشف عن مشاكل NP الكاملة (مع جميع الإيجابيات والسلبيات).
خلط
المصدر
لماذا ، مع وجود مشاكل مماثلة في متناول اليد ، ليس من السهل أن نفهم رسميًا أننا نواجه مشكلة NP؟ نحن بحاجة حقًا إلى تسليط الضوء على مشكلة NP لمشكلتنا ، ثم سنعرف بالتأكيد أن مشكلتنا صعبة للغاية! وإذا كنا قادرين على محاكاته ، كما في القائمة أعلاه ، فهو مكتمل - أي على الأقل NP وليس أكثر من NP ، في الواقع ، "الأصعب بين مشاكل NP" (مثل بقية مشاكل NP الكاملة).
حسنًا ، هل نحتاجها؟ ليس حقًا ، إذا كنت واضحًا ، بعد كل الفحوصات ، أنك تتعامل مع مشكلة NP ، فأنت لست بحاجة إلى إثبات أي شيء ما لم تكن تكتب مقالًا علميًا.
وتحتاج إما (سنتحدث عن هذا أدناه):
- محاكاة مهمتك باستخدام الأنظمة التي تحل مثل هذه المهام ؛
- إيجاد حل يعمل بالسرعة الكافية في حالتك ؛
- إيجاد حل تقريبي يرضينا.
لا تستسلم!
أهم شيء هو تقييم الأبعاد والمعلمات والسيناريوهات الواقعية!
xkcd.com/287
على سبيل المثال ، أنت تعلم أنه على الرغم من حقيقة أن قيم المعلمات ليست ثابتة ، فإن الشرط N <100 لا يتم تنفيذه في جميع السيناريوهات العملية ، مما يعني أن التعداد الشرطي قد يكون حلاً حقيقيًا لك.
عليك أن تحدد بنفسك: ما هي القيم الحقيقية للمعلمات الممكنة والتي تأتي بالفعل في النظام ، ما هو التوزيع العام وميزات البيانات ، وما هو حقيقي وما هو غير ذلك؟ هل نحن بحاجة إلى الحل الأمثل؟ لنستعرض هذه النقاط.
توزيع بيانات الإدخال
أو على الرغم من حقيقة أنه ، في الحالة العامة ، يمكن أن تكون بيانات الإدخال موجودة ، ولكن مرة أخرى لمثال الملكات - عادة ما تكون ملكة واحدة ثابتة أو حتى لا شيء. هذا يعني أنه يمكنك استخدام حل بسيط للغاية في 90٪ من الوقت ولا تتصل إلا بحل معقد في الحالات القصوى.
مثال عندما تكون جميع التركيبات المعتادة بسيطة في المتوسط: مشكلة استكمال الملكات - نحن نعلم أن الاستدلال الشرطي DFS + يمكنه في معظم الحالات إيجاد حلول بسرعة كبيرة ، وفقط في المواقف غير القياسية جدًا يمكن أن يكون صعبًا للغاية.
فيما يلي مثال على كيفية تقييم حل مشكلة تبليط مكتملة للغاية خاصة بـ NP مقابل طريقة عامة لنمذجة فئة كاملة من هذه المشكلات باستخدام طرق البرمجة المنطقية:
(من المادة العلائقية بيانات التحليل للعوامل (Paramonov، سيرجي، فان ليوين، ماتيس، دي Raedt، لوك: التعميل البيانات العلائقية، آلة التعلم، وحجم 106))
أولا، وسرعة حل LTM-ك خاص وطريقة عامة تختلف اختلافا كبيرا. وبالتالي ، فإن حل هذا النوع من المشكلات فقط باستخدام الاستدلال يمكن أن يحل هذه المشكلة تمامًا.
ثانيًا ، من خلال التضحية بجودة المحلول ، أعطت طريقة التقريب العامة سرعة مماثلة جدًا.
الاستدلال والتقريب
الأداة الأخيرة والأقوى هي استخدام أنظمة نمذجة المشكلة كاملة NP مثل برمجة مجموعة الإجابات .
المزيد عن لغات البرمجة المنطقية.
على سبيل المثال ، سيبدو حل مشكلة وضع الملكة كما يلي:
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
بعد إجراء تجربة بسيطة لإيجاد حلول لعدد مختلف من الملكات N ، حصلنا على ما يلي: على طول المحور X - الملكات ، على طول Y - الوقت بالثانية لإيجاد حل:
نحن نرى أنه على الرغم من حقيقة أن نمو الوقت ليس من الواضح أنه متعدد الحدود (وهو أمر منطقي) ، فإننا نقوم بعمل جيد مع عدد كافٍ من الملكات وأحجام الألواح.
بعد ذلك ، إذا عرفنا أحجام اللوحة الحقيقية بالنسبة لنا ، فيمكننا أن نفهم كيف يكون هذا الحل الدقيق مقبولًا لنا في نظام حقيقي.
الاستنتاجات
دعنا نتصفح بإيجاز الأفكار الواردة من المقالة في شكل قائمة مرجعية
- حدد أن لديك بالفعل مشكلة NP.
- فهم ما هي قيم المعلمات الواقعية وتوزيع البيانات.
- حاول أن تكتب (الترتيب يعتمد على المطور و / أو المهمة):
- حل إرشادي دقيق (بناءً على تحليلنا) - هل سيكون سريعًا بما يكفي؟
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
