پاسخ : روبات میکرو موس
میکروموس = مکانیک و کنترل دقیق
بزارین ساده ترین الگوریتمو بزاریم همینجا.
اول به هر نحوی شده باید نقشه دیوار ها رو توی یک متغیری بزارین.
من تو یک متغیر 17*2 تایی اینتیجر گذاشتم که جمعا 16*2*17 بیت داره که همون تعداد دیوار هاست.
یکی از این 17 تایی ها ردیف و دیگری ستون.
این الگوریتم تولانی ترین زمان محاسبه و ساده ترین روش ممکنه. البته با میکرو 16 مگاهرتز تو 1-25 میلی ثانیه محاسبه می شه.
برای بدست اوردن کوتاه ترین مسیر کل زمین باید 256 بار اسکن بشه. البته هیچ وقت به این تعداد نمی رسه و با یک کد می تونین بگین هر وقت مسیر مشخص شد دیگه محاسبه نکنه.
ابتدا خونه ها باید تعریف بشن که هرکودوم یک مقداری از 0 تا 255 دارن. پس یک متغیر از نوع کرکتر 16*16.
ابتدا مقدار تمام خونه ها 255 قرار می گیره به غیر از 4 خونه مرکز که مقسده. مقسد مقدار 0 داره.
حالا برنامه شروع به اسکن کردن زمین می کنه.
یک متغیر برای اسکن وجود داره که من می گم مرحله که از 0 شروع می کنه.
پس در اسکن دنبال خونه ای می گرده که عدد 0 داشته باشه. پس می رسه به 4 خونه مرکزی. در یکی از خونه های مرکزی که رسیید اگر سمت شمال دیوار نبود و خونه بالایی مقدارش بیشتر از عدد مرحله بعلاویه 1 بود آنگاه به خونه بالای مقدار عدد مرحله بعلاوه 1 می ده در غیر این صورت هیچ مقداری بهش نمی ده. همین کارو برای خونه های چپ راست و پایین هم انجام می ده. کار که رو این خونه تموم شد می ره سراغ خونه بعدی که مقدارش 0 یا همون مقدار مرحله هستش.
بعد از این که زمین برای اولین بار کامل اسکن شد مقدار عدد مرحله +1 می شه یعنی عدد1 اونوقت با عدد 1 دوباره زمینو اسکن می کنه.
اگر ماز یک حلزون باشه و بزرگترین مسیر ماز 255 خونه باشه اونوقت برای محاسبه مسیر به 256 اسکن احتیاج هست.
برای جلوگیری از اسکن اضافه می تونین بنویسین که اگر خونه ای که ربات درش هست عددی غیر از 255 گذاشته شد. اسکن متوقف بشه یعنی مسیر پیدا شد.
حالا ربات باید تصمیم بگیره بره چپ یا راست یا بالا یا پایین. اینجا اگر بخاهیم کمتر تو تله بیفتیم می تونیم برانمه اضافه بنویسیم که به مسیر های تولانی تر هم بره.
اگر مقدار عدد خونه ربات مثلا 41 باشه یعنی با توجه به دیوار های کشف شده ربات 41 خونه تا هدف فاصله داره. پس باید بره به خونه ای که فاصلش تا هدف 40 خونه هستش. و باید در نظر بگیره که دیوار سر راهش نباشه. البته اینجا بعضی اوقات 2 یا 3 راه فاصله یکسانی تا مرکز دارن و دیواری هم بینشون نیست خوب ربات می تونه به صورت رندوم یا غیر رندوم یکی رو انتخاب کنه.
می نویسیم اگر خونه ای که در جهت حرکت ربات قرار داره دیواری جلوش نباشه و مقدار فاصله آن خونه یک عدد کمتر از مقدار فاصله خونه کنونی ربات باشه پس ربات مستقیم میره. همین کارو برای 3 جهت دیگه انجام میدیم البته اولویت حرکت مستقیم هستش ولی برای این اولویت بعضی اوقات تله می زارن.(به نظر من مهم نیست)
و به این ترتیب ربات تصمیم بگیره که مثلا بره مستقیم.
اگر ربات تونست تا هدف بره و برگرده می تونین برنامه بنویسین اگر مسیر قبلیی که ربات طی کرد با مسیری که الان تی کرد تا به مرکز برسه تفاوتی نداشت یعنی نزدیک ترین مسیر کشف شده.
فقط اگر رباتتون 45 درجه می تونه حرکت کنه باید نقاط مرز خونه ها رو هم خونه فرض کنین یا اصلا مرکز خونه ها رو در نظر نگیرین. پس برای عدد گذاری شرط اینه که مرز مورد نظر دیوار نباشه و مقدارش بیشتر از مقدار عدد مرحله باشه. ولی در هنگام تصمیم گیری باید ملاک فقط فاصله باشه و جهت مستقیم رفتن ملاک نیست.
در اسکن خونه های جهات اصلی رو مقدار عدد مرحله بعلاوه یک کنین ولی خونه های جهات مورب رو بعلاوه 1.41 اگر اون خونه مورب مقدارش از عدد مرحله بعلاوه 1.41 بیشتر بود. برای اعشار می تونین اینتیجر تعریف کنین و عدد 1 رو 100 در نظر بگیرین تا 2 رقم اعشار داشته باشین.
در ضمن در روش 45 درجه می تونین متغیر دیوار هارو حذف کنین و در همون متغییر فاصله بزارین. در مدل 45 درجه محاسبات طولانی تر می شه.
در مدل 45 یا 90 درجه می تونین خیلی راحت زمان دور زدن رو به فاصله خونه ها اضافه کنین به این طریق که در اسکن هر خونه ببینین خونه ای که مقدار فاصله کمتری داره در کدوم جهته یعنی به کجا باید بره, اینو تو یک مقدار بریزین و در عدد گذاری خونه های اطراف اگر خونه مورد نظر در امتداد اون خونه ای بود که باید بره هیچ مقدار اضافه ای برای دور زدن بهش اضافه نکنین ولی اگر جهتش متفاوت بود به نسبت زاویش یک مقدار اضافه به ازای دور زدن بهش اضافه کنین. البته ممکنه 2 خونه همسایه خونه مورد نظر باشه که مقدارشون برابر باشه و کمتر از مقدار مرحله.اینجا هیچ مشکلی پیش نمیاد برنامه درست عمل میکنه. یکم توضیحش سخته.
با این الگوریتم میزان دور زدن هم محاسبه می شه ولی باز هم لازمه که در تصمیم گیری حرکت اولویت رفتن مستقیم باشه چون الگوریتم فقط می گه اگه مسیر درستو برین خونه فلان چقدر با مرکز فاصله داره و نمی گه کدوم مسیر درسته. که اینجا مشکلی نیست.
البته محاسبه میزان دور زدن که الگوریتمو پیچیده می کنه تاثیرش شاید 15-5% باشه.
اگر مرکز خونه ها رو هم خونه فرض کنین می تونین الگوریتمی بنویسین که هم 45 و هم 90 درجه بره. برای اتمینان بیشتر.
یک سری الگوریتمای پیچیده دیگه هست که سرعت پردازشو زیاد تر می کنه و یکسری الگوریتمای دیگه هم هست که احتمال تو تله افتادنو کم می کنه که بیشتر بر پاییه ی شانسه.
این اگوریتما که جلوگیری از تله می کنه تو امتیاز نهایی تاثیری ندارن. الگوریتمای افزایش سرعت پردازش هم وقتی به درد می خورن که سرعت پردازش ربات خیلی کم باشه و نتونه با سرعت مورد نیاز تصمیم بگیره که من با همچین مشکلی برنخوردم.(با atmega32 16MHz)
مهم تر از همه اینه که نزدیک ترین مسیر تشخیص داده بشه و میزان دور زدن هم محاسبه بشه.
من دیگه نمی دونم یک الگوریتم میکروموس چی از این بیشتر لازم داره چون اگر خودمو جای اون ربات میکروموس می زاشتم از این بیشتر چیزی به ذهنم نمی رسید که به کدوم مسیر برم.
یک راه بسیار خوب برای بدست اوردن الگوریتم برای ربات اینه که خودتونو جای ربات بزارین و فکر کنین اگر بخواین با ورودی های موجود یعنی سنسور ها هوشمندانه ترین کاری که می تونین بکنین چیه.
آدم هم تا زمانی که مازو کامل بدست نیورده به طور مکرر تو تله میفته پس از آدم هوشمند تر که دیگه نمی شه برنامه نوشت. پس کلا الگوریتم جلوگیری از تله رو بی خیال بشین یا فقط یک تابع تصادفی بنویسین که وقتی به 2راهی می رسه شانسی حرکت کنه.
میکروموس = مکانیک و کنترل دقیق
بزارین ساده ترین الگوریتمو بزاریم همینجا.
اول به هر نحوی شده باید نقشه دیوار ها رو توی یک متغیری بزارین.
من تو یک متغیر 17*2 تایی اینتیجر گذاشتم که جمعا 16*2*17 بیت داره که همون تعداد دیوار هاست.
یکی از این 17 تایی ها ردیف و دیگری ستون.
این الگوریتم تولانی ترین زمان محاسبه و ساده ترین روش ممکنه. البته با میکرو 16 مگاهرتز تو 1-25 میلی ثانیه محاسبه می شه.
برای بدست اوردن کوتاه ترین مسیر کل زمین باید 256 بار اسکن بشه. البته هیچ وقت به این تعداد نمی رسه و با یک کد می تونین بگین هر وقت مسیر مشخص شد دیگه محاسبه نکنه.
ابتدا خونه ها باید تعریف بشن که هرکودوم یک مقداری از 0 تا 255 دارن. پس یک متغیر از نوع کرکتر 16*16.
ابتدا مقدار تمام خونه ها 255 قرار می گیره به غیر از 4 خونه مرکز که مقسده. مقسد مقدار 0 داره.
حالا برنامه شروع به اسکن کردن زمین می کنه.
یک متغیر برای اسکن وجود داره که من می گم مرحله که از 0 شروع می کنه.
پس در اسکن دنبال خونه ای می گرده که عدد 0 داشته باشه. پس می رسه به 4 خونه مرکزی. در یکی از خونه های مرکزی که رسیید اگر سمت شمال دیوار نبود و خونه بالایی مقدارش بیشتر از عدد مرحله بعلاویه 1 بود آنگاه به خونه بالای مقدار عدد مرحله بعلاوه 1 می ده در غیر این صورت هیچ مقداری بهش نمی ده. همین کارو برای خونه های چپ راست و پایین هم انجام می ده. کار که رو این خونه تموم شد می ره سراغ خونه بعدی که مقدارش 0 یا همون مقدار مرحله هستش.
بعد از این که زمین برای اولین بار کامل اسکن شد مقدار عدد مرحله +1 می شه یعنی عدد1 اونوقت با عدد 1 دوباره زمینو اسکن می کنه.
اگر ماز یک حلزون باشه و بزرگترین مسیر ماز 255 خونه باشه اونوقت برای محاسبه مسیر به 256 اسکن احتیاج هست.
برای جلوگیری از اسکن اضافه می تونین بنویسین که اگر خونه ای که ربات درش هست عددی غیر از 255 گذاشته شد. اسکن متوقف بشه یعنی مسیر پیدا شد.
حالا ربات باید تصمیم بگیره بره چپ یا راست یا بالا یا پایین. اینجا اگر بخاهیم کمتر تو تله بیفتیم می تونیم برانمه اضافه بنویسیم که به مسیر های تولانی تر هم بره.
اگر مقدار عدد خونه ربات مثلا 41 باشه یعنی با توجه به دیوار های کشف شده ربات 41 خونه تا هدف فاصله داره. پس باید بره به خونه ای که فاصلش تا هدف 40 خونه هستش. و باید در نظر بگیره که دیوار سر راهش نباشه. البته اینجا بعضی اوقات 2 یا 3 راه فاصله یکسانی تا مرکز دارن و دیواری هم بینشون نیست خوب ربات می تونه به صورت رندوم یا غیر رندوم یکی رو انتخاب کنه.
می نویسیم اگر خونه ای که در جهت حرکت ربات قرار داره دیواری جلوش نباشه و مقدار فاصله آن خونه یک عدد کمتر از مقدار فاصله خونه کنونی ربات باشه پس ربات مستقیم میره. همین کارو برای 3 جهت دیگه انجام میدیم البته اولویت حرکت مستقیم هستش ولی برای این اولویت بعضی اوقات تله می زارن.(به نظر من مهم نیست)
و به این ترتیب ربات تصمیم بگیره که مثلا بره مستقیم.
اگر ربات تونست تا هدف بره و برگرده می تونین برنامه بنویسین اگر مسیر قبلیی که ربات طی کرد با مسیری که الان تی کرد تا به مرکز برسه تفاوتی نداشت یعنی نزدیک ترین مسیر کشف شده.
فقط اگر رباتتون 45 درجه می تونه حرکت کنه باید نقاط مرز خونه ها رو هم خونه فرض کنین یا اصلا مرکز خونه ها رو در نظر نگیرین. پس برای عدد گذاری شرط اینه که مرز مورد نظر دیوار نباشه و مقدارش بیشتر از مقدار عدد مرحله باشه. ولی در هنگام تصمیم گیری باید ملاک فقط فاصله باشه و جهت مستقیم رفتن ملاک نیست.
در اسکن خونه های جهات اصلی رو مقدار عدد مرحله بعلاوه یک کنین ولی خونه های جهات مورب رو بعلاوه 1.41 اگر اون خونه مورب مقدارش از عدد مرحله بعلاوه 1.41 بیشتر بود. برای اعشار می تونین اینتیجر تعریف کنین و عدد 1 رو 100 در نظر بگیرین تا 2 رقم اعشار داشته باشین.
در ضمن در روش 45 درجه می تونین متغیر دیوار هارو حذف کنین و در همون متغییر فاصله بزارین. در مدل 45 درجه محاسبات طولانی تر می شه.
در مدل 45 یا 90 درجه می تونین خیلی راحت زمان دور زدن رو به فاصله خونه ها اضافه کنین به این طریق که در اسکن هر خونه ببینین خونه ای که مقدار فاصله کمتری داره در کدوم جهته یعنی به کجا باید بره, اینو تو یک مقدار بریزین و در عدد گذاری خونه های اطراف اگر خونه مورد نظر در امتداد اون خونه ای بود که باید بره هیچ مقدار اضافه ای برای دور زدن بهش اضافه نکنین ولی اگر جهتش متفاوت بود به نسبت زاویش یک مقدار اضافه به ازای دور زدن بهش اضافه کنین. البته ممکنه 2 خونه همسایه خونه مورد نظر باشه که مقدارشون برابر باشه و کمتر از مقدار مرحله.اینجا هیچ مشکلی پیش نمیاد برنامه درست عمل میکنه. یکم توضیحش سخته.
با این الگوریتم میزان دور زدن هم محاسبه می شه ولی باز هم لازمه که در تصمیم گیری حرکت اولویت رفتن مستقیم باشه چون الگوریتم فقط می گه اگه مسیر درستو برین خونه فلان چقدر با مرکز فاصله داره و نمی گه کدوم مسیر درسته. که اینجا مشکلی نیست.
البته محاسبه میزان دور زدن که الگوریتمو پیچیده می کنه تاثیرش شاید 15-5% باشه.
اگر مرکز خونه ها رو هم خونه فرض کنین می تونین الگوریتمی بنویسین که هم 45 و هم 90 درجه بره. برای اتمینان بیشتر.
یک سری الگوریتمای پیچیده دیگه هست که سرعت پردازشو زیاد تر می کنه و یکسری الگوریتمای دیگه هم هست که احتمال تو تله افتادنو کم می کنه که بیشتر بر پاییه ی شانسه.
این اگوریتما که جلوگیری از تله می کنه تو امتیاز نهایی تاثیری ندارن. الگوریتمای افزایش سرعت پردازش هم وقتی به درد می خورن که سرعت پردازش ربات خیلی کم باشه و نتونه با سرعت مورد نیاز تصمیم بگیره که من با همچین مشکلی برنخوردم.(با atmega32 16MHz)
مهم تر از همه اینه که نزدیک ترین مسیر تشخیص داده بشه و میزان دور زدن هم محاسبه بشه.
من دیگه نمی دونم یک الگوریتم میکروموس چی از این بیشتر لازم داره چون اگر خودمو جای اون ربات میکروموس می زاشتم از این بیشتر چیزی به ذهنم نمی رسید که به کدوم مسیر برم.
یک راه بسیار خوب برای بدست اوردن الگوریتم برای ربات اینه که خودتونو جای ربات بزارین و فکر کنین اگر بخواین با ورودی های موجود یعنی سنسور ها هوشمندانه ترین کاری که می تونین بکنین چیه.
آدم هم تا زمانی که مازو کامل بدست نیورده به طور مکرر تو تله میفته پس از آدم هوشمند تر که دیگه نمی شه برنامه نوشت. پس کلا الگوریتم جلوگیری از تله رو بی خیال بشین یا فقط یک تابع تصادفی بنویسین که وقتی به 2راهی می رسه شانسی حرکت کنه.
oo: 
دیدگاه