کاوش محیط های مستطیلی سلول بندی شده

منظور از کاوش محیطسلول بندیشده، یافتنکوتاه ترین مسیر بسته در داخل محیط است با این شرط که هر سلول حداقل یک بار ملاقات شود. در اینمساله، براساس شناخت یاعدم شناخت ربات ازمحیطکاری خود، دونسخه برخط و برون خط تعریف شود. در این پایان نامه بر روی محیط سلول بندیشده ی با m ستون و n سطر که آن را با R(m,n) نشان می دهیم، تمرکز میکنیم. ابتدا نشان می دهیم که طول مسیر کاوش بهینه در هر R(m,n) حداکثر 1+mn است. درنسخه برون خط، محیط کاری ربات به عنوان ورودی داده شود. در ایننسخه، مسیر کاوش بهینه را برای دو حالت R(m,n) فرد (m.n فردباشد) , زوج(m.n زوج باشد) ارایه می دهیم. در نسخه ی برخط، ربات دیدی محدود داشته و کاوش محیط را از سلول شروع خود بدون هیچ دانشی نسبت به محیط آغاز میکند. در این حالت ابتدا با فرض مرزی بودن سلول شروع ربات، الگوریتم بهینه برای محاسبه یمسیر کاوش ارایه میدهیم.

کلیدواژه ها:

الگوریتمبرخط ، ضریب رقابتی ، محیطسلول بندیشده ، مسالهکاوش