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

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

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

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

حالا کارلین، کلین و اویس قرن به الگوریتمی دست یافتند که قادر است معیار ۵۰ درصدی کریستوفیدس را شکست دهد. گرچه تغییرات به‌دست‌آمده اندک هستند، پژوهشگرها امیدوار هستند این پژوهش زمینه‌سازی پیشرفت‌های آینده باشد. دیوید ویلیامسون از دانشگاه کرنل، از دهه‌ی ۱۹۸۰ به بررسی مسئله‌ی فروشنده‌ی دوره‌گرد می‌پردازد. او می‌گوید:

در طول سال‌ها کار حرفه‌ای به‌دنبال بهینه‌سازی مسئله‌ی فروشنده‌ی دوره‌گرد بودم. نتیجه‌ی جدید گامی در جهت بهینه‌سازی محاسبات کامپیوتری است.

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

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

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

کوتاه‌ترین درختی که تمام شهرها را به یکدیگر وصل کند، فاقد ویژگی برابری است؛ زیرا هر شهر در انتهای یک شاخه تنها یک اتصال با شهر دیگر دارد. درنتیجه کریستوفیدس برای تبدیل کوتاه‌ترین درخت به کوتاه‌ترین مسیر دوره‌ای، راه بهتری برای اتصال زوج شهرهایی پیدا کرد که تعداد یال آن‌ها فرد است. سپس ثابت کرد مسیر به‌دست‌آمده هرگز بیشتر از ۵۰ درصد طولانی‌تر از بهترین مسیر دوره‌ای نخواهد بود. او در این مسیر یکی از مشهورترین الگوریتم‌های تقریبی در علوم نظری کامپیوتر را ابداع کرد؛ الگوریتمی که معمولا در کتاب‌ها و دوره‌های آموزشی یکی از اولین مثال‌ها است.

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

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

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

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

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

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

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

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

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

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