در نزدیکی خونه‌مون یک پارک جنگلی هست که متعلق به راکفلرها بوده. پارک خیلی بزرگه و آدم می‌تونه به راحتی توش گم بشه. مشکل این‌جاست که در یک مسیر که جلو می‌رین، مرتب به دوراهی برخورد می‌کنین و باید راه راست یا راه چپ رو انتخاب کنین؛ اما موقع برگشت الزامن به یاد ندارین که راه راست رو انتخاب کرده بودین یا راه چپ رو و این‌جاست که ممکنه گم بشین.
بعد از یکی دو بار نیمه گم شدن در پارک، بالاخره به یک روش برای پیدا کردن مسیر برگشت دست پیدا کردم که پیشنهاد می‌کنم شما هم در موارد مشابه (و یا حتا در خیابون یا هرجای دیگه که از نظر کیفی به همین وضعیت شبیه هست) ازش استفاده کنین:
در تمام مدت کافیه یک عدد رو به یاد داشته باشین. بهش بگیم عدد مسیر. در شروع گردش، عدد مسیر برابر با ۱ خواهد بود. در مسیر جلو برین. هر موقع به دوراهی رسیدین، به دل‌خواه یکی از دو راه رو انتخاب کنین:
– اگر راه سمت چپ رو انتخاب کردین، عدد مسیر رو ضرب در دو کنین
– اگر راه سمت راست رو انتخاب کردین، عدد مسیر رو ضرب در دو کنین و یکی بهش اضافه کنین
برای مثال اول سفر که عدد مسیرتون برابر با ۱ هست. فرض کنین در طی مسیر در اولین دوراهی به راست می‌پیچین (پس عدد مسیر برابر می‌شه با ۳) و بعد در دوراهی بعدی به چپ می‌پیچین (پس عدد مسیر برابر می‌شه با ۶) و بعد در دوراهی بعدی باز هم به چپ می‌پیچین (و عدد مسیر برابر می‌شه با ۱۲) و در پایان به راست می‌پیچین (و عدد مسیر برابر می‌شه با ۲۵).
به همین ترتیب هر چه قدر که دوست دارین جلو می‌رین. وقتی می‌خواهین برگردین و به نقطه‌ی شروع برسین، طبیعتن به یکی از دوراهی‌هایی می‌رسین که قبل‌تر ازش رد شده بودین. در این حال،
– اگر عدد مسیر زوج هست، راه سمت راست رو انتخاب کنین و عدد مسیر رو تقسیم بر دو کنین
– اگر عدد مسیر فرد هست، راه سمت چپ رو انتخاب کنین، از عدد مسیر یکی کم‌کنین و بعد بر دو تقسیمش کنین
با این ترتیب تضمین می‌کنم که وقتی عدد مسیر یک شده باشه، شما هم در نقطه‌ی شروع سفرتون هستین! (یا به عبارت دقیق‌تر اولین دوراهی‌ای رو که دیده بودین پشت سر گذاشته‌این و از این به بعد باید جلو برین تا به نقطه‌ی شروع برسین)
برای مثال فرض کنین شروع به برگشت می‌کنین و عدد مسیر برابر ۹ هست. در این حال در اولین دوراهی راه سمت چپ رو انتخاب می‌کنین (و عدد مسیر برابر می‌شه با ۴). در دوراهی بعدی راه سمت راست رو انتخاب می‌کنین (و عدد مسیر برابر می‌شه با ۲) و در دوراهی آخر هم باز راه سمت راست رو انتخاب می‌کنین (و عدد مسیر برابر می‌شه با ۱). به این ترتیب در مقصد هستین.
در حالت عادی شاید استفاده از این روش ضروری به نظر نرسه. اما این رو بگم که در پیاده‌روی دیروز، در مدت نیم ساعت، عدد مسیرم به نزدیکی دویست رسید و این‌جا بود که کم‌کم داشت اهمیت خودش رو نشون می‌داد.
توضیح بیش‌تر: علت نتیجه‌بخش بودن این روش چندان هم معجزه‌آسا نیست. توضیح ساده‌اش اینه که برای مسیر، یک رشته‌ی عدد دودویی در نظر می‌گیریم که با اضافه شدن هر دوراهی جدید کل رقم‌های صفر و یک رو به چپ حرکت می‌دیم (shift) و انتخاب جدید رو در سمت راست عدد دودویی اضافه می‌کنیم (برای اضافه شدن، راه‌های سمت چپ ۰ هستن و راه‌های سمت راست ۱).
تمرین بیش‌تر: اگر تعداد انتخاب‌ها بیش‌از دو راه بود چه کار می‌کنین؟ مثلن توی مسیر سه راهی داشته باشیم؟
تمرین بیش‌تر: اگر در مسیر حلقه داشته باشیم، این روش جواب‌گو نیست. در وقت اضافه پیدا کنین که چه اتفاق‌هایی ممکنه با وجود حلقه بیفته.
چه واضح توضیح دادی. به نظرم اصلا نمایش دودویی هم لازم نیست در نظر بگیری. این ایده در عین سادگی بسیار موثره. آفرین برشما!
جالب بود!
به گمانم اگه توی کارهای روباتیک جستجو کنیم٬ بتونیم واسه مسیریابی الگوریتمهای خوبی پیدا کنیم.
برای حالتی که سه راهی داری از ضرب در سه و جمع با صفر٬ ۱ و ۲ به ترتیب (مثلا) برای راه وسط٬ راست و چپ استفاده می کنی (اگر وسط نداشته باشیم باز با همین قانون و افزودن ۱ و ۲ کار می کنیم). در بازگشت٬ باید باقی مانده تقسیم بر ۳ رو پیدا کرد.
برای مورد حلقه هم من چک کردم٬ به نظرم چه برای حلقه های بسته و چه برای حلقه های باز همون راه حل گفته شده در این پست جواب می ده. تنها مساله ای که هست اینه که اگر واقعا چش و چالت طوری باشه که ندونی توی دور بی پایان افتادی٬ در اون صورت باید یک آستانه ای تعریف کنی که در راه رفت اگر تعداد بارهایی که گردش به یک سمت (مثلا راست) پشت سر هم تکرار می شه از اون آستانه گذشت٬ بار بعدی حتما مخالفش رو انتخاب کنی! کلا افراط و تفریط خوب نیست!