مسئله فروشنده دوره‌گرد در علم ریاضی با استفاده از هوش مصنوعی

خبرداری؟

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

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

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

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

حالا ممکن است چند راه مختلف وجود داشته باشد: برای مثال راه اول برای او ۲۰ قدم، راه دوم ۱۵ قدم، راه سوم ۱۲ قدم و راه چهارم ۱۸ قدم باشد. در نتیجه باید بفهمیم کدام ترتیب رفتن به خانه‌ها کوتاه‌ترین مسیر را می‌سازد.

این همان مسئله فروشنده دوره‌گرد (Traveling Salesperson Problem) است.

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

مثلا برای ۵ خانه شاید کار راحت باشد، ولی اگر ۱۰۰۰ شهر داشته باشیم، دیگر نمی‌شود همه مسیرهای ممکن را یکی ‌یکی امتحان کرد.

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

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

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

بی‌قراری همراه با خوش‌بینی

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

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

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

شایان اویس قرن هیچ‌گاه به ابزارهای آشنا رضایت نداده باشد و وقتی برای مدت زیادی از یک روش یکسان استفاده می‌کند، بی‌قرار می‌شود.

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

او در این مورد می‌گوید: اینکه می‌بینم بسیاری از دوستان قدیمی و اعضای خانواده‌ام رنج می‌کشند. کار کردن برایم سخت می‌شود.

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

اویس قرن در مورد مادرش می‌گوید: در دوره‌ای که او بزرگ می‌شد، فرهنگ این‌گونه بود که دخترها نباید وارد رشته ریاضیات شوند. او فرصت این کار را نداشت.

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

شایان به‌ویژه به برادرش شهاب نزدیک بود؛ کسی که علوم رایانه خوانده بود و در اواخر دهه ۱۳۶۸ در المپیاد جهانی رایانه، مسابقه‌ای در زمینه مهارت‌های ریاضی و برنامه‌نویسی، شرکت کرده بود. وقتی شایان وارد دوره راهنمایی شد، شهاب کتابی از معماهای ریاضی به او داد و شایان بلافاصله جذب آن شد.

شهاب به یاد می‌آورد که این کتاب جرقه‌ای در ذهنش ایجاد کرده بود تا خیلی، خیلی عمیق‌تر به مسائل بپردازد. شایان بعدها خودش نیز در المپیاد شرکت کرد و در سال ۱۳۸۲ مدال طلا گرفت.

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

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

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

در نهایت، تنها اندکی آشنایی با پژوهش کافی بود تا عشق اویس‌ قرن به ریاضیات دوباره زنده شود.

دور زدن‌ها و مسیرهای انحرافی

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

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

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

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

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

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

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

صابری می‌گوید: او به شیوه شاد و مؤدبانه خودش، در ۱۰ دقیقه اول جلسه توضیح می‌داد که چرا روشی که من پیشنهاد داده‌ام، احتمالا جواب نمی‌دهد. بعد در ۱۵ دقیقه باقی‌مانده درباره چیزی صحبت می‌کردیم که از نظر او روش درست بود.

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

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

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

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

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

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

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

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

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

آجر به آجر

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

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

او می‌گوید: فراز و نشیب‌های زیادی دارد که بیشترشان نشیب هستند. همیشه با خودتان فکر می‌کنید: آیا اصلا می‌توانم چیزی پیدا کنم که شکست نخورد؟

او به ندرت آن لحظه‌های «یافتم!» را تجربه می‌کند که در روایت‌های عامه‌پسند از پژوهش ریاضی فراوان دیده می‌شوند. در عوض، کار روی یک اثبات برای او شبیه ساختن یک خانه آجر به آجر است. راه‌های زیادی برای کنار هم قرار دادن قطعات وجود دارد و تنها زمانی که تقریبا کل بنا کامل شده است، می‌توانید مطمئن شوید که از نظر ساختاری استحکام دارد.

او می‌گوید: این آجرها را روی هم می‌گذارید. هیچ‌وقت نمی‌دانید دارید آن را به روش درست انجام می‌دهید یا خیر.

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

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

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

اویس‌ قرن می‌گوید برخی از بهترین افکارش زمانی به ذهنش می‌رسند که طبیعت او را احاطه کرده باشد.

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

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

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

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

اما دقیقا چگونه می‌توان چنین نمونه تصادفی‌ تولید کرد؟

واکنش زنجیره‌ای

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

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

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

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

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

در سال ۱۹۸۹ دانشمندان علوم کامپیوتر میلنا میهایل و اومش وازیرانی فرضیه مهمی درباره نمونه‌گیری از اشیای ریاضی مرتبط با درخت‌های پوشا مطرح کردند که به آنها پایه‌های ماتروید (matroid bases) گفته می‌شود. این مسئله کاربردهای فراوانی در علوم رایانه و فراتر از آن دارد.

آنها پیشنهاد کردند یک زنجیره مارکوف ساده می‌تواند این نمونه‌گیری را انجام دهد، اما نمی‌دانستند چگونه ثابت کنند این زنجیره مارکوف زمان ترکیب به اندازه کافی کوتاهی خواهد داشت.

سال‌ها پژوهشگران زیادی تلاش کردند این فرضیه را ثابت کنند، اما شکست خوردند.

اویس‌ قرن و اناری در سال ۲۰۱۸ با همکاری پژوهشگران جدید، همان ریاضیات جدید را ارائه کردند. آنها به همراه ریاضیدان سینتیا وینزانت، مسئله نمونه‌گیری از پایه‌های ماتروید را به زبان چندجمله‌ای‌ها ترجمه کردند؛ درست همان‌طور که اویس‌ قرن هنگام کار روی مسئله فروشنده دوره‌گرد انجام داده بود.

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

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

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

مسیر بازگشت

در اواخر سال ۲۰۱۸، درست زمانی که انقلاب در زمینه نمونه‌گیری تازه آغاز شده بود، اویس قرن از قبل برای چالش دیگری بی‌تاب شده بود. او تصمیم گرفت زمان آن رسیده است که به مسئله فروشنده دوره‌گرد بازگردد؛ همان مسئله‌ای که یک دهه قبل سفر فکری او را آغاز کرده بود.

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

اویس قرن در اواخر سال ۲۰۱۸، یک دهه پس از آنکه برای نخستین‌بار به این مسئله علاقه‌مند شده بود، به آن بازگشت.

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

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

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

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

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

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

روناهی می‌گوید: شایان توانایی فوق‌العاده‌ای برای بازی کردن دارد. مغزش می‌تواند مثل یک بچه کوچک سرگرم شود و همه‌چیز را ساده بگیرد.

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

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