انتشار: آبان 23، 1401
بروزرسانی: 27 خرداد 1404

محقق برای حل عالی معمای الگوریتمی دهه 1950 تحسین شد -- ScienceDaily

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

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

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

محاسبات سریع تر برای مسیریابی خودروهای الکتریکی

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

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

اکنون محققان دپارتمان علوم کامپیوتر دانشگاه کپنهاگ موفق به حل این مشکل شده اند مشکل کوتاه ترین مسیر منبع تکمعمایی که ده ها سال است محققان و کارشناسان را به خود مشغول کرده است.

در ایالات متحده تجلیل شد

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

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

منبع

کریستین ولف-نیلسن می گوید: «مردم از سراسر جهان در این کنفرانس شرکت می کنند تا بهترین نتایج ارائه شده را ببینند.

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

در همان زمان، مقاله تحقیقاتی که جزئیات کشف آنها را نشان می دهد، با "جایزه بهترین مقاله" در کنفرانس FOCS (بنیاد علوم کامپیوتر) در دنور، کلرادو مفتخر شده است. در کنار STOC، این کنفرانس معتبرترین کنفرانس در علم کامپیوتر نظری است. کنفرانس FOCS از 31 اکتبر تا 3 نوامبر 2022 برگزار شد.

"ما الگوریتمی را کشف کردیم که مشکل را در زمان تقریبا خطی و به سریع ترین روش ممکن حل می کند. این یک مسئله الگوریتمی اساسی است که از دهه 1950 مورد مطالعه قرار گرفته و در سراسر جهان آموزش داده شده است. این یکی از دلایلی بود که ما را به حل آن ترغیب کرد. استادیار کریستین ولف-نیلسن توضیح می دهد که به وضوح رها کردن یک مسئله الگوریتمی حل نشده را دشوار می داند.

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

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

محقق فکر می کند که حل مشکل کوتاه ترین مسیر تک منبع می تواند راه را برای الگوریتم هایی هموار کند که نه تنها به ماشین های برقی کمک می کنند سریع ترین مسیر A تا B را در یک لحظه محاسبه کنند، بلکه این کار را به کم مصرف ترین روش انجام می دهند.