استفاده از بهترین الگوریتم های تقریب در علوم رایانه

تصویر: یافتن بهترین راه سفر از A تا B ، C  و D و بازگشت به A ممکن است چندان سخت نباشد، اما افزودن چند مقصد دیگر می تواند شما را دچار سردرد کند.
 
رایانه‌ها در پاسخ گویی به سؤالات ما تبحر دارند. آنها برای سؤالاتی از قبیل کوتاه‌ترین مسیر از خانه من به منطقه 51 کدام است، آیا 8675309 یک عدد اول است، یک قاشق غذاخوری چند قاشق چای خوری می‌شود، آماده کمک به ما هستند.
 
با این حال یک سری سؤالات به ظاهر ساده‌ وجود دارد که دانشمندان علم رایانه معتقدند رایانه‌ها هرگز قادر به پاسخ گویی به آنها نخواهند بود، این اتفاق حداقل در طول زندگی ما رخ نخواهد داد. این مسائل، موضوع سؤال P در مقابل NP هستند که می‌پرسد آیا مسائلی که راه حل‌های آنها سریع بررسی می‌شود می‌توانند به همان سرعت حل شوند. P در مقابل NP چنان سؤال اساسی است که طراحی یک الگوریتم سریع برای حل یکی از این مسائل دشوار و یا اثبات آن، یک میلیون دلار جایزه به همراه خواهد داشت.
 
مسئله محبوب من فروشنده دوره گرد است. سؤال سخت این است: با فرض وجود مجموعه‌ای از شهرها برای مسافرت این فروشنده، مقرون به صرفه‌ترین مسیری که از همه شهرها عبور کند و به شهر مبداء بازگردد کدام است؟ دانشمندان علم رایانه برای رسیدن به پاسخ‌های عملی در دنیای واقعی از الگوریتم‌های تقریب استفاده می‌کنند، اگر چه این روش‌ها راه حل دقیقی برای این گونه مسائل به دست نمی‌دهند اما آن قدر به پاسخ مطلوب نزدیک می‌شوند که مفید واقع می‌شوند. تاکنون، بهترین الگوریتم‌هایی که ارائه شده (سال 1976) احتمال دور بودن پاسخ‌ها از بهترین پاسخ را کمتر از 50 درصد تضمین کرده است.
 برخلاف الگوریتم "کریستوفیدس"، که دارای محدود کننده سخت 50٪ است، ما گمان می‌کنیم در الگوریتم ما ممکن است به اندازه 33٪ باشد.من به عنوان یک دانشمند علم رایانه روی الگوریتم‌های تقریب کار می‌کنم. من و همکارانم "آنا کارلین" و "شایان اویس قرَن" راهی پیدا کرده‌ایم (هرچند به سختی) که بتواند رکورد این 50٪ را شکست دهد. ما توانستیم ثابت کنیم که یک الگوریتم تقریبی خاص، شکافی را در این سد قدیمی ایجاد می‌کند. این یافته راه را برای پیشرفت‌های چشمگیرتر باز می‌کند.
 
اهمیت این دستاورد برای موارد فراتر از برنامه ریزی مسیرهاست. هر یک از این مسائل سخت را می‌توان در مشکل فروشنده دوره گرد رمز گذاری کرد و بالعکس، به این ترتیب اگر یکی را حل کنید همه آنها را حل کرده‌اید. می‌‌توانیم بگوییم که این مسائل سخت، همه هیولاهای محاسباتی هستند که در لباس مبدل ظاهر می‌شوند.
 

یافتن بهترین مسیر دشوار است

معمولاً این مسئله به عنوان "یافتن کوتاه‌ترین مسیر" بیان می‌شود. با این حال، کارآمدترین راه حل می‌تواند مبتنی بر مقادیر مختلفی مانند زمان و هزینه و همچنین مسافت در دنیای واقعی باشد.
 
