دانشمندان کامپیوتر رکورد مسئله فروشنده دوره‌گرد را شکستند

منتشر‌شده در: مجله quanta به تاریخ ۸ اکتبر ۲۰۲۰
لینک منبع: Computer Scientists Break Traveling Salesperson Record

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

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

اکنون، در مقاله‌ای که در ماه جولای به صورت آنلاین منتشر شد، کلین و مشاورانش در دانشگاه واشنگتن، آنا کارلین و شایان اویس قرن، در نهایت به هدفی رسیدند که دانشمندان کامپیوتر برای تقریبا نیم‌قرن دنبال کرده‌اند: راهی بهتر برای یافتن راه‌حل‌های تقریبی برای مسئله فروشنده دوره‌گرد.

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

همانطور که کریستوس پاپدیمیتریو، یک متخصص پیشرو در پیچیدگی محاسباتی، دوست دارد بگوید، مسئله فروشنده دوره‌گرد «یک مسئله نیست، یک اعتیاد است».

بیشتر دانشمندان علوم کامپیوتر بر این باورند که هیچ الگوریتمی وجود ندارد که بتواند به طور موثر بهترین راه‌حل را برای تمام ترکیب‌های ممکن از شهرها پیدا کند. اما در سال ۱۹۷۶، نیکوس کریستوفیدس الگوریتمی ارائه داد که به طور موثر راه‌حل‌های تقریبی را پیدا می‌کند-سفرهای رفت و برگشت که حداکثر ۵۰٪ طولانی‌تر از بهترین سفر رفت و برگشت هستند. در آن زمان، دانشمندان علوم کامپیوتر انتظار داشتند که یک نفر به زودی الگوریتم ساده کریستوفیدس را بهبود بخشد و به راه‌حل واقعی نزدیک‌تر شود. اما پیشرفت پیش‌بینی‌شده حاصل نشد.

امین صابری از دانشگاه استنفورد گفت: «افراد زیادی ساعات بی شماری را صرف بهبود این نتیجه کردند.»

در حال حاضر کارلین، کلین و اویس قرن ثابت کرده‌اند که الگوریتمی که یک دهه پیش ابداع شد، فاکتور ۵۰٪ کریستوفیدس را شکست می‌دهد، گرچه آن‌ها تنها قادر به کسر ۰.۲ بیلیونیم از تریلیونیم یک تریلیونیم یک درصد بودند. با این حال، این بهبود جزئی، هم از طریق یک منطق نظری و هم از طریق یک منطق روانی، به وجود می‌آید. محققان امیدوارند که این امر دریچه‌های عظیمی را برای بهبود بیشتر باز کند.

دیوید ویلیامسون از دانشگاه کرنل که از دهه ۱۹۸۰ در حال بررسی مسئله فروشنده دوره‌گرد بوده‌است گفت: «این نتیجه‌ای است که من در تمام طول دوران کاری‌ام می‌خواستم.»

مسئله فروشنده دوره‌گرد یکی از معدود مسائل اساسی است که دانشمندان نظری کامپیوتر بارها و بارها برای آزمایش محدودیت‌های محاسبات کارآمد به آن روی می‌آورند. ویلیامسون گفت: نتیجه جدید « اولین گام به سمت نشان دادن این است که مرزهای محاسبات کارآمد در واقع بهتر از چیزی است که ما فکر می‌کردیم.»

پیشرفت کسری

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

هر مسیر رفت و برگشت باید تعداد زوج یال در هر شهر داشته باشد، زیرا هر ورودی با یک خروجی همراه است. به نظر می‌رسد که معکوس آن نیز درست است-اگر هر شهر در یک شبکه دارای تعداد زوج اتصال باشد، یال‌های شبکه باید شامل یک مسیر رفت و برگشت باشد.

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

برای انجام این کار، او احتمالا مشهورترین الگوریتم تقریبی در علوم نظری کامپیوتر را ابداع کرد-الگوریتمی که معمولا اولین مثال را در کتب درسی و دروس شکل می‌دهد.

آلانتا نیومن از دانشگاه گرنوبل آلپ و مرکز ملی تحقیقات علمی در فرانسه گفت: « همه الگوریتم ساده را می‌شناسند. و در نتیجه شما به‌روزترین جواب را می‌دانید» - حداقل تا جولای گذشته اینطور بود.

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

در سال ۲۰۱۰، اویس قرن، صابری و مهیت سینگ از موسسه فن‌آوری جورجیا به این فکر افتادند که آیا ممکن است با انتخاب نکردن کوتاه‌ترین درخت اتصال همه شهرها، بلکه انتخاب یک درخت تصادفی از یک مجموعه به دقت انتخاب‌شده، بتوان الگوریتم کریستوفیدس را بهبود بخشید. آن‌ها از نسخه دیگری از مسئله فروشنده دوره‌گرد الهام‌گرفته‌اند که در آن شما مجاز به سفر در ترکیبی از مسیرها هستید-شاید بتوانید از طریق ۳/۴مسیر از شیکاگو تا دنور به علاوه ۱/۴ مسیر از لس‌آنجلس تا دنور به دنور بروید.

