دانشمندان علوم کامپیوتر موفق به کشف طولانی‌ترین مسیر دریایی برای کشتی‌رانی شدند

مسئله‌ای که از سال‌ها پیش در وبسایت Reddit مطرح شده بود، نهایتا حل شد. این مسئله به دنبال یافتن طولانی‌ترین مسیر مستقیمی است که امکان کشتی‌رانی در جهان را بدون برخورد به خشکی فراهم می‌نماید. با نگاهی به تصویر زیر کاملا روشن است که این مسیرها یک خط مستقیم نیستند.

به خاطر داشته باشید که خطوط مستقیم نمایش داده شده روی نقشه‌های مسطح در فضای کروی زمین به شکل منحنی مشاهده می‌شوند. روهان چابوکوار از مرکز تحقیقاتی United Technologies در ایرلند و کاشال موخرجی از موسسه تحقیقاتی IBM در هند، الگوریتمی را توسعه داده‌اند که توانایی محاسبه طولانی‌ترین مسیر مستقیم روی خشکی یا دریا را دارد. این ۲ محقق نتایج فعالیت خود را ارایه کرده‌اند.

این الگوریتم از تکنیکی موسوم به انشعاب و تحدید (branch and bound) استفاده می‌کند. در این روش کلیه راه‌حل‌های بالقوه در قالب شاخه‌هایی از یک درخت در نظر گرفته می‌شوند. سپس الگوریتم شاخه‌ها را یکی پس از دیگری مورد بررسی قرار خواهد داد. فرآیند به منظور کاهش بار کاری مورد نیاز پروسه انشعاب اجرا می‌شود. این الگوریتم اساسا کلیه راه‌حل‌های ممکن در یک شاخه را بررسی نموده و در جهت یافتن یک زیرمجموعه نزدیک‌تر به مقادیر بهینه تلاش می‌کند. در صورتی که انشعاب به راه‌حل بهینه نزدیک نباشد، کاملا نادیده گرفته می‌شود. ۲ محقق ادعا کردند که الگوریتم آن‌ها با انجام محاسبات حدودا ۱۰ دقیقه‌ای موفق به یافتن طولانی‌ترین مسیر آبی شده است. یافتن طولانی‌ترین مسیر خشکی وقت‌گیرتر بوده و به ۴۵ دقیقه زمان نیاز دارد. هر ۲ مسیر با اجرای الگوریتم بر روی یک لپ‌تاپ معمولی پیدا شدند.

جالب این است که مسیر آبی کشف شده توسط الگوریتم تقریبا مشابه مسیری است که یکی از کاربران وبسایت Reddit، ادعای یافتن آن‌ را در سال ۲۰۱۲ مطرح کرده بود. مسیر ترسیم شده توسط محققان، طولی معادل ۳۲۰۸۹.۷ کیلومتر دارد. طولانی‌ترین مسیر خشکی نیز از ۱۵ کشور جهان عبور کرده و ۱۱۲۴۱.۱ کیلومتر طول دارد.