14 نوامبر 2022 -توسط دانشگاه کپنهاگ-اعتبار: Unsplash/CC0 دامنه عمومی
برای بیش از نیم قرن، محققان در سراسر جهان با یک مسئله الگوریتمی به نام “مسئله کوتاه ترین مسیر تک منبع” دست و پنجه نرم می کنند. مشکل اساساً در مورد چگونگی ابداع یک دستور ریاضی است که به بهترین وجه کوتاه ترین مسیر را بین یک گره و تمام گره های دیگر در یک شبکه پیدا کند، جایی که ممکن است ارتباط هایی با وزن های منفی وجود داشته باشد.
پیچیده است؟. اما در واقع، این نوع محاسبه در حال حاضر در طیف گسترده‌ای از برنامه‌ها و فناوری‌هایی که برای یافتن راه‌های خود به آنها وابسته‌ایم استفاده می‌شود – برای مثال، Google Maps ما را در سراسر مناظر و شهرها راهنمایی می‌کند.
اکنون، محققان دپارتمان علوم کامپیوتر دانشگاه کپنهاگ موفق به حل مشکل کوتاهترین مسیر تک منبعی شده‌اند، معمایی که ده‌ها سال است که محققان و کارشناسان را سرگردان کرده است.
“ما الگوریتمی را کشف کردیم که مشکل را در زمان تقریبا خطی و به سریع ترین روش ممکن حل می کند. این یک مسئله الگوریتمی اساسی است که از دهه 1950 مورد مطالعه قرار گرفته است و در سراسر جهان تدریس می شود. این یکی از دلایلی بود که ما را به حل آن ترغیب کرد. استادیار کریستین ولف-نیلسن توضیح می دهد که به وضوح رها کردن یک مسئله الگوریتمی حل نشده را دشوار می داند.
محاسبات سریع تر برای مسیریابی خودروهای الکتریکی
سال گذشته، Wulff-Nilsen موفقیت دیگری در همان زمینه ایجاد کرد، موفقیتی که نتیجه‌ای را ایجاد کرد که به چگونگی یافتن کوتاهترین مسیر در شبکه‌ای که در طول زمان تغییر می‌کند، می‌پردازد. راه حل او برای معمای اخیر بر اساس آن کار است.
محقق فکر می‌کند که حل مشکل کوتاهترین مسیر تک منبع می‌تواند راه را برای الگوریتم‌هایی هموار کند که نه تنها به ماشین‌های الکتریکی کمک می‌کنند سریع‌ترین مسیر را از A به B در یک لحظه محاسبه کنند، بلکه این کار را به کم‌مصرف‌ترین روش انجام می‌دهند.
وولف-نیلسن توضیح می دهد:
“ما بعدی به موضوع اضافه می کنیم که الگوریتم های قبلی ندارند. این بعد به ما امکان می دهد به آنچه وزن های منفی می گوییم نگاه کنیم. یک مثال عملی از آن می تواند با اشاره به تپه های یک شبکه جاده ای باشد، که خوب است بدانیم آیا شما یک ماشین الکتریکی دارید که در حین حرکت در سراشیبی شارژ می شود.»
حقایقی در مورد مشکل کوتاهترین مسیر منبع تک
هدف از مشکل کوتاهترین مسیر منبع تک، یافتن کوتاهترین مسیرها از یک گره شروع معین به تمام گره های دیگر در یک شبکه است.
شبکه به صورت نموداری متشکل از گره ها و اتصالات بین آنها به نام یال نمایش داده می شود.
هر لبه یک جهت دارد (مثلاً می توان از آن برای نشان دادن جاده های یک طرفه استفاده کرد) و همچنین وزنی که نشان می دهد چقدر هزینه سفر در آن لبه است. اگر همه وزن‌های لبه غیرمنفی باشند، مشکل را می‌توان در زمان خطی با یک الگوریتم کلاسیک Dijkstra حل کرد.
نتیجه جدید مشکل را تقریباً در همان زمان الگوریتم دایکسترا حل می کند، اما وزن لبه های منفی را نیز امکان پذیر می کند.
کریستین ولف-نیلسن می‌گوید:
“در اصل، این الگوریتم می تواند برای هشدار دادن به بازیگران مانند بانک های مرکزی استفاده شود، اگر سفته بازان در مورد خرید و فروش ارزهای مختلف سفته بازی می کنند. بسیاری از این موارد امروزه با استفاده از کامپیوتر اتفاق می افتد. اما از آنجایی که الگوریتم ما بسیار سریع است، ممکن است قادر باشد که برای شناسایی حفره‌ها قبل از بهره‌برداری از آنها استفاده می‌شود.
این محقق تاکید می‌کند که سیستم‌هایی برای محاسبه ارز و مسیرهای ماشین‌های الکتریکی از قبل وجود دارد. اما حل مشکل کوتاهترین مسیر تک منبع به محققان این امکان را داده است که الگوریتمی عالی ایجاد کنند که شکست آن از نظر سرعت تقریباً غیرممکن است. در عین سادگی، استفاده از آن را برای نیازهای مختلف جامعه آسان می کند.
در ایالات متحده تجلیل شد
در واقع، کریستین وولف-نیلسن و همکارانش قبلاً توسط افرادی در سراسر جهان تماس گرفته اند تا به آنها تبریک بگویند و اطلاعات بیشتری در مورد نحوه انجام این کار بیابند.در همان زمان، مقاله تحقیقاتی که جزئیات کشف آنها را نشان می دهد، با “جایزه بهترین مقاله” در کنفرانس FOCS (بنیاد علوم کامپیوتر) در دنور، کلرادو مفتخر شده است.
کریستین ولف-نیلسن می گوید: «مردم از سراسر جهان در این کنفرانس شرکت می کنند تا بهترین نتایج ارائه شده را ببینند.
این تحقیق با همکاری کریستین ولف-نیلسن، از دپارتمان علوم کامپیوتر، Danupon Nanongkai از موسسه ماکس پلانک و همکار آمریکایی آنها، آرون برنشتاین از دانشگاه راتگرز، انجام شد.
این تحقیق در حال حاضر در arXiv موجود است.