برای درک دشواری این مسئله تصور کنید که شخصی لیستی از 100 شهر به همراه هزینه بلیط هواپیما، قطار و اتوبوس بین هر جفت از شهرها به شما می‌دهد. آیا فکر می‌کنید می‌توانید ارزان‌ترین تور را برای بازدید از همه شهرها ترتیب دهید؟
 
تعداد قابل توجهی از مسیرهای ممکن را باید در نظر بگیرید. اگر 100 شهر دارید که می‌خواهید به آنها سفر کنید، تعداد مسیرهای ممکن برای بازدید از آنها 100 فاکتوریل است، یعنی100 × 99 × 98 x … × 1  که بزرگ‌تر از تعداد اتم‌های جهان است.
   
تصویر: این مجموعه از نقاط و خطوط، کوتاه‌ترین سفر فروشنده دوره گرد است که از 1000 نقطه عبور می‌کند.
 

پیش رفتن با نتایج خوب و کافی

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

الگوریتم تقریب: قهرمان دیرینه

یکی از اولین و مشهورترین الگوریتم‌های تقریب، الگوریتم طراحی شده برای مسئله فروشنده دوره گرد است که به الگوریتم "کریستوفیدس – سردیوکوف" معروف است. این الگوریتم در دهه 1970 توسط "نیکوس کریستوفیدس" و توسط یک ریاضیدان شوروی سابق به نام "آناتولی سردیوکوف" به طور مستقل طراحی شد، البته کار وی تا همین اواخر چندان شناخته شده نبود.
 هیچ راهی برای دانستن این که الگوریتم تقریب برای یک مثال خاص چقدر به راه حل مطلوب نزدیک می‌شود وجود ندارد.الگوریتم "کریستوفیدس – سردیوکوف"، حداقل با توجه به سایر الگوریتم‌ها، کاملاً ساده است. شما می‌توانید مسئله فروشنده دوره گرد را مانند شبکه‌ای بدانید که در آن هر شهر یک گره است و هر مسیر بین یک جفت شهر یک ضلع یا لبه است. به هر لبه یک "ارزش" اختصاص داده شده است، که به عنوان مثال می تواند زمان سفر بین دو شهر باشد. الگوریتم ابتدا ارزان‌ترین مجموعه لبه‌هایی را انتخاب می‌کند که تمام شهرها را به هم متصل می‌سازد.
 
به نظر می‌رسد انجام این کار آسان است: شما فقط ارزان‌ترین لبه را که یک شهر جدید را متصل می‌کند اضافه می‌کنید. با این حال، این یک راه حل نیست. پس از اتصال همه شهرها، ممکن است تعداد لبه‌ها از برخی از آنها فرد از کار در بیاید، که منطقی نیست: هر بار که با یک لبه وارد یک شهر می‌شوید، باید یک لبه مکمل برای ترک آن استفاده کنید. بنا بر این این الگوریتم ارزان‌ترین مجموعه لبه‌ها را اضافه می‌کند که باعث می‌شود هر شهر تعداد لبه‌های زوج داشته باشد و سپس از این برای ارائه تور گشت و گذار در شهرها استفاده می‌کند.
 
این الگوریتم به سرعت اجرا می‌شود و همیشه یک راه حل تولید می‌کند که حداکثر 50٪ طولانی‌تر از راه حل مطلوب است. بنا بر این، اگر یک تور 150 مایلی ارائه کند، به این معنی است که بهترین تور کوتاه‌تر از 100 مایل نیست.
 
البته، هیچ راهی برای دانستن این که الگوریتم تقریب برای یک مثال خاص چقدر به راه حل مطلوب نزدیک می‌شود وجود ندارد، مگر این که واقعاً راه حل مطلوب را بدانید، که در این صورت دیگر نیازی به الگوریتم تقریب نیست! اما اثبات چیزی در مورد بدترین حالت، امکان پذیر است. به عنوان مثال، الگوریتم "کریستوفیدس – سردیوکوف"، تضمین می‌کند که توری را ارائه ‌کند که حداکثر 5ر1 برابر طول کوتاه‌ترین مجموعه لبه‌های اتصال همه شهرها است و بنا بر این، حداکثر 5ر1 برابر طول تور مطلوب خواهد بود.
 

