ربما يكون العمل البحثي هو الجزء الأكثر إثارة للاهتمام في تدريبنا. الفكرة هي أن تجرب نفسك في الاتجاه الذي اخترته وأنت لا تزال في الجامعة. على سبيل المثال، غالبًا ما يذهب الطلاب من مجالات هندسة البرمجيات والتعلم الآلي لإجراء أبحاث في الشركات (بشكل رئيسي JetBrains أو Yandex، ولكن ليس فقط).
في هذه التدوينة سأتحدث عن مشروعي في علوم الحاسوب. كجزء من عملي، قمت بدراسة وتطبيق أساليب لحل واحدة من أشهر مشاكل NP-hard: مشكلة تغطية قمة الرأس.
في الوقت الحاضر، يتم تطوير نهج مثير للاهتمام لمشاكل NP-hard بسرعة كبيرة - خوارزميات ذات معلمات. سأحاول أن أطلعك على آخر المستجدات، وأخبرك ببعض الخوارزميات ذات المعلمات البسيطة وأصف إحدى الطرق القوية التي ساعدتني كثيرًا. لقد قدمت نتائجي في مسابقة تحدي PACE: وفقًا لنتائج الاختبارات المفتوحة، حصل الحل الخاص بي على المركز الثالث، وستُعرف النتائج النهائية في 1 يوليو.
معلومات عني
اسمي فاسيلي ألفيروف، وأنا الآن أنهي سنتي الثالثة في المدرسة العليا للاقتصاد بجامعة الأبحاث الوطنية - سانت بطرسبرغ. لقد كنت مهتمًا بالخوارزميات منذ أيام الدراسة، عندما درست في مدرسة موسكو رقم 179 وشاركت بنجاح في أولمبياد علوم الكمبيوتر.
عدد محدود من المتخصصين في الخوارزميات ذات المعلمات يدخلون إلى الشريط...
المثال مأخوذ من الكتاب
تخيل أنك حارس أمن بار في بلدة صغيرة. كل يوم جمعة، يأتي نصف المدينة إلى البار الخاص بك للاسترخاء، مما يسبب لك الكثير من المتاعب: تحتاج إلى طرد العملاء المشاغبين من الحانة لمنع المعارك. في النهاية، تشعر بالملل وتقرر اتخاذ الإجراءات الوقائية.
نظرًا لأن مدينتك صغيرة، فأنت تعرف بالضبط أي أزواج من الزبائن من المحتمل أن يتقاتلوا إذا انتهى بهم الأمر في الحانة معًا. هل لديك قائمة n الأشخاص الذين سيأتون إلى الحانة الليلة. عليك أن تقرر إبقاء بعض سكان البلدة خارج الحانة دون أن يدخل أي شخص في قتال. وفي الوقت نفسه، لا يريد رؤسائك خسارة الأرباح ولن يكونوا سعداء إذا لم تسمح بأكثر من ذلك k الناس.
لسوء الحظ، المشكلة التي تواجهك هي مشكلة NP-hard كلاسيكية. ربما تعرفها باسم أو كمشكلة تغطية قمة الرأس. بالنسبة لمثل هذه المشكلات، بشكل عام، لا توجد خوارزميات تعمل في وقت مقبول. على وجه الدقة، تقول الفرضية غير المثبتة والقوية جدًا ETH (فرضية الوقت الأسي) أن هذه المشكلة لا يمكن حلها في الوقت المناسب أي أنه لا يمكنك التفكير في أي شيء أفضل بشكل ملحوظ من البحث الكامل. على سبيل المثال، لنفترض أن شخصًا ما سيأتي إلى الحانة الخاصة بك ن = 1000 بشر. ثم سيكون البحث الكامل الخيارات الموجودة تقريبًا - مبلغ مجنون. لحسن الحظ، إدارتك أعطتك حدًا ك = 10، وبالتالي فإن عدد المجموعات التي تحتاج إلى التكرار فيها أقل بكثير: عدد المجموعات الفرعية المكونة من عشرة عناصر هو . هذا أفضل، لكنه لا يزال لن يتم حسابه في يوم واحد حتى على مجموعة قوية.
للتخلص من احتمالية حدوث قتال في هذا التكوين من العلاقات المتوترة بين زوار الحانة، عليك إبعاد بوب ودانيال وفيدور. ولا يوجد حل يتخلف فيه اثنان فقط عن الركب.
هل هذا يعني أن الوقت قد حان للاستسلام والسماح للجميع بالدخول؟ دعونا نفكر في الخيارات الأخرى. حسنًا، على سبيل المثال، لا يمكنك السماح فقط بدخول أولئك الذين من المحتمل أن يتقاتلوا مع عدد كبير جدًا من الأشخاص. إذا كان شخص ما يمكن أن يقاتل على الأقل مع ك + 1 شخص آخر، فمن المؤكد أنك لا تستطيع السماح له بالدخول - وإلا فسيتعين عليك إبعاد الجميع ك + 1 سكان البلدة، الذين يمكنه القتال معهم، الأمر الذي سيزعج القيادة بالتأكيد.
دعك تطرد كل ما تستطيع وفقًا لهذا المبدأ. ثم يمكن لأي شخص آخر القتال بما لا يزيد عن k الناس. طردهم k يا رجل، لا يمكنك منع شيء أكثر من ذلك الصراعات. وهذا يعني أنه إذا كان هناك أكثر من إذا كان الشخص متورطا في صراع واحد على الأقل، فمن المؤكد أنك لا تستطيع منعهم جميعا. نظرًا لأنك ستسمح بالتأكيد بدخول الأشخاص غير المنخرطين في النزاع تمامًا، فأنت بحاجة إلى المرور عبر جميع المجموعات الفرعية ذات الحجم العاشر من بين مائتي شخص. هناك تقريبا ، ويمكن بالفعل فرز هذا العدد من العمليات على المجموعة.
إذا كان بإمكانك أن تأخذ بأمان أفرادًا ليس لديهم صراع على الإطلاق، فماذا عن أولئك الذين يشاركون في صراع واحد فقط؟ في الواقع، يمكن أيضًا السماح لهم بالدخول عن طريق إغلاق الباب في وجه خصمهم. في الواقع، إذا كانت أليس في صراع مع بوب فقط، فإذا سمحنا لأليس بالخروج من الاثنين، فلن نخسر: ربما يكون لدى بوب صراعات أخرى، لكن أليس بالتأكيد لا تعاني منها. علاوة على ذلك، ليس من المنطقي بالنسبة لنا ألا نسمح لكلينا بالدخول. بعد هذه العمليات لم يعد هناك شيء الضيوف الذين لم يتم حل مصيرهم: لدينا فقط الصراعات، كل منها مع اثنين من المشاركين وكل منها يشارك في اثنين على الأقل. لذلك كل ما تبقى هو الفرز الخيارات، والتي يمكن اعتبارها بسهولة نصف يوم على جهاز كمبيوتر محمول.
في الواقع، مع التفكير البسيط يمكنك تحقيق ظروف أكثر جاذبية. لاحظ أننا نحتاج بالتأكيد إلى حل جميع النزاعات، أي من كل زوج متضارب، اختر شخصًا واحدًا على الأقل لن نسمح له بالدخول. لنأخذ في الاعتبار الخوارزمية التالية: خذ أي تعارض، حيث نزيل أحد المشاركين ونبدأ بشكل متكرر من الباقي، ثم نزيل الآخر ونبدأ أيضًا بشكل متكرر. نظرًا لأننا نطرد شخصًا ما في كل خطوة، فإن شجرة العودية لمثل هذه الخوارزمية هي شجرة ثنائية من العمق k، لذا تعمل الخوارزمية بشكل إجمالي حيث n هو عدد القمم، و m - عدد الأضلاع. في مثالنا، هذا حوالي عشرة ملايين، والتي يمكن حسابها في جزء من الثانية ليس فقط على جهاز كمبيوتر محمول، ولكن حتى على الهاتف المحمول.
المثال أعلاه هو مثال خوارزمية ذات معلمات. الخوارزميات ذات المعلمات هي خوارزميات تعمل في الوقت المناسب و (ك) بولي (ن)حيث p - متعدد الحدود، f هي وظيفة حسابية تعسفية، و k - بعض المعلمات، والتي من المحتمل جدًا أن تكون أصغر بكثير من حجم المشكلة.
كل المنطق قبل هذه الخوارزمية يعطي مثالا النواة هي إحدى التقنيات العامة لإنشاء خوارزميات ذات معلمات. Kernelization هو تقليل حجم المشكلة إلى قيمة محدودة بوظيفة المعلمة. غالبًا ما تسمى المشكلة الناتجة بالنواة. وهكذا، من خلال التفكير البسيط حول درجات القمم، حصلنا على نواة تربيعية لمسألة الغطاء الرأسي، والتي يتم تحديد معلماتها حسب حجم الإجابة. هناك إعدادات أخرى يمكنك اختيارها لهذه المهمة (مثل Vertex Cover Before LP)، ولكن هذا هو الإعداد الذي سنناقشه.
تحدي الوتيرة
منافسة (تحدي الخوارزميات ذات المعلمات والتجارب الحسابية) ولد في عام 2015 لإنشاء علاقة بين الخوارزميات ذات المعلمات والأساليب المستخدمة عمليًا لحل المشكلات الحسابية. تم تخصيص المسابقات الثلاث الأولى لإيجاد عرض شجرة الرسم البياني ()، البحث عن شجرة شتاينر () والبحث عن مجموعة من القمم التي تقطع الدورات (). في هذا العام، كانت إحدى المشكلات التي يمكنك تجربة حلها هي مشكلة تغطية قمة الرأس الموضحة أعلاه.
تكتسب المنافسة شعبية كل عام. إذا كنت تصدق البيانات الأولية، فقد شارك هذا العام 24 فريقًا في المسابقة لحل مشكلة تغطية القمة وحدها. تجدر الإشارة إلى أن المسابقة لا تستمر عدة ساعات أو حتى أسبوع، بل عدة أشهر. تتاح للفرق الفرصة لدراسة الأدبيات والتوصل إلى فكرتها الأصلية ومحاولة تنفيذها. في جوهرها، هذه المسابقة هي مشروع بحثي. وسيتم عقد أفكار للحلول الأكثر فعالية ومنح الفائزين بالتزامن مع المؤتمر (الندوة الدولية حول الحساب المحدد والدقيق) كجزء من أكبر اجتماع خوارزمي سنوي في أوروبا . يمكن العثور على مزيد من المعلومات التفصيلية حول المسابقة نفسها على ، ونتائج السنوات السابقة تكذب .
مخطط الحل
لحل مشكلة تغطية قمة الرأس، حاولت استخدام خوارزميات ذات معلمات. وتتكون عادةً من جزأين: قواعد التبسيط (التي تؤدي بشكل مثالي إلى النواة) وقواعد التقسيم. قواعد التبسيط هي المعالجة المسبقة للمدخلات في وقت متعدد الحدود. والغرض من تطبيق مثل هذه القواعد هو تقليل المشكلة إلى مشكلة أصغر مكافئة. تعد قواعد التبسيط الجزء الأكثر تكلفة في الخوارزمية، ويؤدي تطبيق هذا الجزء إلى إجمالي وقت التشغيل بدلاً من وقت متعدد الحدود البسيط. في حالتنا، تعتمد قواعد التقسيم على حقيقة أنه بالنسبة لكل قمة عليك أن تأخذها أو جارتها كإجابة.
المخطط العام هو كما يلي: نطبق قواعد التبسيط، ثم نختار بعض القمم، ونجري نداءين متكررين: في الأول نأخذه استجابةً، وفي الآخر نأخذ جميع جيرانه. وهذا ما نسميه الانقسام (التفرع) على طول هذا الرأس.
سيتم إجراء إضافة واحدة بالضبط إلى هذا المخطط في الفقرة التالية.
أفكار لقواعد التقسيم (الغداء).
دعونا نناقش كيفية اختيار الرأس الذي سيحدث الانقسام من خلاله.
الفكرة الرئيسية جشعة للغاية بالمعنى الخوارزمي: لنأخذ قمة من الدرجة القصوى ونقسمها على طولها. لماذا يبدو أفضل؟ لأنه في الفرع الثاني من الاستدعاء العودي سنقوم بإزالة الكثير من القمم بهذه الطريقة. يمكنك الاعتماد على رسم بياني صغير متبقي ويمكننا العمل عليه بسرعة.
يظهر هذا النهج، مع تقنيات kernelization البسيطة التي تمت مناقشتها بالفعل، نفسه جيدًا ويحل بعض الاختبارات التي يبلغ حجمها عدة آلاف من القمم. ولكن، على سبيل المثال، لا يعمل هذا بشكل جيد مع الرسوم البيانية المكعبة (أي الرسوم البيانية التي تبلغ درجة كل قمة ثلاثة).
هناك فكرة أخرى تعتمد على فكرة بسيطة إلى حد ما: إذا تم فصل الرسم البياني، فيمكن حل المشكلة المتعلقة بمكوناته المتصلة بشكل مستقل، من خلال الجمع بين الإجابات في النهاية. هذا، بالمناسبة، تعديل صغير موعود في المخطط، والذي سيسرع الحل بشكل كبير: سابقًا، في هذه الحالة، عملنا على منتج العصر لحساب استجابات المكونات، لكننا الآن نعمل من أجل المجموع. ولتسريع التفرع، تحتاج إلى تحويل الرسم البياني المتصل إلى رسم بياني غير متصل.
كيف افعلها؟ إذا كانت هناك نقطة مفصلية في الرسم البياني، فأنت بحاجة إلى القتال من أجلها. نقطة المفصل هي قمة بحيث عند إزالتها، يفقد الرسم البياني اتصاله. يمكن العثور على جميع نقاط الوصل في الرسم البياني باستخدام خوارزمية كلاسيكية في الوقت الخطي. هذا النهج يسرع بشكل كبير المتفرعة.
عند إزالة أي من القمم المحددة، سيتم تقسيم الرسم البياني إلى مكونات متصلة.
سنفعل هذا، ولكننا نريد المزيد. على سبيل المثال، ابحث عن قطع صغيرة في الرأس في الرسم البياني واقسمها على طول القمم منه. الطريقة الأكثر فعالية التي أعرفها للعثور على الحد الأدنى من القطع الرأسي العالمي هي استخدام شجرة جوموري-هو، والتي تم بناؤها بالزمن المكعب. في تحدي PACE، يبلغ حجم الرسم البياني النموذجي عدة آلاف من القمم. في هذه الحالة، يجب تنفيذ مليارات العمليات في كل قمة من شجرة العودية. اتضح أنه من المستحيل ببساطة حل المشكلة في الوقت المخصص.
دعونا نحاول تحسين الحل. يمكن العثور على الحد الأدنى للقمة المقطوعة بين زوج من القمم بواسطة أي خوارزمية تقوم بإنشاء الحد الأقصى للتدفق. يمكنك السماح لها على مثل هذه الشبكة ، في الممارسة العملية يعمل بسرعة كبيرة. لدي شك في أنه من الممكن نظريًا إثبات تقدير وقت التشغيل ، وهو أمر مقبول تمامًا بالفعل.
لقد حاولت عدة مرات البحث عن القطع بين أزواج القمم العشوائية واختيار الأكثر توازناً. لسوء الحظ، أدى هذا إلى نتائج سيئة في اختبار تحدي PACE المفتوح. لقد قارنتها مع خوارزمية تقسم القمم ذات الدرجة القصوى، وتشغلها مع تحديد عمق الهبوط. خوارزمية تحاول العثور على قطع بهذه الطريقة تركت وراءها رسومًا بيانية أكبر. ويرجع ذلك إلى حقيقة أن التخفيضات كانت غير متوازنة للغاية: بعد إزالة 5-10 قمم، كان من الممكن تقسيم 15-20 فقط.
تجدر الإشارة إلى أن المقالات حول أسرع الخوارزميات من الناحية النظرية تستخدم تقنيات أكثر تقدمًا لاختيار القمم للتقسيم. تتميز هذه التقنيات بتنفيذ معقد للغاية وغالبًا ما يكون أداءها ضعيفًا من حيث الوقت والذاكرة. لم أتمكن من تحديد تلك المقبولة تمامًا للممارسة.
كيفية تطبيق قواعد التبسيط
لدينا بالفعل أفكار للتركيز. دعني أذكرك:
- إذا كان هناك قمة معزولة، قم بحذفها.
- إذا كان هناك قمة من الدرجة 1، فقم بإزالتها وأخذ جارتها ردًا على ذلك.
- إذا كان هناك قمة من الدرجة على الأقل ك + 1، استعيدها.
مع الأولين، كل شيء واضح، مع الثالث هناك خدعة واحدة. إذا كنا في مشكلة كوميدية حول حانة، فقد تم إعطاؤنا حدًا أعلى لـ k، ثم في تحدي PACE، ما عليك سوى العثور على غطاء قمة بالحجم الأدنى. يعد هذا تحويلًا نموذجيًا لمشكلات البحث إلى مشكلات اتخاذ القرار؛ وفي كثير من الأحيان لا يوجد فرق بين نوعي المشكلات. من الناحية العملية، إذا كنا نكتب حلاً لمشكلة تغطية قمة الرأس، فقد يكون هناك اختلاف. على سبيل المثال، كما في النقطة الثالثة.
من وجهة نظر التنفيذ، هناك طريقتان للمضي قدما. النهج الأول يسمى التعميق التكراري. وهو كما يلي: يمكننا البدء ببعض القيود المعقولة من الأسفل على الإجابة، ثم تشغيل الخوارزمية الخاصة بنا باستخدام هذا القيد كقيد على الإجابة من الأعلى، دون النزول إلى مستوى أقل من هذا القيد في التكرار. إذا وجدنا بعض الإجابات، فمن المؤكد أنها الأمثل، وإلا فيمكننا زيادة هذا الحد بمقدار واحد والبدء من جديد.
هناك طريقة أخرى تتمثل في تخزين بعض الإجابات المثالية الحالية والبحث عن إجابة أصغر، وتغيير هذه المعلمة عند العثور عليها k لمزيد من قطع الفروع غير الضرورية في البحث.
بعد إجراء العديد من التجارب الليلية، استقررت على مزيج من هاتين الطريقتين: أولاً، أقوم بتشغيل الخوارزمية الخاصة بي مع نوع ما من القيود على عمق البحث (تحديدها بحيث لا تستغرق وقتًا يذكر مقارنة بالحل الرئيسي) واستخدام الأفضل تم العثور على الحل كحد أعلى للإجابة - أي لنفس الشيء k.
رؤوس الدرجة 2
لقد تعاملنا مع القمم من الدرجة 0 و 1. اتضح أنه يمكن القيام بذلك مع رؤوس الدرجة 2، ولكن هذا سيتطلب عمليات أكثر تعقيدًا من الرسم البياني.
لشرح ذلك، نحتاج إلى تعيين القمم بطريقة أو بأخرى. دعونا نسمي قمة الدرجة 2 قمة vوجيرانها - القمم x и y. التالي سيكون لدينا حالتين.
- عندما x и y - الجيران. ثم يمكنك الإجابة x и yو v يمسح. في الواقع، من هذا المثلث يجب أخذ رأسين على الأقل في المقابل، وبالتأكيد لن نخسر إذا أخذنا x и y: ربما لديهم جيران آخرين، و v هم ليسوا هنا.
- عندما x и y - وليس الجيران. ثم يذكر أنه يمكن لصق القمم الثلاثة في واحدة. الفكرة هي أنه في هذه الحالة هناك إجابة مثالية، والتي نأخذ فيها أيًا منهما vأو كلا الرأسين x и y. علاوة على ذلك، في الحالة الأولى، سيتعين علينا أن نأخذ جميع الجيران ردا على ذلك x и yولكن في الثانية ليس من الضروري. يتوافق هذا تمامًا مع الحالات التي لا نستجيب فيها للقمة الملصقة وعندما نفعل ذلك. يبقى فقط أن نلاحظ أنه في كلتا الحالتين تنخفض الاستجابة لمثل هذه العملية بمقدار واحد.
تجدر الإشارة إلى أن هذا النهج يصعب تنفيذه بدقة في وقت خطي عادل. يعد لصق القمم عملية معقدة، حيث تحتاج إلى نسخ قوائم الجيران. إذا تم ذلك بلا مبالاة، فقد ينتهي بك الأمر إلى الحصول على وقت تشغيل دون المستوى الأمثل بشكل مقارب (على سبيل المثال، إذا قمت بنسخ الكثير من الحواف بعد كل لصق). لقد استقريت على إيجاد مسارات كاملة من القمم من الدرجة الثانية وتحليل مجموعة من الحالات الخاصة، مثل الدورات من هذه القمم أو من جميع هذه القمم باستثناء واحدة.
بالإضافة إلى ذلك، من الضروري أن تكون هذه العملية قابلة للعكس، بحيث عند العودة من التكرار نعيد الرسم البياني إلى شكله الأصلي. ولضمان ذلك، لم أقم بمسح قوائم الحواف للقمم المدمجة، وبعد ذلك عرفت فقط الحواف التي يجب أن أذهب إليها. يتطلب تنفيذ الرسوم البيانية أيضًا الدقة، ولكنه يوفر وقتًا خطيًا مناسبًا. وبالنسبة للرسوم البيانية التي تحتوي على عشرات الآلاف من الحواف، فهي تتناسب مع ذاكرة التخزين المؤقت للمعالج، مما يعطي مزايا كبيرة في السرعة.
النواة الخطية
وأخيرا، الجزء الأكثر إثارة للاهتمام من النواة.
في البداية، تذكر أنه في الرسوم البيانية الثنائية يمكن العثور على الحد الأدنى لغطاء القمة باستخدام . للقيام بذلك تحتاج إلى استخدام الخوارزمية من أجل العثور على الحد الأقصى للتطابق هناك، ثم استخدم النظرية .
فكرة النواة الخطية هي كالتالي: أولاً نقوم بتقسيم الرسم البياني إلى قسمين، أي بدلاً من كل قمة v دعونا نضيف قمتين и وبدلا من كل حافة ش - ت دعونا نضيف ضلعين и . سيكون الرسم البياني الناتج ثنائيًا. دعونا نجد الحد الأدنى من الغطاء الرأسي فيه. ستصل بعض رؤوس الرسم البياني الأصلي إلى هناك مرتين، وبعضها مرة واحدة فقط، والبعض الآخر لن يصل أبدًا. تنص نظرية نيمهاوزر-تروتر على أنه في هذه الحالة يمكن إزالة القمم التي لم تضرب ولو مرة واحدة واستعادة تلك التي ضربت مرتين. علاوة على ذلك، تقول إنه من بين القمم المتبقية (تلك التي ضربت مرة واحدة) عليك أن تأخذ نصفها على الأقل كإجابة.
لقد تعلمنا للتو أن لا نترك أكثر من 2k قمم في الواقع، إذا كانت الإجابة المتبقية هي على الأقل نصف جميع الرؤوس، فلن يكون هناك المزيد من الرؤوس في المجموع أكثر من 2k.
وهنا تمكنت من اتخاذ خطوة صغيرة إلى الأمام. من الواضح أن النواة التي تم بناؤها بهذه الطريقة تعتمد على نوع الغطاء الرأسي الأدنى الذي أخذناه في الرسم البياني الثنائي. أود أن آخذ واحدة بحيث يكون عدد القمم المتبقية في حده الأدنى. في السابق، كانوا قادرين على القيام بذلك فقط في الوقت المناسب . لقد توصلت إلى تنفيذ هذه الخوارزمية في ذلك الوقت وبالتالي يمكن البحث عن هذا اللب في الرسوم البيانية لمئات الآلاف من القمم في كل مرحلة من مراحل التفرع.
نتيجة
تظهر الممارسة أن الحل الذي قدمته يعمل بشكل جيد في اختبارات عدة مئات من القمم وعدة آلاف من الحواف. في مثل هذه الاختبارات، من الممكن أن نتوقع العثور على حل خلال نصف ساعة. تزداد احتمالية العثور على إجابة في وقت مقبول، من حيث المبدأ، إذا كان الرسم البياني يحتوي على عدد كبير بما فيه الكفاية من القمم ذات الدرجة العالية، على سبيل المثال، الدرجة 10 وما فوق.
للمشاركة في المسابقة، كان لا بد من إرسال الحلول إلى . اذا حكمنا من خلال المعلومات المقدمة هناك ، حلّي في الاختبارات المفتوحة يحتل المرتبة الثالثة من أصل عشرين، بفارق كبير عن المركز الثاني. لكي نكون صادقين تمامًا، ليس من الواضح تمامًا كيف سيتم تقييم الحلول في المسابقة نفسها: على سبيل المثال، يجتاز الحل الخاص بي اختبارات أقل من الحل في المركز الرابع، ولكن في تلك التي تنجح، فإنه يعمل بشكل أسرع.
وستُعرف نتائج الاختبارات المغلقة في الأول من يوليو.
المصدر: www.habr.com