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

پنج‌شنبه ۱ آبان ۱۳۹۹ - ۰۹:۴۰
مطالعه 6 دقيقه
مرجع متخصصين ايران
بالاخره دانشمندان علوم كامپيوتر موفق شدند راه‌حل‌هاي‌ تقريبي بهتري براي مسئله‌ي بهينه‌سازي فروشنده‌ي دوره‌گرد پيدا كنند؛ اين مسئله اغلب در تست محاسبات بهينه متخصصد دارد.
تبليغات

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

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

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

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

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

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

مسير كسري

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تبليغات
جديد‌ترين مطالب روز

هم انديشي ها

تبليغات

با چشم باز خريد كنيد
اخبار تخصصي، علمي، تكنولوژيكي، فناوري مرجع متخصصين ايران شما را براي انتخاب بهتر و خريد ارزان‌تر راهنمايي مي‌كند
ورود به بخش محصولات