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