چگونه مسائل NP-Hard را با الگوریتم های پارامتری حل کنیم

کار تحقیقاتی شاید جالب ترین بخش آموزش ما باشد. ایده این است که در زمانی که هنوز در دانشگاه هستید، خود را در مسیر انتخابی خود امتحان کنید. به عنوان مثال، دانشجویان رشته های مهندسی نرم افزار و یادگیری ماشین اغلب برای انجام تحقیقات در شرکت ها (عمدتاً JetBrains یا Yandex، اما نه تنها) می روند.

در این پست در مورد پروژه خود در علوم کامپیوتر صحبت خواهم کرد. به عنوان بخشی از کارم، رویکردهایی را برای حل یکی از معروف ترین مسائل NP-hard مطالعه و به کار بردم: مشکل پوشش راس.

امروزه، یک رویکرد جالب برای مسائل NP-hard بسیار سریع در حال توسعه است - الگوریتم های پارامتری. من سعی خواهم کرد تا شما را به سرعت بالا ببرم، چند الگوریتم پارامتری ساده را به شما بگویم و یک روش قدرتمند را شرح دهم که به من کمک زیادی کرد. من نتایج خود را در مسابقه چالش PACE ارائه کردم: با توجه به نتایج تست های آزاد، راه حل من رتبه سوم را کسب می کند و نتایج نهایی در 1 ژوئیه مشخص می شود.

درباره خودم

نام من واسیلی آلفروف است، من اکنون سال سوم خود را در دانشکده عالی اقتصاد دانشگاه تحقیقات ملی - سن پترزبورگ به پایان می برم. من از دوران مدرسه که در مدرسه شماره 179 مسکو درس می خواندم و با موفقیت در المپیادهای علوم کامپیوتر شرکت می کردم، به الگوریتم علاقه داشتم.

تعداد محدودی متخصص در الگوریتم های پارامتری وارد نوار می شوند...

نمونه برگرفته از کتاب "الگوریتم های پارامتری شده"

تصور کنید که شما یک نگهبان یک بار در یک شهر کوچک هستید. هر جمعه، نیمی از شهر برای استراحت به بار شما می‌آیند، که برای شما دردسرهای زیادی ایجاد می‌کند: برای جلوگیری از دعوا، باید مشتریان شلوغ را از بار بیرون بیاورید. در نهایت خسته می شوید و تصمیم می گیرید اقدامات پیشگیرانه انجام دهید.

از آنجایی که شهر شما کوچک است، دقیقاً می‌دانید که اگر با هم در یک بار قرار بگیرند، کدام جفت مشتری احتمالاً با هم دعوا می‌کنند. آیا لیستی از n افرادی که امشب به بار خواهند آمد. شما تصمیم می گیرید بدون اینکه کسی وارد دعوا شود، برخی از مردم شهر را از بار دور نگه دارید. در عین حال، روسای شما نمی خواهند سود خود را از دست بدهند و اگر بیش از این اجازه ندهید، ناراضی خواهند بود. k مردم است.

متأسفانه، مشکل پیش روی شما یک مشکل کلاسیک NP-hard است. شما ممکن است او را بشناسید پوشش راس، یا به عنوان یک مشکل پوشش راس. برای چنین مشکلاتی، در حالت کلی، هیچ الگوریتمی وجود ندارد که در زمان قابل قبولی کار کند. به طور دقیق، فرضیه اثبات نشده و کاملا قوی ETH (فرضیه زمان نمایی) می گوید که این مشکل در زمان قابل حل نیست. ، یعنی شما نمی توانید چیزی بهتر از یک جستجوی کامل فکر کنید. به عنوان مثال، فرض کنید شخصی قرار است به بار شما بیاید 1000 نفر انسان. سپس جستجوی کامل خواهد بود گزینه هایی که تقریبا وجود دارد - مقدار دیوانه کننده خوشبختانه مدیریت شما به شما محدودیت داده است k = 10، بنابراین تعداد ترکیب هایی که باید روی آنها تکرار کنید بسیار کمتر است: تعداد زیر مجموعه های ده عنصر . این بهتر است، اما باز هم در یک روز حتی روی یک خوشه قدرتمند حساب نمی شود.

برای از بین بردن احتمال دعوا در این پیکربندی روابط تیره بین بازدیدکنندگان نوار، باید باب، دانیل و فدور را دور نگه دارید. هیچ راه حلی وجود ندارد که در آن تنها دو نفر پشت سر بگذارند.