بر خلاف مسئله معمول فروشنده دوره‌گرد، این مسئله کسری می‌تواند به طور موثر حل شود. و در حالی که مسیرهای کسری منطقی نیستند، دانشمندان علوم کامپیوتر مدت‌ها است که بر این باورند که بهترین مسیر کسری باید یک راهنمای دقیق برای خطوط تراز مسیرهای معمولی خوب باشد.

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

این روش نه تنها برای سه محقق بلکه برای سایر دانشمندان علوم کامپیوتر نیز امیدوار کننده به نظر می‌رسید. اولا سونسن از موسسه فن‌آوری فدرال سوئیس لوزان گفت: « شهود ساده است. اما اثبات آن مسئله پیچیده‌تری است.»

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

کارلین گفت: « اگر ما باید یک یال بسیار گران‌قیمت به این تطابق‌ها اضافه کنیم، اساسا دچار مشکل می‌شویم.»

مقاومت کردن

با این وجود، اویس قرن از این هم‌کاری یک باور تغییر ناپذیر به‌وجود آورد که الگوریتم آن‌ها باید الگوریتم کریستوفیدس را برای مسئله عمومی فروشنده دوره‌گرد شکست دهد.

او گفت: «من هرگز شک نداشتم.»

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

کارلین فکر کرد که هرچه باشد، این یک فرصت جالب برای یادگیری بیشتر در مورد هندسه چند جمله‌ای است. او گفت: «من واقعا فکر نمی‌کردم که ما بتوانیم این مسئله را حل کنیم.»

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

این سه نفر در هم‌کاری شدیدی غرق شدند. کلین گفت: «به مدت دو سال، این تنها چیزی بود که به آن فکر می‌کردم.»

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

با این حال، آن‌ها به ابزار خود-به ویژه هندسه چند جمله‌ای-پی برده بودند. یک چندجمله‌ای، ترکیبی از جملات ساخته‌شده از اعداد و متغیرهایی است که به توان‌های بالا برده می‌شوند مانند 3x^2*y+8xz^2. برای مطالعه مسئله فروشنده دوره‌گرد، محققان یک نقشه از شهرها را به شکل یک چند جمله‌ای در نظر گرفتند که یک متغیر برای هر یال بین شهرها و یک عبارت برای هر درخت که می‌توانست تمام شهرها را به هم متصل کند،‌ دارد. سپس فاکتورهای عددی این عبارات را وزن دهی کردند تا مقدار هر یال در راه‌حل کسری برای مسئله فروشنده دوره‌گرد را نشان دهد.

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

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

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

در عرض یک سال، محققان دیگر با الگوریتم‌های کاملا متفاوتی مواجه شدند که تا حد زیادی ضریب تقریب برای مورد گرافیکی را بهبود دادند؛ که اکنون به جای ۵۰٪ کریسوتفیدس به ۴۰٪ کاهش پیدا کرده‌است.

سونسون، یکی از محققانی که پیشرفت بیشتری در این زمینه داشته‌است، گفت: «وقتی آن‌ها نتیجه خود [در این مورد گرافیکی] را اعلام کردند، … این باعث شد فکر کنیم که امکان دارد. این باعث شد ما برای آن تلاش کنیم.» سونسون سال‌ها در تلاش بوده‌است تا از الگوریتم کریستوفیدس برای مسئله عمومی فروشنده دوره‌گرد پیشی بگیرد. او گفت: « اکنون که می‌دانم ممکن است، دوباره امتحان خواهم کرد.»

طی چند دهه، مسئله فروشنده دوره‌گرد، روش‌های جدید بسیاری را به شهرت رسانده است. اویس قرن امیدوار است که این مسئله در حال حاضر همین نقش را برای هندسه چند جمله‌ای نیز ایفا کند؛ موضوعی که خودش در آن به یک مبلغ مشتاق تبدیل شده‌است. در یک دهه یا بیشتر از زمانی که او شروع به یادگیری در مورد این رویکرد کرد، این امر به او کمک کرد تا طیف گسترده‌ای از قضایا را اثبات کند. او گفت که این ابزار « کل حرفه من را شکل داده‌است.»

نیومن گفت: «نتیجه جدید از مسئله فروشنده دوره‌گرد، قدرت این رویکرد را نشان می‌دهد. قطعا این یک الهام برای نگاه دقیق‌تر به آن است.»

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

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