یک الگوریتم جدید برای تقاطع گراف‌ها

منتشرشده در QuantaMagazine به تاریخ ۱۵ سپتامبر ۲۰۲۰
لینک مقاله اصلی: A New Algorithm for Graph Crossings, Hiding in Plain Sight

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

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

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

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

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

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

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

برای اینکه متوجه شویم نمی‌شود این کار را کرد، خیلی طول نمی‌کشد.

اما اینکه گراف‌های پیچیده‌تر مسطح هستند یا نه، همیشه انقدر واضح نیست.

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

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

هلم گفت: « [ این کار ] خیلی بهتر از این است که هر بار از صفر شروع کنیم، اما واقعا خوب نیست.»

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

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

برای مثال، شما می‌توانید تصویر A را با برگرداندن مثلث ایجاد شده توسط گره‌های ۱، ۲ و ۳ بر روی یال متصل‌کننده گره‌های ۲ و ۳ به تصویر B تغییر دهید. بخش بالایی ترسیم B نیز می‌تواند برای تولید ترسیم C بر روی گره‌های ۴ و ۵ قرینه شود. طرح‌ها متفاوت به نظر می‌رسند، اما همان گراف هستند.

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

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

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

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

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

روتنبرگ توضیح داد: «ما این را الگوریتم تنبل-حریص (lazy-greedy) می‌نامیم. این الگوریتم تنها تغییرات لازم برای تطبیق دادن یال را انجام می‌دهد.»

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

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

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

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

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