محققان سریع ترین الگوریتم جریان ممکن را توسعه می دهند

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

محاسبات به سرعت یک شبکه بزرگ است

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

رویکرد کینگ این مشکل را برطرف می کند: با استفاده از الگوریتم او، زمان محاسبات و اندازه شبکه با سرعت یکسان افزایش می یابد - کمی شبیه به پیاده روی و ادامه دادن مداوم همان سرعت هر چقدر که مسیر شیب دار باشد. نگاهی اجمالی به ارقام خام نشان می دهد که تا چه حد پیش رفته ایم: تا پایان هزاره، هیچ الگوریتمی موفق به محاسبه سریع تر از متر^1.5، کجا متر مخفف تعداد اتصالات در یک شبکه است که کامپیوتر باید محاسبه کند و فقط یک بار خواندن داده های شبکه طول می کشد متر زمان در سال 2004، سرعت محاسبات مورد نیاز برای حل مشکل با موفقیت به کاهش یافت متر^1.33. با استفاده از الگوریتم کینگ، زمان محاسباتی "اضافی" مورد نیاز برای رسیدن به راه حل پس از خواندن داده های شبکه اکنون ناچیز است.

مثل پورشه ای که با کالسکه اسبی مسابقه می دهد

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

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

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

الگوریتم های رعد و برق سریع برای تغییر شبکه ها

روز پنجشنبه، Simon Meierhans - یکی از اعضای تیم کینگ - یک الگوریتم تقریبا خطی جدید را در سمپوزیوم سالانه ACM در نظریه محاسبات (STOC) در ونکوور ارائه کرد. این الگوریتم مسئله حداقل هزینه جریان حداکثر را برای شبکه هایی که با اضافه شدن اتصالات جدید به تدریج تغییر می کنند، حل می کند. علاوه بر این، در مقاله دوم که توسط سمپوزیوم IEEE در مبانی علوم رایانه (FOCS) در اکتبر پذیرفته شد، محققان ETH الگوریتم دیگری را توسعه دادند که همچنین اتصالات حذف شده را کنترل می کند.

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

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

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

کل را محاسبه کنید؟ یا قطعاتش؟

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

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

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

سریع و گسترده

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

تغییر دیدگاه از راه آهن به برق

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

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

نقطه عطفی در اصول نظری

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

با این حال، پایه گذاری برای حل مسائل بسیار بزرگی که قبلاً نمی توانستند به طور مؤثر محاسبه شوند، تنها یکی از مزایای این الگوریتم های جریان بسیار سریع تر است - زیرا آنها همچنین روش محاسبه وظایف پیچیده را در وهله اول تغییر می دهند. یک گروه بین المللی از محققان دانشگاه کالیفرنیا در برکلی می نویسد: «در طول دهه گذشته، انقلابی در مبانی نظری برای به دست آوردن الگوریتم های سریع قابل اثبات برای مسائل اساسی در علوم کامپیوتر نظری رخ داده است. Deeksha Adil، محقق در موسسه مطالعات نظری در ETH زوریخ.