الگوریتمهای روزمره: از دستور پخت تا مسیریابی
جواب کوتاه
خیلی از کارهای روزمره، الگوریتمهای واقعیان که اسم دارن و توی کامپیوترها هم به کار میرن. پوشیدن جوراب پیش از کفش، مرتبسازی بر اساس وابستگیه. چیدن ورقها توی دست، مرتبسازی درجیه. پیدا کردن اسم توی دفترچه با نصف کردن، جستجوی دودوییه. صف نونوایی، ساختمان دادهی صفه. انتخاب کوتاهترین راه، الگوریتم کوتاهترین مسیره. پر کردن چمدون با بیشترین چیز بهدردبخور، مسئلهی کولهپشتیه. آسانسوری که اول همهی طبقههای بالا رو میره و بعد پایین میاد، یه الگوریتم زمانبندیه. شناختن اینها، الگوریتم رو از یه چیز انتزاعی به یه چیز آشنا تبدیل میکنه.
یه روز معمولی، پر از الگوریتم
صبح بیدار میشید، لباس میپوشید، کلیدتون رو پیدا میکنید، توی صف نونوایی میایستید، کوتاهترین راه رو تا سر کار انتخاب میکنید و عصر، توی سوپرمارکت، صف کوتاهتر رو. هیچکدوم از اینها رو «الگوریتم» نمیدونید؛ ولی پشت تکتکشون یه الگوریتم واقعی هست که اسم داره و کامپیوترها هم هر روز اجراش میکنن.
این درس، یه روز معمولی رو از صبح تا شب دنبال میکنه و برای هر کار، اسم الگوریتمش رو میگه. هدف این نیست که چیزی رو حفظ کنید؛ هدف اینه که دفعهی بعد که توی درسهای این مسیر به «مرتبسازی درجی» یا «جستجوی دودویی» رسیدید، بگید: «آهان، این همونیه که هر روز انجام میدم». توی درس قبل دیدیم الگوریتم دقیقا چیه.
دستور پخت: الگوریتم با چند آشپز
دستور پخت، معروفترین مثال الگوریتمه؛ با یه تفاوت که توی درس قبل دیدیم: «نمک به اندازه» دقیق نیست. ولی یه نکتهی جالبتر هم توی آشپزی هست: بعضی قدمها رو میشه همزمان انجام داد. وقتی برنج دم میکشه، میشه سالاد رو آماده کرد. یه آشپز باتجربه، ترتیب کارها رو طوری میچینه که هیچوقت بیکار نمونه.
به این ایده، همزمانی (Concurrency) میگن، و کامپیوترها هم دقیقا همین کار رو میکنن: وقتی یه برنامه منتظر رسیدن داده از اینترنته، پردازنده کار دیگهای انجام میده. یه مهمونی شام، یعنی چند الگوریتم کوچیک که باید همزمان و با زمانبندی درست اجرا بشن، تا همهی غذاها با هم آماده بشن.
لباس پوشیدن: ترتیب وابستگی
هیچکس اول کفش نمیپوشه و بعد جوراب. چون بعضی کارها به کارهای دیگه وابستهان: جوراب پیش از کفش، زیرپوش پیش از پیراهن، شلوار پیش از کمربند. ولی بعضیها وابستگی ندارن؛ ساعت رو میشه هر وقت بست. پیدا کردن یه ترتیب که همهی وابستگیها رو رعایت کنه، یه الگوریتم معروف داره: مرتبسازی توپولوژیک (Topological Sort).
کامپیوترها این الگوریتم رو همهجا اجرا میکنن: وقتی یه برنامه رو نصب میکنید، اول کتابخونههایی نصب میشن که برنامه بهشون وابستهست. وقتی یه پروژهی ساختمونی برنامهریزی میشه، اول پی، بعد دیوار، بعد سقف. هر جا «این باید پیش از اون باشه» هست، این الگوریتم هم هست.
کلید گمشده: جستجو
کلیدتون گم شده. یه راه اینه که کل خونه رو گوشه به گوشه بگردید؛ مطمئن ولی کند. راه بهتر اینه که اول جاهای محتملتر رو بگردید: جیب کت دیروز، کنار در، روی میز آشپزخونه. این دو راه، دو استراتژی جستجوان: جستجوی کامل، و جستجو با اولویت احتمال.
یه نکتهی جالب دیگه: آدمها معمولا یه جا رو چند بار میگردن، چون یادشون نمیمونه کجاها رو دیدن. کامپیوترها برای همین، یه فهرست از جاهای دیدهشده نگه میدارن. و بهترین الگوریتم کلید گمشده؟ ساختمان دادهی درست: یه جای ثابت کنار در، که جستجو رو از کل خونه به یه قدم برسونه.
بازی بیست سوالی: نصف کردن
توی بازی بیست سوالی، یه نفر یه چیزی رو توی ذهنش نگه میداره و بقیه با سوالهای بله و نه حدسش میزنن. بازیکن خوب، سوالهایی میپرسه که جوابها رو تقریبا نصف کنه: «زندهست؟»، «از گربه بزرگتره؟». بازیکن تازهکار، میپرسه «گربهست؟» و با جواب نه، تقریبا هیچی یاد نمیگیره.
این، روح جستجوی دودوییه. با هر سوالی که دقیقا نصف کنه، بیست سوال کافیه تا از میون حدود یه میلیون چیز، یکی رو پیدا کنید؛ چون دو به توان بیست، حدود یه میلیونه. همین ایده، توی ایستگاه جستجو کامل میشه.
دفترچه تلفن: جستجوی دودویی
توی درس اول دیدیم که برای پیدا کردن یه اسم توی دفترچهی مرتب، میشه از وسط باز کرد و نصف رو کنار گذاشت. این، جستجوی دودویی (Binary Search) ـه؛ یکی از پرکاربردترین الگوریتمهای دنیا. شرطش هم یه چیزه: داده باید مرتب باشه.
کامپیوترها هر روز میلیاردها بار این کار رو میکنن: پیدا کردن یه کاربر بین میلیونها، یه کلمه توی فرهنگ لغت گوشی، یا یه فایل بین هزاران. هر بار که میبینید یه جستجو بین دادهی خیلی بزرگ، تقریبا فوری جواب میده، احتمالا یه نسخه از همین ایده پشتشه.
فرهنگ لغت: حدس زدن جای کلمه
وقتی کلمهای مثل «زنبور» رو توی یه فرهنگ لغت کاغذی دنبال میکنید، از وسط باز نمیکنید؛ میدونید «ز» حدود یهسوم کتابه و همونجا رو باز میکنید. این از جستجوی دودویی هم زیرکانهتره: به جای نصف کردن کور، از دونستن پخش داده، جای تقریبی رو حدس میزنید.
به این، جستجوی درونیابی (Interpolation Search) میگن. وقتی داده یکنواخت پخش شده باشه، از دودویی هم سریعتره؛ ولی اگه پخش نامنظم باشه، مثل دفترچهای که نصف اسمهاش با «م» شروع میشه، ممکنه کندتر بشه. همین بدهبستون، درس همیشگی این مسیره.
چیدن ورقها توی دست: مرتبسازی درجی
وقتی توی بازی ورق، کارتها رو یکییکی برمیدارید، هر کارت تازه رو سر جای درستش بین کارتهای مرتبشدهی توی دستتون میذارید. بقیه رو کمی کنار میزنید و کارت رو وسطشون جا میدید. این، دقیقا الگوریتم مرتبسازی درجی (Insertion Sort) ـه.
این الگوریتم برای چند کارت عالیه و برای دادهای که تقریبا مرتبه، خیلی سریع. ولی برای هزاران کارت قاطی، کند میشه؛ چون هر کارت تازه ممکنه مجبور بشه از کنار خیلیها رد بشه. جالبه که خیلی از زبانهای برنامهنویسی، برای تکههای کوچیک داده، هنوز همین الگوریتم رو به کار میبرن.
لباسها پیش از شستن: دستهبندی
پیش از شستن، لباسها رو دسته میکنید: سفیدها، رنگیها، تیرهها. لازم نیست کل لباسها رو با هم مقایسه کنید؛ هر لباس رو نگاه میکنید و توی سبد درست میندازید. یه بار گشتن کافیه. به این ایده، مرتبسازی سطلی (Bucket Sort) میگن.
این روش وقتی خیلی سریعه که دستهها از قبل معلوم باشن و تعدادشون کم باشه. ادارهی پست هم همین کار رو با نامهها میکنه: هر نامه رو بر اساس شهر، توی یه کیسه میندازه؛ بعد هر کیسه رو جدا بر اساس محله. کامپیوترها هم برای مرتب کردن عددها توی بازههای مشخص، از نسخههای همین ایده استفاده میکنن.
جفت کردن جورابها: هش
بعد از شستن، باید جورابها رو جفت کنید. راه کند: هر جوراب رو برداری و کل تپه رو دنبال جفتش بگردی. راه سریع: جورابها رو یکییکی برداری و روی میز، هر رنگ رو یه جای مشخص بذاری؛ وقتی جوراب تازهای اومد، مستقیم میری سراغ جای رنگش و ببینی جفتش اونجا منتظره یا نه.
این، روح جدول هش (Hash Table) ـه: یه قاعده که از خود چیز، جاش رو تعیین میکنه، تا پیدا کردنش تقریبا یه قدم باشه. کامپیوترها همین ایده رو برای پیدا کردن سریع کاربر با نام کاربری، یا کلمه توی یه متن بزرگ، به کار میبرن. ایستگاه هفتم این مسیر، کامل دربارهی همینه.
صف نونوایی: اول اومده، اول رفته
توی صف نونوایی، هر کسی زودتر اومده، زودتر نون میگیره. به این قاعده، اولورودی اولخروجی میگن، و ساختمان دادهای که این رو نگه میداره، صف (Queue) ـه. منصفانهست، سادهست، و برای هر جایی که چند کار منتظر نوبتن، مناسبه.
کامپیوترها پر از صفن: صف چاپگر که برگهها رو به ترتیب چاپ میکنه، صف پیامهایی که منتظر فرستادنن، و صف درخواستهایی که به یه سایت میرسن. وقتی یه سایت از شلوغی کند میشه، معمولا یعنی صفش بلند شده؛ همون حسی که توی یه صف طولانی نونوایی دارید.
بشقابهای روی هم: آخر اومده، اول رفته
توی آشپزخونه، بشقابها روی هم چیده میشن. آخرین بشقابی که شسته و روی دسته گذاشتید، اولین بشقابیه که برمیدارید. این برعکس صفه: آخرورودی اولخروجی، و ساختمان دادهش پشته (Stack) ـه.
شاید فکر کنید پشته کمکاربرده؛ ولی هر بار که دکمهی «برگشت» مرورگر یا «بازگردانی» یه ویرایشگر رو میزنید، دارید از یه پشته استفاده میکنید: آخرین صفحه یا آخرین کاری که انجام دادید، اولین چیزیه که برمیگرده. ایستگاه ششم، صف و پشته رو کنار هم نشون میده.
کدوم صف سوپرمارکت؟
توی سوپرمارکت سه صندوق هست و باید یکی رو انتخاب کنید. بیشتر آدمها کوتاهترین صف رو انتخاب میکنن؛ ولی آدمهای باتجربه، تعداد سبدهای پر رو هم میشمرن. صفی با سه نفر که هر کدوم یه سبد پر دارن، ممکنه از صفی با شش نفر که هر کدوم یه نون دارن، کندتر باشه.
یه کشف جالب از ریاضی صفها هم این بوده که یه صف مشترک برای چند صندوق، مثل خیلی از بانکها، معمولا منصفانهتر و قابل پیشبینیتر از چند صف جداست؛ چون دیگه یه مشتری کند، فقط پشتسریهاش رو معطل نمیکنه. سرورهای اینترنت هم برای تقسیم درخواستها، همین سوال رو حل میکنن.
راه سر کار: کوتاهترین مسیر
برای رسیدن به سر کار، چند راه دارید: یکی کوتاهتر ولی پرترافیک، یکی بلندتر ولی خلوت. اپ نقشه، خیابونها رو به شکل یه گراف میبینه: نقطهها، یعنی تقاطعها، و خطها، یعنی خیابونها، که هر کدوم یه وزن دارن، مثل زمان رد شدن. بعد با یه الگوریتم کوتاهترین مسیر، مثل الگوریتم دایجسترا، بهترین راه رو پیدا میکنه.
نکتهی جالب اینه که «کوتاهترین» همیشه یعنی کوتاهترین فاصله نیست؛ میتونه کمترین زمان، کمترین هزینهی سوخت یا کمترین تعداد چراغ قرمز باشه. الگوریتم یکیه؛ فقط وزن خطها عوض میشه. ایستگاه گراف، این الگوریتم رو قدمبهقدم نشون میده.
بستن چمدون: مسئلهی کولهپشتی
برای یه سفر، یه چمدون دارید با جای محدود، و کلی چیز که میخواید ببرید، هر کدوم با یه اندازه و یه ارزش. کدومها رو ببرید که بیشترین ارزش توی چمدون جا بشه؟ این، یکی از معروفترین مسئلههای علوم کامپیوتره: مسئلهی کولهپشتی (Knapsack Problem).
راه سادهای که بیشتر آدمها میرن، اینه که چیزهایی رو اول بذارن که نسبت به جاشون ارزش بیشتری دارن. این روش، که اسمش حریصانهست، معمولا جواب خوبی میده ولی نه همیشه بهترین. پیدا کردن بهترین جواب دقیق، وقتی تعداد چیزها زیاد باشه، میتونه خیلی سخت بشه؛ همون جایی که الگوریتمها به مرزشون میرسن.
برنامهریزی روز: اول کدوم کار؟
یه روز پرکار دارید، با چند کار که هر کدوم یه مهلت دارن. یه قاعدهی ساده که ریاضیدانها ثابت کردن برای کم کردن بیشترین تاخیر خیلی خوب کار میکنه: کارها رو به ترتیب نزدیکترین مهلت انجام بدید. به این، اولزودترینمهلت (Earliest Deadline First) میگن.
ولی اگه هدف عوض بشه، الگوریتم هم عوض میشه. اگه بخواید بیشترین تعداد کار رو تموم کنید، شاید بهتر باشه کارهای کوتاه رو اول انجام بدید. سیستمعاملها هم هر لحظه همین تصمیم رو بین برنامهها میگیرن. و این، یه یادآوری مهمه: «بهترین» الگوریتم، به اینکه دقیقا چی رو میخواید بهتر کنید، بستگی داره.
آسانسور: بالا، بعد پایین
توی یه ساختمون بلند، آسانسور درخواستهای زیادی میگیره: طبقهی سه میخواد بره بالا، طبقهی نه پایین، طبقهی پنج بالا. اگه آسانسور به ترتیب درخواستها حرکت کنه، مدام بالا و پایین میره و همه معطل میشن. راه بهتر: تا وقتی کسی بالاتر کار داره، بالا برو و همه رو سر راه سوار و پیاده کن؛ بعد برگرد پایین.
به این، الگوریتم آسانسور یا اسکن (SCAN) میگن، و جالبه که قبلا هارد دیسکهای کامپیوتر هم برای حرکت دادن سوزن خوندنشون، دقیقا همین الگوریتم رو به کار میبردن. یه مسئلهی زمانبندی، دو دنیای کاملا متفاوت.
چراغ راهنمایی: یه چرخهی ساده
چراغ راهنمایی یه الگوریتم سادهی تکراریه: سبز، زرد، قرمز، و از اول. ولی چراغهای هوشمندتر، با حسگر، شلوغی هر طرف رو میسنجن و زمان سبز رو بر اساسش عوض میکنن. و توی شهرهای بزرگ، چراغهای پشت سر هم با هم هماهنگ میشن تا ماشینها بتونن پشت سر هم از چند چراغ سبز رد بشن.
این مثال نشون میده یه الگوریتم چطور از ساده به هوشمند رشد میکنه: اول یه چرخهی ثابت، بعد با ورودی تازه، یعنی حسگر، و بعد با هماهنگی بین چند الگوریتم. خیلی از نرمافزارهای واقعی همین مسیر رو طی میکنن.
تقسیم منصفانهی کیک
دو بچه میخوان یه کیک رو تقسیم کنن و هر دو نگرانن سهمشون کمتر باشه. یه الگوریتم قدیمی و هوشمندانه: یکی میبره، اون یکی انتخاب میکنه. کسی که میبره، میدونه اگه نابرابر ببره، تکهی کوچیکتر به خودش میرسه؛ پس تا جایی که میتونه برابر میبره.
این الگوریتم بی هیچ داوری، منصفانهست؛ چون انگیزهی هر دو نفر رو درست میچینه. پژوهشگرها نسخههای پیچیدهتری از این ایده برای سه نفر و بیشتر هم ساختن، و همین فکرها توی تقسیم منابع بین برنامهها، یا طراحی حراجهای آنلاین، به کار میرن.
جدول حذفی: پیدا کردن بهترین
توی یه جام حذفی با شونزده تیم، هر بازی یه تیم رو حذف میکنه. برای پیدا کردن قهرمان، باید پونزده تیم حذف بشن؛ پس دقیقا پونزده بازی لازمه. این، یه الگوریتم پیدا کردن بزرگترینه، با مقایسهی جفتجفت.
ولی یه نکتهی جالب: تیم دوم واقعی، لزوما فینالیست نیست؛ شاید توی دور اول به قهرمان خورده و حذف شده. برای پیدا کردن دومی واقعی، باید بین تیمهایی که به قهرمان باختن، یه رقابت کوچیک دیگه گذاشت. این، همون چیزیه که دانشمندها توی تحلیل الگوریتمهای پیدا کردن «دومین بزرگترین» بررسی کردن.
شمردن رایها
توی یه انتخابات کلاسی، رایها رو چطور میشمرید؟ هر برگه رو میخونید و جلوی اسم اون نفر، یه خط میکشید. آخر، خطها رو میشمرید. این، یه الگوریتم شمارشه که با یه جدول کوچیک، یعنی یه جور جدول هش، کار میکنه: هر اسم، یه جای مشخص روی کاغذ.
حالا اگه رایها خیلی زیاد باشن، میشه کار رو بین چند نفر تقسیم کرد: هر کس یه دسته برگه رو میشمره و آخر، عددها جمع میشن. همین ایده، یعنی تقسیم کار بین چند شمارنده و جمع کردن نتیجهها، پایهی پردازش دادههای خیلی بزرگ توی شرکتهای بزرگ اینترنتیه.
غلطیاب گوشی: نزدیکترین کلمه
وقتی توی گوشی «سلم» تایپ میکنید و گوشی «سلام» پیشنهاد میده، یه الگوریتم داره نزدیکترین کلمهی درست رو پیدا میکنه. یه راه سنجیدن نزدیکی، شمردن کمترین تعداد تغییره: افزودن، حذف یا عوض کردن یه حرف. از «سلم» تا «سلام»، یه تغییره: افزودن یه الف.
به این عدد، فاصلهی ویرایشی (Edit Distance) میگن و برای حسابش، یه الگوریتم برنامهنویسی پویا هست که توی ایستگاه پنجم میبینیم. همین ایده، توی پیدا کردن شباهت بین متنها، و حتی مقایسهی رشتههای ژنتیکی توی زیستشناسی، به کار میره.
«شاید این رو هم دوست داشته باشید»
وقتی یه فروشگاه اینترنتی میگه «کسانی که این رو خریدن، این رو هم خریدن»، یه الگوریتم سادهی پیشنهاد کار میکنه: نگاه به خریدهای آدمهایی که شبیه شما خرید کردن، و پیشنهاد چیزهایی که اونها خریدن و شما هنوز نه. به این ایده، پالایش مشارکتی (Collaborative Filtering) میگن.
این الگوریتمها امروز خیلی پیچیدهتر شدن و از یادگیری ماشین استفاده میکنن؛ ولی ایدهی پایه همونه: شباهت. یه نکتهی مهم هم دارن: فقط چیزی رو پیشنهاد میدن که شبیه گذشتهست؛ برای همین گاهی آدم رو توی یه دایرهی تکراری نگه میدارن.
گاهی «به اندازهی کافی خوب» بهترینه
توی خیلی از این مثالها دیدیم که پیدا کردن بهترین جواب دقیق، یا خیلی سخته یا ارزش وقتش رو نداره. هیچکس برای بستن چمدون، همهی ترکیبهای ممکن رو امتحان نمیکنه. آدمها یه قاعدهی ساده و سریع به کار میبرن که معمولا جواب خوبی میده. به این قاعدهها، روش ابتکاری (Heuristic) میگن.
کامپیوترها هم برای مسئلههای خیلی سخت، همین کار رو میکنن: جواب خوب و سریع، به جای جواب کامل و غیرممکن. هنر طراحی الگوریتم، فقط پیدا کردن بهترین جواب نیست؛ دونستن اینه که کی بهترین لازمه و کی «به اندازهی کافی خوب» کافیه.
چرا اسم اینها رو بدونیم
شاید بپرسید وقتی این کارها رو بلدیم، دونستن اسمشون چه فایدهای داره. فایدهش اینه که اسم، یه ایده رو قابل جابهجا کردن میکنه. وقتی بدونید جفت کردن جوراب و پیدا کردن کاربر با نام کاربری، هر دو «هش» ـن، راه حل یکی رو میتونید برای اون یکی به کار ببرید.
برنامهنویسها هم دقیقا همینطوری فکر میکنن: یه مسئلهی تازه رو میبینن و میپرسن «این شبیه کدوم مسئلهی معروفه؟». اگه شبیه یه مسئلهی حلشده باشه، نصف کار انجام شده. این مسیر، همین مسئلههای معروف رو یکییکی معرفی میکنه.
چند باور رایج
- «الگوریتم فقط توی کامپیوتره.» هر روز دهها الگوریتم با دست اجرا میکنید.
- «کوتاهترین صف همیشه سریعترینه.» تعداد سبدها هم مهمه.
- «بیشتر نفر یعنی کار سریعتر.» فقط بخش قابل تقسیم، سریعتر میشه.
- «همیشه باید بهترین جواب رو پیدا کرد.» گاهی جواب خوب و سریع بهتره.
- «اسم الگوریتمها فقط برای امتحانه.» اسم، ایده رو به مسئلهی تازه میبره.
یه مثال
رضا صاحب یه کافهی کوچیکه و ساعت شلوغی، سفارشها روی هم میمونن. اول سفارشها رو به ترتیب رسیدن آماده میکرد؛ یه صف ساده. ولی یه چای ساده، پشت یه سفارش دهتایی معطل میموند. یه روز تصمیم گرفت سفارشهای یکیدوتایی رو یه نفر جدا آماده کنه، و بقیه رو به ترتیب.
بعد دید وقتی قهوهساز گرم میشه، میشه همزمان کیکها رو برید. بی اینکه اسمش رو بدونه، چند الگوریتم به کار برده بود: صف، اولویت کارهای کوتاه و همزمانی. مشتریها کمتر معطل میشن و یکیشون، که برنامهنویس بود، بهش گفت: «شما داری یه سیستمعامل اداره میکنی».
تمرین امروز
امروز الگوریتمهای روز خودتون رو پیدا کنید.
- سه کار از روزتون رو بنویسید که ترتیب مشخصی دارن.
- برای هر کدوم، فکر کنید کدوم مثال این درس شبیهشه: صف، پشته، جستجو، مرتبسازی یا مسیر.
- یه کار رو پیدا کنید که «به اندازهی کافی خوب» انجامش میدید و میشه بهترش کرد.
- یه جای ثابت برای یه چیزی که همیشه گم میکنید، تعیین کنید؛ یه هش کوچیک.
- یه بار بیست سوالی بازی کنید و سوالهایی بپرسید که نصف کنن.
درس بعدی، یه راه کشیدن الگوریتمها رو یاد میده: فلوچارت: کشیدن الگوریتم.
جمعبندی. آنچه از این درس با خودتان میبرید.
- کارهای روزمره، الگوریتمهای واقعی با اسم دارن.
- جوراب پیش از کفش: مرتبسازی بر اساس وابستگی.
- چیدن ورق: مرتبسازی درجی؛ دفترچه: جستجوی دودویی.
- صف، پشته و جفت کردن جوراب: ساختمانهای دادهی روزمره.
- گاهی بهترین جواب ممکن نیست و «به اندازهی کافی خوب» کافیه.
خودتون رو بسنجید
۱۵ پرسش، هر بار تازه از میان ۳۰ پرسش این درس. آخرش فقط کارنامه رو میبینید: چند تا درست، چند تا نادرست.