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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



منبع

Matthew Newman

Matthew Newman Matthew has over 15 years of experience in database management and software development, with a strong focus on full-stack web applications. He specializes in Django and Vue.js with expertise deploying to both server and serverless environments on AWS. He also works with relational databases and large datasets
[ Back To Top ]