الگوریتم و ترتیب اجرای دستورها

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

چرا ترتیب جابه‌جاشدنی نیست

هر دستور یک تابع روی حالت ربات است: حالت جدید برابر است با اِعمال دستور روی حالت قبلی. وقتی دو دستور را پشت سر هم اجرا می‌کنی در واقع دو تابع را ترکیب کرده‌ای، و ترکیب تابع‌ها در حالت کلی جابه‌جاپذیر نیست. مثال ساده: ربات در (۰، ۰) رو به شمال است. برنامهٔ F,R,F ابتدا او را به (۰، ۱) می‌برد، سپس رو به شرق می‌چرخاند و در پایان به (۱، ۱) می‌رساند. اما برنامهٔ R,F,F با همان سه دستور، اول ربات را رو به شرق می‌چرخاند و بعد دو خانه جلو می‌برد و او را در (۲، ۰) می‌گذارد. دو خانهٔ کاملاً متفاوت با دستورهای یکسان.

ردگیری دستی: مطمئن‌ترین ابزار اشکال‌زدایی

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

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

برنامهٔ F,R,F,L,F,F را از خانهٔ (۰، ۰) و جهت شمال ردگیری می‌کنیم. گام ۱ با F به (۰، ۱) می‌رسیم. گام ۲ با R جهت به شرق تغییر می‌کند. گام ۳ با F به (۱، ۱) می‌رسیم. گام ۴ با L جهت دوباره شمال می‌شود. گام‌های ۵ و ۶ با دو F به (۱، ۲) و سپس (۱، ۳) می‌رسیم. حالت پایانی: خانهٔ (۱، ۳) رو به شمال.

این برنامه ۶ دستور دارد که ۴ تای آن F و ۲ تای آن چرخش است. جابه‌جایی مستقیم برابر جذر (۱ به توان ۲ + ۳ به توان ۲) یعنی جذر ۱۰ و تقریباً ۳٫۱۶ خانه است، پس بازده مسیر برابر ۳٫۱۶ ÷ ۴ = ۰٫۷۹ می‌شود.

حالا یک پرسش شمارشی: با همین مجموعه دستور یعنی چهار F و یک R و یک L، چند برنامهٔ متمایز می‌توان نوشت؟ تعداد کل جایگشت‌های ۶ شیء برابر ۷۲۰ است، اما چون چهار F از هم قابل تشخیص نیستند باید بر ۲۴ تقسیم کنیم: ۷۲۰ ÷ ۲۴ = ۳۰ برنامهٔ متمایز. تنها تعداد کمی از این ۳۰ برنامه ربات را به هدف می‌رسانند و بقیه به دیوار می‌خورند؛ همین نشان می‌دهد که «داشتن دستورهای درست» بدون «ترتیب درست» هیچ ارزشی ندارد.

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

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

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

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

در میدان دوم، برنامهٔ پیش‌فرض را اجرا کن و بعد جای دو دستور مجاور را عوض کن. خواهی دید که تعداد دستورها همان است ولی نقطهٔ پایان و حتی موفقیت یا شکست ربات کاملاً تغییر می‌کند.