اَبا اِباد

مساله‌ی فروشنده‌ی دوره‌گرد

الگوریتم تقریبی برای مساله فروشنده دوره گرد

شنیده‌اید می‌گویند آدم نباید فقط جلوی پایش را ببیند؟ منظورشان این است که آدم باید حواسش به آینده هم باشد و تصمیماتش را با لحاظ کردن آینده اتخاذ کند. یک عده هم می‌گویند آدم باید در لحظه زندگی کند و باید دم را غنیمت بشمارد. مثلا نظر خیام اینچنین است آنجا که می‌گوید: ♡ روزی که گذشت هیچ از او یاد مکن/فردا که نیامده‌ست فریاد مکن/‎بر نامده و گذشته بنیاد مکن/حالی خوش باش و عمر بر باد مکن♡

البته در دنیای مدرن هم توجه ویژه‌ای به این فلسفه و این نگاه شده است و انسان امروز خواه ناخواه به اخذ چنین رویکردی تشویق و حتی سوق داده می‌شود. اما واقعا کدام رویکرد درست است؟

طرفداران آن ایده‌ی آینده نگر می‌گویند آدمی که به فکر آینده نباشد و همواره پی عشق و حال باشد، بالاخره با فرارسیدن آینده سرش به سنگ می‌خورد.

طرفداران ایده‌ی خیام هم فلسفه‌شان را بر عدم قطعیت جهان استوار می‌کنند که آدم از کجا خبر‌ دارد که یک دقیقه‌ی بعد همچنان زنده است و‌ نفس می‌کشد یا این سلامتی و خوشی اکنون را همچنان دارد؟

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

حالا با این تفاسیر، باید استدلال کدام دسته را پذیرفت؟ آینده نگری یا زندگی در حال یا تعادل بین این دو؟

اما من در اینجا قصد دارم این سوال را از یک سوال فلسفی به یک سوال ریاضیاتی تبدیل کنم. مساله‌ی فوق در واقع یک مساله‌ی بهینه‌سازی‌ست. یعنی ما می‌خواهیم ببینیم راه حل اوپتیموم و بهینه‌ی این مساله چیست که هم از زندگی لذت ببریم و هم آینده را از دست ندهیم به طوریکه نه سیخ بسوزد نه کباب. یک مساله‌ی معروف در علوم کامپیوتر که یکی از شاخه‌های ریاضیات است وجود دارد که کمابیش شبیه همین مساله است. اسم این مساله، مساله‌ی فروشنده‌ی دوره‌گرد است. فرض کنید یک فروشنده می‌خواهد به تمام مراکز استان‌های ایران سر بزند. اما زمان محدود است و بنزین گران است و استهلاک خودرو هم بالاست. پس این فروشنده باید به این فکر کند که شهرها را به ترتیبی سر بزند که کمترین مسافت را طی کند و در عین حال به تمام مراکز استان‌ها نیز سر زده باشد. ظاهرا مساله‌ی ساده‌ایست، اما راستش این مساله بسیار پیچیده است. تعداد حالات ممکن در این مساله در حد ده بتوان ۳۲ حالت است.

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

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

– ابا اباد

دیدگاه‌ خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *