الگوریتم حل مارپیچ
الگوریتم های متفاوتی برای حل مسأله مارپیچ وجود دارد که تمامی آنها روش های تمام خودکاری برای حل مساله مارپیچ هستند. در ادامه این مقاله چند الگوریتم حل این مساله معرفی خواهند شد. الگوریتم های موشی و دنبال کننده دیوار و الگوریتم تضمین کننده و همچنین الگوریتمی به نام ترماکس برای روبات هایی بدون دانش قبلی از توپولوژی مارپیچ استفاده میشوند.از طرف دیگر الگوریتم های بن بست و کوتاه ترین مسیر برای استفاده برنامه های رایانه ای و همچنین استفاده انسان ها به کار میروند که به کمک این روش ها میتوان دید کلی از توپولوژی الگوریتم ها بدست آورد.
مارپیچ استاندارد و یا کامل به مارپیچی گفته میشود که دور نداشته باشد و معادل یک درخت در نظریه گراف ها میباشد.بسیاری از راه حل های حل مساله مارپیچ بسیار به حل مسایل مربوط به نظریه گراف نزدیکند به طوری که با یک تبدیل مناسب از مسیر ها به یالهای گراف میتوان یک گراف را از یک صفحه مارپیچ استخراج کرد.[۱]
محتویات |
الگوریتم موشی [ویرایش]
یک روش ضعیف برای حل مساله مارپیچ میباشد که قابلیت پیاده سازی بر روی روبات های با هوش مصنوعی پایین میباشد.الگوریتم اینگونه عمل میکند که یک مسیر مستقیم پیمایش میشود و هر گاه که به یک مانع برخورد کردیم به صورت تصادفی مسیر جدیدی را برای ادامه کار انتخاب میکنیم.این الگوریتم از لحاظ نظری ممکن است که به جواب نرسد و تا بی نهایت ادامه پیدا کند.همچنین از آنجا که این الگوریتم بعضی از مسیر ها را چندین با طی کند بسیار کند میباشد.
دنبال کننده دیوار [ویرایش]
این روش بهترین روش موجود برای حل صفحه های مارپیچ انتفالی میباشد که به روش قانون گردش به چپ و یا گردش به راست مشهور هستند.این الگوریتم تضمین میکند که اگر صفحه مارپیچ یک فضای پیوسته ساده باشد با گرفتن یک دست به دیوار (دست راست و یا دست چپ) همواره در صورت وجود به خروجی میرسیم و یا در غیر اینصورت به دروازه ورودی بر میگردیم.
دیدگاه دیگری که به درک چگونگی کارکرد صحیح این الگوریتم کمک میکند تصور کردن محیط صفحه مارپیچ به عنوان یک دایره بسته میباشد.پس اگر این دایره را طی کنیم یا به یک دروازه خروج رسیده و یا اینکه دوباره به نقطه شروع باز خواهیم گشت.در حقیقت هر یک از محیط های بسته ساده یک دور را میسازند.پس اگر صفحه مارپیچ فضای پیوسته ساده نباشد این الگوریتم جواب درستی به ما نمیدهد. این الگوریتم در فضاهایی با بعدهای بیشتر مثل سه بعد و یا بعد های بیشتر نیز قابل پیاده سازی میباشد اگر و تنها اگر بتوان یک نگاشت از این فضا به فضای دو بعدی داشته باشیم. به طور مثال اگر در تبدیل فضای سه بعدی به سمت بالا را یک خط اریب به سمت شمال شرق و به سمت پایین را یک خط به سمت جنوب غربی در فضای دو بعدی در نظر بگیریم میتوان فرض گرد که نگاشتی از فضای سه بعدی به فضای دو بعدی یافته ایم. اما در این حالت باید جهت کنونی حرکت به یاد داشته باشیم و در تصمیم گیری برای انتخاب حرکت بعدی از آن استفاده کنیم.
الگوریتم تضمین کننده [ویرایش]
برای صفحه مارپیچ های نا پیوسته نیز میتوان از الگوریتم دنبال کننده دیوار استفاده کرد به شرط اینکه اگر درگاه های ورود و خروج به مارپیچ در دیواره بیرونی یک حلقه قرار داشته باشند.اما اگر به طور مثال نقطه شروع در داخل صفحه باشد و دیوار های صفحه مارپیچ دارای ناپیوستگی بوده و به چند بخش تقسیم شده باشند.در این صورت به طور دایمی به دور خود خواهیم گشت.الگوریتم تضمینی این مشکل را حل خواهد کرد.
الگوریتم تضمینی به طوری طراحی شده است که موانع احتمالی را پیش بینی میکند.این الگوریتم یک جهت دلخواه حرکت را انتخاب میکند سپس به صورت مستقیم به جهت انتخاب شده حرکت میکند.هنگامی که به یک مانع رسید یک دست را به طور ثابت به دیواره مانع گرفته و حرکت میکنیم و به ازای تمام چرخش ها زاویه ای که چرخیده ایم به مجموع زوایای چرخش اضافه میکنیم و هنگامی که به زاویه حرکت اولیه بازگشتیم یعنی مجموع چرخش ها به صفر رسید یعنی به مسیر اصلی برگشته و مانع را دور زده ایم و به جهت دلخواه انتخابی ادامه مسیر میدهیم.
در این الگوریتم هنگامی دست را از دیوار بر میداریم که زاویه چرخش برابر صفر شده باشد(مجموع زوایای چرخش برای گرفتن دیوار و مجوع زوایای چرخش در حین دنبال کردن دیوار).این شگرد این امکان را به الگوریتم میدهد که در مسیر هایی مانند "G" گیر نکند. اگر الگوریتم ۳۶۰ درجه با دست چسبیده به دیوار حرکت کند یعنی این که در یک دایره افتاده است که اگر در پیاده سازی الگوریتم این حالت در نظر گرفته نشده باشد در دور بی نهات خواهد افتاد و باید الگوریتم بعد از اتفاق افتادن چرخش ۳۶۰ درجه با عوض کردن دست اجرا شود.
این الگوریتم قابلیت اجرا از هر نقطه درونی داخل صفحه مارپیچ را داراست. اما قابلیت اجرا برای حالاتی که نقطه شروع خارج صفحه باشد اما نقطه پایان داخل صفحه را دارا نیست.
الگوریتم ترماکس [ویرایش]
الگوریتم ترماکس توسط چارلز پیر ترماکس به عنوان یک الگوریتم کار آمد برای تشخیص راه حل یک مارپیچ با استفاده از نشانه گذاری مسیر پیموده شده درون یک صفحه مارپیچ میباشد. در این روش یک مسیر یا علامت نخورده است یا یک بار علامت خورده و یا دو بار علامت زده شده است.در ابتدای کار یک مسیر دلخواه انتخاب شده و هنگامی که به یک انشعاب که در گذشته علامت نخورده است میرسیم آن را علامت میزنیم و یک مسیر دلخواه دیگر را انتخاب میکنیم اما اگر به یک انشعاب علامت خورده رسیدیم مسیر آمده را در صورتی که تنها یک بار علامت خورده باشد بر میگیردیم و آن را دوباره علامت میزنیم.در حقیقت همواره مسیری که کمترین علامت را خورده باشد انتخاب میکنیم.هنگامی که نقطه مقصد علامت میخورد جواب مساله مسیری است که تنها یک بار علامت خورده باشد.
این الگوریتم در حقیقت یک نتیجه از الگوریتم جستجوی عمق اول میباشد.[۲][۳]
الگوریتم بن بست [ویرایش]
این الگوریتم برای مواقعی که میتوان تمام صفحه مارپیچ را یکجا دید مناسب است بنابراین برای مواقعی که مارپیچ بر روی کاغذ است و یا توسط رایانه قصد حل آن را داریم مناسب است.روش کلی کار این روش این است که بن بست ها را پیدا کرده و از یک بن بست تا اولین انشعاب را پر میکند. ویدیو در یوتیوبویدیو در یوتیوب. این الگوریتم به صورت مرحله به مرحله مسیر را به ما نمیدهد و باید برای تمام بن بست ها اجرا شود و مسیر هایی که در نهایت پر نشده اند نشان دهنده جواب هستند.در صورتی که مارپیچ ما دور نداشته باشد جواب یکتا به ما داده اما در صورت وجود دور مسیر هایی که جزو حداقل یک جواب هستند نشان میدهد.[۱]
الگوریتم کوتاه ترین مسیر [ویرایش]
هنگامی که یک مارپیچ دارای تعداد زیادی جواب باشد انتخاب مناسب انتخابی است که کوتاهترین مسیر میان ابتدا تا انتها را به کاربر بدهد.این الگوریتم از جستجوی اول سطح استفاده میکند ولی الگوریتم جستجو آ* از روش های اکتشافی استفاده میکنند.الگوریتم جستجوی سطح اول از یک صف برای ملاقات خانه ها به ترتیب افزایشی استفاده میکند.به طوری که به هر خانه ای که میرسد کوتاه ترین فاصله تا مبدا را در خود نگه میدارد و این کوتاه ترین فاصله از فاصله خانه های کناری به دست می آید.هنگامی که به خانه مقصد رسیدیم مسیر مناسب برابر بازگشت از مسیر طی شده به مقصد است.
منابع [ویرایش]
- مشارکتکنندگان ویکیپدیا، «Maze solving algorithm»، ویکیپدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۹ می ۲۰۱۱).
- ↑ Maze to Tree - YouTube در یوتیوب
- ↑ Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 9780521736534, http://books.google.com/books?id=m3QTSMYm5rkC&pg=PA46.
- ↑ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 9780201361186.
