موضوع مقاله: الگوریتم حل هزارتو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم حل هزارتو | مقدمه: تعداد متفاوتی الگوریتم برای حل مسئلهٔ مارپیچ وجود دارد که آن‌ها، روش‌های خودکاری برای حل مارپیچ‌ها هستند. | ## بخش 1: الگوریتم حل هزارتو | الگوریتم‌های موشی تصادفی، دنبال کنندهٔ دیوار، تضمینی و الگوریتم تریماکس برای این طراحی شده‌اند که درون مارپیچ و توسط سیاری استفاده شوند که هیچ دانش قبلی نسبت به توپولوژی مارپیچ ندارد، در حالی که پر کردن بن بست و الگوریتم‌های کوتاه‌ترین راه برای این طراحی شده‌اند که به وسیلهٔ شخص یا برنامهٔ رایانه‌ای که می‌تواند در لحظه کل مارپیچ را ببیند، استفاده شوند. مارپیچ‌هایی که هیچ حلقه‌ای ندارد به مارپیچ‌های استاندارد یا کامل شناخته می‌شوند و با مفهوم درخت در نظریهٔ نظریه گرافها هم ارزهستند. به طوری که اگر کسی مسیرهای مارپیچ را در جهت درست بکشد، نتیجهٔ حاصل می‌تواند تبدیل به یک درخت شود. الگوریتم موشی تصادفی این یک روش بدیهی برای این مسئله است که توسط یک روبات غیر هوشمند یا شاید یک موش می‌تواند پیاده‌سازی شود و آن به سادگی حرکت کردن در یک مسیر مستقیم تا رسیدن به یک تقاطع است و بعد انتخاب یک مسیر به صورت تصادفی است تا در آن جهت حرکت شود. گرچه چنین روشی همواره در نهایت به یک پاسخ درست می‌رسد، اما این الگوریتم می‌تواند بسیار کند باشد. اگر مارپیچ یک فضای همبند ساده باشد، یعنی تمام دیوارهایش به هم یا به دیوارهٔ خارجی مارپیچ متصل باشند، با گرفتن یک دست به یک دیوار مارپیچ تضمین می‌شود که بازی‌کننده گم نمی‌شود و اگر که خروجی وجود داشته باشد به خروجی می‌رسد؛ در غیر این صورت، او دوباره به ورودی بازمی‌گردد در حالی که هر تونل مارپیچ را حداقل یک بار طی کرده باشد. یک دیدگاه دیگر برای این که چرا دنبال کنندهٔ دیوار نتیجه می‌دهد، دیدگاه توپولوژی است. اگر دیوارها متصل باشند، ممکن است به صورت یک حلقه یا دایره تغییر شکل دهند آنگاه دنبال کردن دیوار به حرکت کردن دور دایره از نقطهٔ آغاز تا پایان خلاصه می‌شود. برای پیشبرد این ایده ملاحظه شود که با گروه کردن مؤلفه‌های همبند دیوارهای مارپیچ، مرزهای آن‌ها به‌طور دقیق همان جواب هستند، حتی اگر بیش از یک جواب وجود داشته باشد. (شکل‌های سمت راست) اگر مارپیچ پیوستهٔ ساده نباشد (یعنی اگر نقطهٔ شروع یا نقاط پایان در مرکز ساختار مارپیچ باشد یا مسیرها از رو یا زیر هم بگذرند.) این روش تضمینی ندارد که در رسیدن به هدف کمک کند. دنبال کردن دیوار می‌تواند در مارپیچ‌های سه بعدی یا با بعدهای بیش تر انجام شود اگر امکانش باشد که به صورت قطعی مسیرهای آن روی صفحهٔ ۲بعدی تصویر شود. برای مثال در یک مارپیچ ۳ بعدی می‌توان مسیرهایی که به سمت خارج می‌آیند را به سمت شمال غربی و مسیرهایی که به داخل می‌روند را به سمت شمال شرقی در نظر بگیریم. اما اگر به‌طور مثال نقطه شروع در داخل صفحه باشد، ممکن است در یک بخش جدا از بخش خروجی باشد ؛ در این صورت تعقیب‌کننده دیوار به‌طور دائمی به دور خود خواهد گشت. | ## بخش 2: الگوریتم حل هزارتو | الگوریتم تضمینی طوری طراحی شده‌است که موانع احتمالی را رفع می‌کند و نیازمند انتخاب یک جهت دلخواه حرکت است. هنگامی که یک مانع دیده می‌شود یک دست را (برای مثال دست راست) به‌طور ثابت به دیواره مانع گرفته و حرکت می‌کنیم و به ازای تمام چرخش‌ها زاویهٔ چرخش را به مجموع زوایای چرخش اضافه می‌کنیم و هنگامی که به جهت حرکت اولیه بازگشتیم و مجموع زوایای چرخش صفر شد، یعنی مانع را دور زده‌ایم و مسیر را ادامه می‌دهیم. در این الگوریتم هنگامی دست را از دیوار برمی‌داریم که مجموع زوایای چرخش و جهت فعلی(نسبت به جهت اولیه) برابر صفر شده باشد. این کار این امکان را به الگوریتم می‌دهد که در مسیرهای تله دار به شکل حرف "G" گیر نیفتد. فرض کنید که الگوریتم(در حرکت روی G) از دیوار اولی به سمت چپ بپییچد آنگاه به وسیلهٔ دیوارها مجبور می‌شود۳۶۰ درجه بچرخد. این چنین که هنگامی که راست‌ترین دیوار پایین را ترک کند، دوباره وارد بخش منحنی سمت چپ می‌شود. الگوریتم تضمین‌کننده راست‌ترین دیوار را به دلیل اینکه مجموع زوایای چرخش در آن نقطه صفر نشده، ترک نمی‌کند و دیوار را همچنان دنبال می‌کند تا در نهایت با حرکت به سمت چپ و دقیقاً زیر شکل حرف از آن خارج می‌شود. ین الگوریتم به یک فرد به همراه قطب نما این امکان را می‌دهد که از هر نقطه درونی، بدون در نظر گرفتن مکان اولیه، به یک خروجی در بیرون هر مارپیچ متناهی دوبعدی راه یابد. اما قابلیت یافتن مسیر برای حالاتی که نقطه شروع خارج صفحه و نقطه پایان داخل صفحه باشد را دارا نیست. الگوریتم تریماکس الگوریتم تریماکس که توسط چارلز پیر ترماکس معرفی شده، یک روش بهینه برای پیدا کردن راه خروجی مارپیچ است که لازمهٔ آن کشیدن خط‌هایی روی زمین است که مسیری را مشخص کند و تضمین شده‌است که برای تمام مارپیچ‌هایی که مسیرهای خوش تعریفی دارند کار می‌کند. هر بار مسیری انتخاب می‌شود با زدن علامت روی زمین (از انشعاب تا انشعاب) مشخص می‌شود. از ابتدا یک مسیر اتفاقی انتخاب می‌شود (اگر بیش از یک مسیر وجود داشته باشد) در هنگام رسیدن به انشعابی که هنوز بازدید نشده (هیچ مسیر علامت داری نیست) یک مسیر اتفاقی انتخاب می‌شود (و مسیر را علامتگذاری می‌کنیم). در هنگام رسیدن به انشعاب علامت دار، اگر مسیر کنونی یک علامته باشد مسیر رفته را برمی‌گردیم (و مسیر بازگشت را برای بار دوم علامت گذاری می‌کنیم) اگر این حالت نبود مسیری که کمترین علامت دارد را انتخاب می‌کنیم (و طبق معمول آن را علامت گذاری می‌کنیم)، وقتی بالاخره به نتیجه رسیدیم مسیرهایی که دقیقاً یک بار علامت گذاری شده‌اند یک مسیر مشخص به شروع را نشان می‌دهند. | ## بخش 3: الگوریتم حل هزارتو | اگر خروجی وجود نداشته باشد، این روش، مسیر را تا شروع نشان می‌دهددر حالی که تمام مسیرها دو علامته هستند. پرکردن بن بست‌ها الگوریتمی است برای حل مارپیچ‌ها که در آن تمام مسیرهای بن‌بست غیر از مسیر درست پر می‌شود. برای مواقعی که مارپیچ بر روی کاغذ است یا توسط رایانه قصد حل آن را از این روش می‌توان استفاده کرد . در این الگوریتم تمام صفحه مارپیچ یکجا دیده می‌شود بنابراین برای فردی که داخل یک مارپیچ نامعلوم قرار دارد مفید نمی‌تواند باشد . روش کلی کار این است که اول تمام بن بست‌ها را پیدا کرده و سپس از یک بن بست تا اولین انشعاب را پر می‌کند. الگوریتم پرکردن بن‌بست نمی‌تواند به‌طور اتفاقی یک مسیر را از ابتدا حذف کند و باید برای تمام بن بست‌ها اجرا شود زیرا در هر مرحله توپولوژی مارپیچ حفظ می‌شود. علاوه برآن، این رویه به دلیل اینکه پاسخ نهایی نمی‌تواند هیچ بن‌بستی را شامل شود طولانی!!!! اگر این الگوریتم بر روی مارپیچی کامل (مارپیچی که دور نداشته باشد) اجرا شود، جوابی یکتا خواهد داد اما در صورت وجود دور تنها می‌تواند مسیرهای احتمالی مسئله را به ما بدهد. الگوریتم کوتاه‌ترین مسیر هنگامی که یک مارپیچ چند راه حل داشته باشد، ممکن است حل‌کننده بخواهد کوتاه‌ترین مسیر از ابتدا تا انتها را پیدا کند. یک الگوریتم ممکن کوتاه‌ترین مسیر را با پیاده‌سازی الگوریتم جستجوی اول سطح پیدا می‌کند. در حالی که الگوریتمی دیگر، الگوریتم جستجوی آ*، از روش‌های اکتشافی استفاده می‌کند. الگوریتم جستجوی سطح اول از یک صف استفاده می‌کند که خانه‌ها را به ترتیب بر اساس فاصلهٔ آن‌ها از ابتدا تا انتها بازدید می‌کند. | ## جمع‌بندی | هر خانهٔ بازدید شده باید اطلاعات مربوط به فاصلهٔ خودش از نقطهٔ شروع یا اینکه کدام یک از همسایگانش که به شروع نزدیک تر است باعث شده که به صف اضافه شود را نگه دارد.