بهینه‌سازی مسیر و رقابت ربات‌ها

در مسابقهٔ ربات، رسیدن به هدف شرط لازم است نه شرط کافی؛ برنده کسی است که زودتر برسد. دو برنامه ممکن است هر دو ربات را به یک خانه برسانند ولی یکی چند ثانیه بیشتر طول بکشد. بهینه‌سازی مسیر یعنی از میان همهٔ برنامه‌های درست، ارزان‌ترین را پیدا کنی — و برای این کار اول باید «ارزان» را با عدد تعریف کنی.

تابع هزینه: زمان به‌جای احساس

هزینهٔ یک برنامه را با زمان اجرای آن می‌سنجیم: تعداد گام‌های F ضرب‌در زمان هر گام، به‌علاوهٔ تعداد چرخش‌ها ضرب‌در زمان هر چرخش. نکتهٔ کلیدی این است که چرخش هم زمان می‌برد؛ بسیاری از دانش‌آموزان فقط گام‌ها را می‌شمارند و برنامهٔ پرچرخشی می‌نویسند که روی کاغذ کوتاه به نظر می‌رسد ولی در عمل کند است.

کف مطلق: از این کمتر ممکن نیست

پیش از بهینه‌سازی، حد پایین را حساب کن. کمینهٔ تعداد F برابر فاصلهٔ منهتنی میان شروع و هدف است. کمینهٔ تعداد چرخش هم از هندسه به دست می‌آید: اگر هدف دقیقاً روبه‌روی جهت اولیه باشد صفر چرخش لازم است؛ اگر هم اختلاف افقی و هم اختلاف عمودی ناصفر باشد، دست‌کم یک چرخش لازم است. وقتی برنامه‌ات به این دو کف رسید، دیگر هیچ بهینه‌سازی‌ای در آن میدان ممکن نیست و باید سراغ کاهش خطا و برخورد بروی.

مثال عددی حل‌شده

هدف رسیدن از (۰، ۰) با جهت شمال به خانهٔ (۲، ۳) است. فاصلهٔ منهتنی برابر ۲ + ۳ = ۵ است، پس هیچ برنامه‌ای نمی‌تواند کمتر از ۵ گام داشته باشد. برنامهٔ الف یعنی F,F,F,R,F,F پنج گام و یک چرخش دارد و زمانش برابر ۵ × ۰٫۸ + ۱ × ۰٫۵ = ۴ + ۰٫۵ = ۴٫۵ ثانیه است. برنامهٔ ب یعنی F,F,R,F,F,L,F هم به همان خانه می‌رسد و آن هم پنج گام دارد، اما دو چرخش لازم دارد و زمانش برابر ۵ × ۰٫۸ + ۲ × ۰٫۵ = ۴ + ۱ = ۵ ثانیه می‌شود.

پس برنامهٔ ب به اندازهٔ ۵ − ۴٫۵ = ۰٫۵ ثانیه کندتر است و درصد کندی نسبی برابر ۰٫۵ ÷ ۴٫۵ = ۰٫۱۱۱ یعنی حدود ۱۱٫۱ درصد است. چون برنامهٔ الف هم به کف گام (۵) و هم به کف چرخش (۱) رسیده، بهینه است و هیچ برنامهٔ سریع‌تری برای این هدف وجود ندارد.

حالا امتیاز مسابقه را حساب کنیم. فرض کن قانون داوری چنین است: امتیاز برابر ۱۰۰ منهای ۲ برابر زمان بر حسب ثانیه، منهای ۵ برابر تعداد برخورد. ربات الف در ۱۸ ثانیه و بدون برخورد کارش را تمام می‌کند: ۱۰۰ − ۳۶ − ۰ = ۶۴ امتیاز. ربات ب سریع‌تر است و در ۱۴ ثانیه تمام می‌کند ولی ۲ برخورد دارد: ۱۰۰ − ۲۸ − ۱۰ = ۶۲ امتیاز. با وجود ۴ ثانیه اختلاف سرعت، ربات الف با ۲ امتیاز برنده می‌شود. اگر بخواهیم بدانیم ربات ب با همان دو برخورد چقدر باید سریع‌تر شود، کافی است بنویسیم ۱۰۰ − ۲t − ۱۰ بزرگ‌تر از ۶۴ باشد که به t کمتر از ۱۳ ثانیه می‌رسد.

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

یک کاربرد واقعی

شرکت‌های حمل بار برای هر کامیون همین مسئله را در مقیاس شهر حل می‌کنند: تابع هزینه ترکیبی از مسافت، زمان توقف در چراغ‌ها و پنجرهٔ زمانی تحویل است، و الگوریتم مسیریابی از میان میلیون‌ها ترتیب ممکن، کم‌هزینه‌ترین را انتخاب می‌کند. کاهش تنها چند درصد از هزینهٔ هر مسیر، در پایان سال به صرفه‌جویی بسیار بزرگی تبدیل می‌شود.

در شبیه‌ساز چه می‌بینی

هر دو برنامهٔ الف و ب را در یک میدان اجرا کن و شمارندهٔ گام را مقایسه کن. خواهی دید که شمارندهٔ گام هر دو یکسان است، ولی برنامه‌ای که چرخش کمتری دارد زودتر تمام می‌شود؛ پس معیار درستِ مقایسه، زمان است نه تعداد خانه‌ها.