به گزارش ایسنا، در علوم رایانه نظری، کلید حل مسائل دشوار، پیدا کردن ابزارهای مناسب است. بیشتر پژوهشگران به سمت ابزارهایی گرایش پیدا میکنند که با مسائلی که امیدوارند حل کنند، تناسب داشته باشد و برخی نیز تمام دوران حرفهای خود را صرف تسلط بر چند روش آشنا میکنند. اما شایان اویس قرن، دانشمند علوم رایانه در دانشگاه واشنگتن در سیاتل، هیچگاه به ابزارهای آشنا رضایت نداده است. وقتی برای مدت زیادی از یک روش یکسان استفاده میکند، بیقرار میشود.
اویس قرن نه تنها از نظر فکری، بلکه از نظر فیزیکی نیز ظاهرا در یک جا ماندن برایش دشوار است. وقتی درباره پژوهشهایش صحبت میکنید، هرچه هیجانش بیشتر میشود، از یک وضعیت نشستن به وضعیت دیگری تغییر حالت میدهد؛ ابتدا چهارزانو روی یک صندلی راحتی مینشیند، سپس زانوهایش را در آغوش میگیرد و بعد به پهلو میچرخد و پاهایش را روی دسته صندلی میاندازد.
شاید از این رو منطقی باشد که اویس قرن به دلیل فعالیتهایش روی «مسئله فروشنده دورهگرد» شناخته شده است؛ مسئلهای محاسباتی و بسیار دشوار درباره حرکت از مکانی به مکان دیگر. او همچنین در زمینهای ظاهرا بیارتباط با این مسئله، یعنی یافتن بهترین روش برای انتخاب تصادفی از میان مجموعه بزرگی از اشیای ریاضی، دستاوردهای مهمی داشته است.
برای آنکه درک بهتری از مسئله فروشنده دورهگرد داشته باشید، فرض کنید یک پستچی باید به خانهها سر بزند و بعد به خانه خودش بازگردد. اما یک مشکل دارد: میخواهد کوتاهترین مسیر ممکن را پیدا کند تا کمتر راه برود.
حالا ممکن است چند راه مختلف وجود داشته باشد: برای مثال راه اول برای او ۲۰ قدم، راه دوم ۱۵ قدم، راه سوم ۱۲ قدم و راه چهارم ۱۸ قدم باشد. در نتیجه باید بفهمیم کدام ترتیب رفتن به خانهها کوتاهترین مسیر را میسازد.
این همان مسئله فروشنده دورهگرد (Traveling Salesperson Problem) است.
نکته جالب اینجاست که وقتی تعداد خانهها خیلی زیاد شود، تعداد مسیرهای ممکن خیلی خیلی زیاد میشود و پیدا کردن بهترین مسیر برای رایانه هم دشوار میشود.
مثلا برای ۵ خانه شاید کار راحت باشد، ولی اگر ۱۰۰۰ شهر داشته باشیم، دیگر نمیشود همه مسیرهای ممکن را یکی یکی امتحان کرد.
پس دانشمندان …