سوپرمارکت را جارو کن (supermarket sweep) اسم یک بازی-شوی تلویزیونی آمریکایی بود که از سال ۱۹۶۵ تا سال ۲۰۲۲ از شبکههای مختلف آمریکایی پخش میشد. در این برنامه، شرکت کنندگان در گروههای مختلف، به یک سری سوالات پاسخ میدادند و بسته به پاسخ صحیحشان، میتوانستند زمان کوتاهی مثلا یک دقیقه وارد یک سوپرمارکت شوند و هرچیزی که میخواهند را در همان یک دقیقه بردارند و از سوپرمارکت خارج شوند. آنوقت گروهی که میتوانست در مجموع اجناس با ارزشتری را بردارد، برنده میشد. مثلا اگر قیمت اجناسی که یک گروه برداشته بود، ۱۰۰ دلار و قیمت اجناس گروه دیگر ۲۰۰ دلار میشد، گروه دوم برنده میشد.
در خلال این سالها، ورژنهای مختلفی از این بازی روی آنتن رفت، اما شمای کلی این بازی به همین شکل بود. البته اکنون نمیخواهم به کار ضدفرهنگی این برنامه و تشویق به مصرفگرایی و مضرات مصرفگرایی بپردازم. این بازی شباهت زیادی به یک مسالهی معروف و دشوار ریاضی دارد و از همین بابت این مثال جالب را آوردم. ویدئوی زیر یکی از قسمتهای این شو تلویزیونی را نشان میدهد.
اجازه دهید به این بازی به چشم یک مساله نگاه کنیم. شاید در ابتدا فکر کنید که این بازی، خیلی راحت است و فقط نیاز به آمادگی جسمانی و سرعت بالا دارد. اما راستش را بخواهید، حل این مساله بیشتر از آمادگی جسمانی، نیاز به آمادگی ذهنی و قدرت حل مساله دارد و به حجم بالایی از پردازش نیاز دارد. شاید خود شرکت کنندگان هم این موضوع را نفهمند، اما اگر مساله به یک کامپیوتر و الگوریتم داده شود، آنوقت مشخص میشود که این شرکت کنندگان گیر چه مسالهی سختی افتاده اند. افراد شرکت کننده در این بازی در واقع باید سه پارامتر را مدنظر داشته باشند.
اول اینکه هرکدام از آنها یک چرخ دستی دارند و این چرخ دستی حجم محدودی دارد. پس پارامتر محدودکنندهی اول حجم است. از آنجایی که فضای چرخدستی محدود است، آنها نمیتوانند کل سوپرمارکت را داخل چرخ بگذارند و خارج شوند. پس آنها ناچارند که اجناسی را پیدا کنند که بیشترین قیمت و کمترین حجم را دارد.
پس پارامتر دوم قیمت است. آنها اگر بتوانند در این فروشگاه خاویار یا زعفران پیدا کنند، پیدا کردن پاسخ شاید کمی راحتتر باشد. اما آنها که از قبل خبر ندارند که این فروشگاه چه دارد و چه ندارد؟ پس آنها باید در فروشگاه دور بزنند و یکی یکی اجناس را ببینند. اما آنها با محدودیت زمان روبرو هستند. چون پردازش هر آیتم داخل فروشگاه زمانی نیاز دارد، ما میتوانیم زمان را به مرحله (step) ترجمه کنیم. شرکت کنندهی بخت برگشته باید در کمترین تعداد مراحل، گرانترین اجناس با کمترین حجم را پیدا کند. این پاسخ یک پاسخ بهینه یا optimum است. اما او در هر مرحله ناچار است هر کالا را دوباره با کالاهای قبلی چک کند. مثلا وقتی دارد آیتم صدم را نگاه میکند، باید آن را با نود و نه آیتم قبلی نیز مقابسه کند و به همین ترتیب برای آیتم صد و یکم الی آخر.
این مساله در علوم کامپیوتر تحت عنوان مسالهی کوله پشتی (knapsack problem) شناخته میشود که ذیل دستهای از مسائل تحت عنوان مسائل ان پی هارد قرار میگیرد. یعنی بهترین الگوریتمی که ما بتوانیم پیدا کنیم، میتواند در تعداد مراحل نمایی این مساله را حل کند و باز هم مشخص نیست که آیا راه حلی که میدهد بهترین راه حل است یا راه حل بهتری هم وجود دارد. برای همین مساله اگر فروشگاه سایز متوسطی داشته باشد، راه حل گفته شده برای یافتن بهینهترین پاسخ، ممکن است چند میلیارد سال به درازا بیانجامد.
– ابا اباد