آیا این بدان معناست که زمان تسلیم شدن و اجازه دادن به همه است؟ بیایید گزینه های دیگر را در نظر بگیریم. خوب، به عنوان مثال، شما نمی توانید فقط به کسانی اجازه دهید که به احتمال زیاد با تعداد بسیار زیادی از مردم مبارزه کنند. اگر کسی می تواند حداقل با k+1 شخص دیگری، پس قطعاً نمی توانید اجازه دهید او وارد شود - در غیر این صورت باید همه را بیرون نگه دارید k+1 مردم شهر، که او می تواند با آنها مبارزه کند، که قطعا رهبری را ناراحت می کند.

اجازه دهید طبق این اصل هرکسی را که می توانستید بیرون بریزید. آن وقت هر کس دیگری می تواند با بیش از k مردم. بیرون انداختنشون k مرد، شما نمی توانید چیزی بیش از جلوگیری از درگیری ها این بدان معنی است که اگر بیش از اگر شخصی حداقل در یک درگیری درگیر باشد، مطمئناً نمی توانید از همه آنها جلوگیری کنید. از آنجایی که مطمئناً افراد کاملاً بدون درگیری را وارد می‌کنید، باید از هر دویست نفر، همه زیرمجموعه‌های سایز ده را مرور کنید. تقریبا وجود دارد ، و این تعداد عملیات را می توان از قبل در خوشه مرتب کرد.

اگر بتوانید با خیال راحت افرادی را بگیرید که اصلاً درگیری ندارند، پس آنهایی که فقط در یک درگیری شرکت می کنند چطور؟ در واقع، آنها همچنین می توانند با بستن در به روی حریف خود اجازه ورود پیدا کنند. در واقع، اگر آلیس فقط با باب در تضاد باشد، پس اگر آلیس را از بین آن دو آزاد کنیم، بازنده نخواهیم شد: باب ممکن است درگیری های دیگری داشته باشد، اما آلیس مطمئناً آنها را ندارد. علاوه بر این، منطقی نیست که ما هر دوی خود را وارد نکنیم. پس از چنین عملیاتی دیگر چیزی باقی نمی ماند مهمانانی با سرنوشتی حل نشده: ما فقط داریم درگیری‌هایی که هر کدام با دو شرکت‌کننده و هر کدام در حداقل دو شرکت درگیر هستند. بنابراین تنها چیزی که باقی می ماند این است که مرتب سازی کنیم گزینه هایی که به راحتی می توان آن ها را نیم روز در لپ تاپ در نظر گرفت.

در واقع، با استدلال ساده می توانید به شرایط جذاب تری دست پیدا کنید. توجه داشته باشید که ما قطعاً باید همه اختلافات را حل کنیم، یعنی از هر جفت متضاد، حداقل یک نفر را انتخاب کنیم که اجازه ورود به او را نخواهیم داد. بیایید الگوریتم زیر را در نظر بگیریم: هر درگیری را که از آن یک شرکت‌کننده را حذف می‌کنیم و به صورت بازگشتی از بقیه شروع می‌کنیم، سپس دیگری را حذف می‌کنیم و همچنین به صورت بازگشتی شروع می‌کنیم. از آنجایی که ما در هر مرحله فردی را بیرون می اندازیم، درخت بازگشتی چنین الگوریتمی درخت دودویی عمق است. k، بنابراین در کل الگوریتم کار می کند جایی که n تعداد رئوس است و m - تعداد دنده ها در مثال ما، این حدود ده میلیون است که می توان آن را در یک ثانیه نه تنها در یک لپ تاپ، بلکه حتی در یک تلفن همراه محاسبه کرد.

مثال بالا یک نمونه است الگوریتم پارامتری شده. الگوریتم های پارامتری، الگوریتم هایی هستند که در زمان اجرا می شوند f(k) poly(n)جایی که p - چند جمله ای، f یک تابع قابل محاسبه دلخواه است و k - برخی از پارامترها، که احتمالاً بسیار کوچکتر از اندازه مشکل خواهد بود.

تمام استدلال های قبل از این الگوریتم یک مثال می دهد هسته سازی یکی از تکنیک های کلی برای ایجاد الگوریتم های پارامتری است. هسته سازی کاهش اندازه مسئله به مقدار محدود شده توسط تابعی از یک پارامتر است. مشکل حاصل اغلب هسته نامیده می شود. بنابراین، با استدلال ساده در مورد درجات رئوس، یک هسته درجه دوم برای مسئله پوشش راس به دست آوردیم که با اندازه پاسخ پارامتر شده است. تنظیمات دیگری نیز وجود دارد که می توانید برای این کار انتخاب کنید (مانند Vertex Cover Above LP)، اما این تنظیماتی است که در مورد آن صحبت خواهیم کرد.

چالش سرعت

رقابت چالش PACE (چالش الگوریتم های پارامتری و آزمایش های محاسباتی) در سال 2015 برای ایجاد ارتباط بین الگوریتم های پارامتری شده و رویکردهای مورد استفاده در عمل برای حل مسائل محاسباتی متولد شد. سه مسابقه اول به یافتن پهنای درخت یک نمودار اختصاص داشت (پهنای درخت)، در جستجوی درخت اشتاینر (درخت اشتاینر) و جستجوی مجموعه ای از رئوس که چرخه ها را قطع می کند (مجموعه راس بازخورد). امسال، یکی از مشکلاتی که می‌توانید در آن تلاش کنید، مشکل پوشش راس بود که در بالا توضیح داده شد.

این رقابت هر سال محبوبیت بیشتری پیدا می کند. اگر داده های اولیه را باور کنید، امسال 24 تیم برای حل مشکل پوشش راس به تنهایی در مسابقه شرکت کردند. شایان ذکر است که این مسابقه نه چند ساعت یا حتی یک هفته بلکه چندین ماه به طول می انجامد. تیم ها این فرصت را دارند که ادبیات را مطالعه کنند، ایده اصلی خود را ارائه دهند و سعی کنند آن را اجرا کنند. در اصل این مسابقه یک پروژه تحقیقاتی است. ایده هایی برای موثرترین راه حل ها و اهدای جوایز به برندگان همزمان با کنفرانس برگزار می شود. IPEC (سمپوزیوم بین المللی محاسبات پارامتری و دقیق) به عنوان بخشی از بزرگترین نشست الگوریتمی سالانه در اروپا ALGO. اطلاعات دقیق تر در مورد خود مسابقه را می توانید در اینجا پیدا کنید کاربران آنلاین حاضر در سایت "، و نتایج سالهای گذشته دروغ است اینجا.

نمودار حل

برای حل مشکل پوشش راس، از الگوریتم های پارامتری استفاده کردم. آنها معمولاً از دو بخش تشکیل شده‌اند: قوانین ساده‌سازی (که در حالت ایده‌آل منجر به هسته‌سازی می‌شوند) و قوانین تقسیم‌بندی. قوانین ساده سازی، پیش پردازش ورودی در زمان چند جمله ای است. هدف از اعمال چنین قوانینی کاهش مشکل به یک مسئله کوچکتر معادل است. قوانین ساده سازی گران ترین بخش الگوریتم هستند و اعمال این بخش منجر به کل زمان اجرا می شود. به جای زمان چند جمله ای ساده در مورد ما، قوانین تقسیم بر این واقعیت استوار است که برای هر رأس باید آن را یا همسایه اش را به عنوان پاسخ در نظر بگیرید.

طرح کلی به این صورت است: قوانین ساده سازی را اعمال می کنیم، سپس تعدادی راس را انتخاب می کنیم و دو فراخوان بازگشتی ایجاد می کنیم: در اولی آن را در پاسخ می گیریم و در دیگری همه همسایگان آن را می گیریم. این همان چیزی است که ما آن را تقسیم (انشعاب) در طول این راس می نامیم.

در پاراگراف بعدی دقیقاً یک مورد به این طرح اضافه خواهد شد.

ایده هایی برای تقسیم (برانچینگ) قوانین

بیایید در مورد چگونگی انتخاب یک راس که در امتداد آن تقسیم رخ می دهد بحث کنیم.
ایده اصلی به معنای الگوریتمی بسیار حریصانه است: بیایید یک راس حداکثر درجه را بگیریم و در امتداد آن تقسیم کنیم. چرا بهتر به نظر می رسد؟ زیرا در شاخه دوم فراخوانی بازگشتی، رئوس زیادی را به این ترتیب حذف خواهیم کرد. می توانید روی یک نمودار کوچک باقی مانده حساب کنید و ما می توانیم به سرعت روی آن کار کنیم.