یک پیشرفت واقعاً کوچک که یک مسئله مهم است

از زمان کشف این الگوریتم در سال 1976، دانشمندان علم رایانه قادر به بهبود آن نبوده‌اند. با این حال، تابستان سال گذشته من و همکارانم ثابت کردیم که یک الگوریتم خاص به طور متوسط توری ارائه می‌کند که کمتر از 49.99999٪ فاصله با راه حل مطلوب دارد. من ناگزیرم از درج تعداد واقعی 9 ها صرف نظر کنم، چون تعداد آنها بسیار زیاد است، اما با این وجود این الگوریتم سد دیرینه 50٪ را می‌شکند.
 
الگوریتمی که ما آنالیز کردیم بسیار شبیه "کریستوفیدس-سردیوکوف" است. تنها تفاوتش در این است که در اولین مرحله، مجموعه‌ای تصادفی از لبه‌ها را انتخاب می‌کند که همه شهرها را به هم متصل می‌سازد و به طور میانگین مانند یک تور فروشنده دوره گرد به نظر می‌رسد. ما از این انتخاب تصادفی استفاده می‌کنیم تا نشان دهیم دیگر جایی که الگوریتم قبلی در آن گیر کرده بود گیر نمی‌کنیم.
 دانشمندان علم رایانه گزینه "به اندازه کافی خوب" را پذیرفته‌اند و از 50 سال گذشته تاکنون روی الگوریتم‌های به اصطلاح تقریب کار کرده‌اند.با وجودی که پیشرفت ما اندک است، اما امیدواریم که برای محققان دیگر الهام بخش باشد تا نگاهی دیگر به این مشکل بیندازند و پیشرفت بیشتری داشته باشند. غالباً در حوزه تحقیق ما آستانه‌هایی مانند 50٪ برای مدت طولانی ثابت می‌مانند و پس از اولین تلنگر، با سرعت بیشتری سقوط می‌کنند. یکی از امیدهای بزرگ ما این است که درکی که درباره فروشنده دوره گرد در حین اثبات این نتیجه به دست آوردیم انگیزه‌ای برای پیشرفت بیشتر باشد.
 

نزدیک شدن به کمال

برای این هدف خوش بینانه که می‌خواهیم ظرف چند سال آینده پیشرفت بیشتری داشته باشیم دلیل دیگری داریم: ما فکر می‌کنیم الگوریتمی که ما آنالیز کردیم و در سال 2010 طراحی و ساخته شد، ممکن است خیلی بهتر از آن چیزی باشد که توانستیم اثبات کنیم. برخلاف الگوریتم "کریستوفیدس"، که دارای محدود کننده سخت 50٪ است، ما گمان می‌کنیم در الگوریتم ما ممکن است به اندازه 33٪ باشد.
 
در واقع، نتایج آزمایشی که الگوریتم تقریبی را با راه حل‌های شناخته شده مطلوب مقایسه می‌کند، نشان می‌دهد که این الگوریتم در عمل کاملاً خوب است و اغلب تور را تنها با چند درصد فاصله با حد مطلوب ارائه می‌کند.
 مسئله فروشنده دوره گرد علاوه بر یافتن مسیرهایی برای فروشندگان دوره گرد (یا این روزها کامیون‌های حمل بار)، در بسیاری از زمینه‌ها، از نقشه برداری ژنوم گرفته تا طراحی تابلوهای مدار کاربرد دارد.حد نظری فعلی حدود 1٪ است - به این معنی که  هیچ الگوریتمی وجود ندارد (مگر اینکه P = NP) که بتواند در حد 1٪ از حد مطلوب باشد. سؤالی که نظریه پردازان امیدوارند به آن پاسخ دهند این است که چقدر می‌توانیم به حد مطلوب نزدیک‌ شویم؟
 
منبع: ناتان کلِین، University of Washington