محققان از بیش از ۵۰ سال پیش با مسئله‌ای الگوریتمی موسوم به «یافتن کوتاه‌ترین مسیر» روبه‌رو بودند و نمی‌توانستند راه‌حلی برای آن پیدا کنند. اما حالا گروهی از دانشمندان دانشگاه کپنهاگ توانسته‌اند به این معمای قدیمی پاسخ بدهند.
«کریستین وولف-نیلسن»، استادیار دپارتمان علوم کامپیوتر دانشگاه کپنهاگ می‌گوید حل مسئله یافتن کوتاه‌ترین مسیر نه تنها می‌تواند به هموار‌کردن راه برای الگوریتم‌هایی کمک کند که در مسیریابی از نقطه «الف» به «ب» در خودروهای برقی ایفای نقش می‌کنند، بلکه این کار را به بهینه‌ترین حالت ممکن از نظر مصرف انرژی انجام می‌دهند.
معمای الگوریتمی یافتن کوتاه‌ترین مسیر چیست؟
مسئله یافتن کوتاه‌ترین مسیر اساساً سؤالی در این رابطه است که چگونه باید دستورالعمل ریاضیاتی لازم برای یافتن کوتاه‌ترین مسیر بین یک گره و سایر گره‌های یک شبکه را که ممکن است ارتباطاتی با وزن منفی داشته باشد، تدوین کرد. این محاسبات همین حالا در اپ‌ها و فناوری‌های زیادی از جمله گوگل مپس استفاده می‌شوند تا در مسیریابی به ما کمک کنند.
وولف-نیلسن پارسال دستاورد دیگری در همین حوزه داشت که به کشف کوتاه‌ترین مسیر در شبکه‌ای که در طول زمان تغییر می‌کند، کمک می‌کرد. حالا راه‌حل جدید او بر مبنای همین تلاش‌ها ارائه شده است. در معمای الگوریتمی کوتاه‌ترین مسیر، شبکه به‌عنوان گرافی شامل گره‌ها و ارتباطات بین آن‌ها یا «لبه‌ها» تعریف می‌شود.
هر لبه یک جهت دارد (برای مثال می‌توان جاده‌های یک طرفه را در نظر گرفت) و وزن آن مشخص می‌کند که سفر‌کردن در آن لبه چقدر هزینه برمی‌دارد. اگر وزن تمام لبه‌ها غیر‌منفی باشد، مسئله با یک الگوریتم دایکسترا در یک زمان خطی حل می‌شود. حالا این راه‌کار جدید اجازه می‌دهد تا حتی در لبه‌های منفی هم در زمانی مشابه با الگوریتم دایکسترا بتوان مسئله را حل کرد.
وولف-نیلسن می‌گوید این الگوریتم می‌تواند به جاهایی مثل بانک‌های مرکزی نشان دهد که سفته‌بازها در حال سفته‌بازی پیرامون خرید و فروش یک ارز مشخص هستند یا نه: «خیلی از این کارها امروز با کامپیوتر انجام می‌شود، اما الگوریتم ما چنان سریع است که احتمالاً بتواند برای شناسایی حفره‌های امنیتی پیش از اینکه مورد سوءاستفاده قرار بگیرند، استفاده شود.»
محققان می‌گویند همین حالا سیستم‌هایی وجود دارند که می‌توانند تخلف در بازار ارز را شناسایی یا مسیر حرکت خودروها را مشخص کنند، اما راه‌کار آن‌ها از نظر سرعت از همه راه‌حل‌های قبلی بهتر عمل می‌کند. از سوی دیگر، سادگی این راه‌کار باعث می‌شود بتوان از آن برای حوزه‌های گوناگون استفاده کرد.
نتایج مطالعات دانشمندان در پایگاه داده arXiv در دسترس قرار گرفته است.
<دیجیاتو / منبع