این رویکرد، با تکنیک‌های هسته‌سازی ساده که قبلاً مورد بحث قرار گرفت، خود را به خوبی نشان می‌دهد و برخی از تست‌های چند هزار رئوس را حل می‌کند. اما مثلاً برای نمودارهای مکعبی (یعنی نمودارهایی که درجه هر رأس آنها سه است) خوب کار نمی کند.
ایده دیگری بر اساس یک ایده نسبتا ساده وجود دارد: اگر گراف قطع شود، مشکل اجزای متصل به آن را می توان به طور مستقل حل کرد و پاسخ ها را در پایان ترکیب کرد. به هر حال، این یک اصلاح کوچک وعده داده شده در طرح است که راه حل را به میزان قابل توجهی سرعت می بخشد: قبلاً در این مورد، ما برای محاسبه پاسخ مؤلفه ها برای حاصل ضرب زمان ها کار می کردیم، اما اکنون برای مجموع. و برای سرعت بخشیدن به انشعاب، باید یک نمودار متصل را به یک نمودار قطع شده تبدیل کنید.

چگونه انجامش بدهیم؟ اگر نقطه بیانی در نمودار وجود دارد، باید در آن بجنگید. نقطه مفصلی یک راس است به طوری که با حذف، گراف اتصال خود را از دست می دهد. تمام نقاط اتصال در یک نمودار را می توان با استفاده از یک الگوریتم کلاسیک در زمان خطی پیدا کرد. این رویکرد به طور قابل توجهی سرعت انشعاب را افزایش می دهد.

هنگامی که هر یک از رئوس انتخاب شده حذف شود، نمودار به اجزای متصل تقسیم می شود.

ما این کار را خواهیم کرد، اما بیشتر می خواهیم. به عنوان مثال، به دنبال برش های کوچک رأس در نمودار بگردید و در امتداد رئوس از آن تقسیم کنید. کارآمدترین روشی که من برای یافتن حداقل برش راس جهانی می شناسم استفاده از درخت Gomori-Hu است که در زمان مکعب ساخته شده است. در چالش PACE، اندازه نمودار معمولی چندین هزار رأس است. در این شرایط، میلیاردها عملیات باید در هر رأس درخت بازگشتی انجام شود. به نظر می رسد که حل مشکل در زمان تعیین شده به سادگی غیرممکن است.

بیایید سعی کنیم راه حل را بهینه کنیم. حداقل برش راس بین یک جفت رئوس را می توان با هر الگوریتمی که حداکثر جریان را ایجاد می کند پیدا کرد. می توانید آن را به چنین شبکه ای اجازه دهید الگوریتم دینیتز، در عمل خیلی سریع کار می کند. من مشکوک هستم که از نظر تئوری امکان اثبات تخمینی برای زمان عملیات وجود دارد ، که در حال حاضر کاملا قابل قبول است.

من چندین بار سعی کردم به دنبال برش بین جفت رئوس تصادفی باشم و متعادل ترین راس را انتخاب کنم. متأسفانه، این نتایج ضعیفی را در آزمایش چالش باز PACE ایجاد کرد. من آن را با الگوریتمی مقایسه کردم که رئوس حداکثر درجه را تقسیم می‌کند و آنها را با محدودیت در عمق فرود اجرا می‌کند. الگوریتمی که در تلاش برای یافتن یک برش از این طریق بود، نمودارهای بزرگتری را پشت سر گذاشت. این به این دلیل است که برش ها بسیار نامتعادل بودند: با حذف 5-10 رئوس ، می توان فقط 15-20 را تقسیم کرد.

شایان ذکر است که مقالاتی درباره سریع‌ترین الگوریتم‌ها از نظر تئوری از تکنیک‌های بسیار پیشرفته‌تری برای انتخاب رئوس برای تقسیم استفاده می‌کنند. چنین تکنیک هایی پیاده سازی بسیار پیچیده و اغلب عملکرد ضعیفی از نظر زمان و حافظه دارند. من نتوانستم مواردی را که برای تمرین کاملاً قابل قبول هستند شناسایی کنم.

نحوه اعمال قوانین ساده سازی

ما در حال حاضر ایده هایی برای هسته سازی داریم. بگذارید یادآوری کنم:

1. اگر یک راس مجزا وجود دارد، آن را حذف کنید.
2. اگر راس درجه 1 وجود دارد، آن را بردارید و همسایه آن را در پاسخ بگیرید.
3. اگر یک راس درجه حداقل وجود دارد k+1، آن را پس بگیرید.

با دو مورد اول همه چیز روشن است، با سومی یک ترفند وجود دارد. اگر در یک مشکل کمیک در مورد یک نوار به ما حد بالایی داده می شد k، سپس در چالش PACE فقط باید یک پوشش راس با حداقل اندازه پیدا کنید. این یک تبدیل معمولی از مسائل جستجو به مسائل تصمیم است؛ اغلب هیچ تفاوتی بین این دو نوع مشکل وجود ندارد. در عمل، اگر در حال نوشتن یک حل کننده برای مسئله پوشش راس باشیم، ممکن است تفاوتی وجود داشته باشد. مثلاً مانند نکته سوم.

از نقطه نظر اجرا، دو راه برای ادامه وجود دارد. اولین رویکرد عمیق‌سازی تکراری نامیده می‌شود. به شرح زیر است: می‌توانیم با محدودیت معقولی از پایین روی پاسخ شروع کنیم و سپس الگوریتم خود را با استفاده از این محدودیت به عنوان یک محدودیت برای پاسخ از بالا اجرا کنیم، بدون اینکه در بازگشت از این محدودیت کمتر شویم. اگر پاسخی پیدا کرده باشیم، تضمین می شود که بهینه است، در غیر این صورت می توانیم این حد را یک بار افزایش دهیم و دوباره شروع کنیم.

روش دیگر این است که مقداری از پاسخ بهینه فعلی را ذخیره کنید و به دنبال پاسخ کوچکتر بگردید و در صورت یافتن این پارامتر را تغییر دهید k برای قطع بیشتر شاخه های غیر ضروری در جستجو.

پس از انجام چندین آزمایش آخر شب، به ترکیبی از این دو روش اکتفا کردم: اول، الگوریتم خود را با محدودیتی در عمق جستجو اجرا می‌کنم (آن را طوری انتخاب می‌کنم که در مقایسه با راه‌حل اصلی زمان ناچیزی بگیرد) و از بهترین روش استفاده می‌کنم. راه حلی که به عنوان حد بالایی برای پاسخ یافت می شود - یعنی برای همان چیز k.

رئوس درجه 2

ما با رئوس درجه 0 و 1 سروکار داشتیم. به نظر می رسد که این را می توان با رئوس درجه 2 انجام داد، اما این به عملیات پیچیده تری از نمودار نیاز دارد.

برای توضیح این موضوع، باید به نحوی رئوس را مشخص کنیم. یک راس درجه 2 را رأس بنامیم v، و همسایگان آن - رئوس x и y. در ادامه دو مورد خواهیم داشت.

1. وقتی که x и y - همسایه ها. بعد میتونی جواب بدی x и yو v حذف. در واقع، از این مثلث حداقل دو رأس باید در ازای آن گرفته شود، و اگر بگیریم قطعا ضرر نخواهیم کرد. x и y: احتمالاً همسایگان دیگری دارند و v آنها اینجا نیستند.
2. وقتی که x и y - نه همسایه ها سپس بیان می شود که هر سه راس را می توان به یکی چسباند. ایده این است که در این مورد یک پاسخ بهینه وجود دارد که در آن هر کدام را می گیریم v، یا هر دو راس x и y. علاوه بر این، در مورد اول، ما باید همه همسایگان را در پاسخ بپذیریم x и y، اما در دومی لازم نیست. این دقیقاً مطابق با مواردی است که راس چسب را در پاسخ نمی گیریم و زمانی که می گیریم. فقط باید توجه داشت که در هر دو مورد پاسخ چنین عملیاتی یک بار کاهش می یابد.

شایان ذکر است که اجرای دقیق این رویکرد در زمان خطی منصفانه بسیار دشوار است. چسباندن رئوس یک عملیات پیچیده است؛ شما باید لیست همسایگان را کپی کنید. اگر این کار با بی دقتی انجام شود، می توانید به زمان اجرای مجانبی کمتر از حد مطلوب برسید (به عنوان مثال، اگر بعد از هر چسباندن لبه های زیادی کپی کنید). من به یافتن کل مسیرها از رئوس درجه 2 و تجزیه و تحلیل دسته ای از موارد خاص، مانند چرخه هایی از این رئوس یا از همه این رئوس ها به جز یک رئوس، تصمیم گرفتم.

علاوه بر این، لازم است که این عملیات برگشت پذیر باشد، به طوری که در هنگام بازگشت از بازگشت، گراف را به شکل اولیه بازگردانیم. برای اطمینان از این موضوع، لیست لبه های رئوس ادغام شده را پاک نکردم، و سپس فقط می دانستم کدام یال ها باید به کجا بروند. این پیاده سازی نمودارها نیز به دقت نیاز دارد، اما زمان خطی منصفانه ای را فراهم می کند. و برای نمودارهای چند ده هزار لبه، در حافظه نهان پردازنده قرار می گیرد، که مزایای زیادی در سرعت به ارمغان می آورد.

هسته خطی

در نهایت، جالب ترین بخش هسته.

برای شروع، به یاد بیاورید که در نمودارهای دو بخشی حداقل پوشش راس را می توان با استفاده از آن یافت . برای این کار باید از الگوریتم استفاده کنید هاپکرافت-کارپ به منظور یافتن حداکثر تطابق در آنجا، و سپس از قضیه استفاده کنید کونیگ-اگرواری.

ایده یک هسته خطی این است: ابتدا نمودار را دوشاخه می کنیم، یعنی به جای هر رأس. v بیایید دو قله اضافه کنیم и و به جای هر لبه u - v بیایید دو دنده اضافه کنیم и . نمودار حاصل دو بخشی خواهد بود. اجازه دهید حداقل پوشش راس را در آن پیدا کنیم. برخی از رئوس نمودار اصلی دو بار، برخی فقط یک بار و برخی دیگر هرگز به آنجا خواهند رسید. قضیه Nemhauser-Trotter بیان می کند که در این مورد می توان رئوسی را که حتی یک بار هم برخورد نکرده اند حذف کرد و آنهایی را که دو بار برخورد کردند را پس گرفت. علاوه بر این، او می گوید که از رئوس باقیمانده (آنهایی که یک بار برخورد می کنند) باید حداقل نصف را به عنوان پاسخ در نظر بگیرید.

ما تازه یاد گرفته ایم که بیشتر از آن ترک نکنیم 2k قله ها در واقع، اگر پاسخ باقیمانده حداقل نیمی از همه رئوس باشد، در مجموع هیچ رئوسی بیشتر از 2k.

در اینجا توانستم یک قدم کوچک به جلو بردارم. واضح است که هسته ای که به این روش ساخته می شود به این بستگی دارد که چه نوع پوشش راس حداقلی در گراف دوبخشی گرفته ایم. من می خواهم یکی را بگیرم تا تعداد رئوس باقی مانده حداقل باشد. قبلاً آنها فقط به موقع می توانستند این کار را انجام دهند . من در آن زمان به پیاده سازی این الگوریتم رسیدم بنابراین، این هسته را می توان در نمودارهای صدها هزار رأس در هر مرحله انشعاب جستجو کرد.

نتیجه

تمرین نشان می دهد که راه حل من روی تست های چند صد راس و چندین هزار یال به خوبی کار می کند. در چنین آزمایشاتی کاملاً ممکن است انتظار داشت که در نیم ساعت راه حل پیدا شود. احتمال یافتن پاسخ در یک زمان قابل قبول، در اصل، در صورتی افزایش می‌یابد که نمودار دارای تعداد کافی رئوس درجه بالا باشد، مثلاً درجه 10 و بالاتر.

برای شرکت در مسابقه باید راه حل هایی ارسال می شد optil.io. با قضاوت بر اساس اطلاعات ارائه شده در آنجا امضا کردن، راه حل من در تست های باز رتبه سوم از بیست را دارد، با فاصله زیادی از دوم. کاملاً صادقانه بگویم، کاملاً مشخص نیست که چگونه راه‌حل‌ها در خود مسابقه ارزیابی می‌شوند: به عنوان مثال، راه‌حل من تست‌های کمتری نسبت به راه‌حل رتبه چهارم می‌دهد، اما در مواردی که موفق می‌شوند، سریع‌تر عمل می‌کند.

نتایج آزمایشات بسته اول تیرماه مشخص خواهد شد.

منبع: www.habr.com