الگوریتم های حل ماز میکرو ماوس هزار تو لابیرنت

http://pnu-club.com/imported/2009/07/1665.jpg

http://pnu-club.com/imported/mising.jpg

1- الگوریتم دنبال کردن دیواره ها

این الگوریتم بهترین روش پیمودن ماز است، که با قانون دست راست یا دست چپ شناخته می شود. اگر ماز ساده باشد، یعنی همه ی دیواره ها به یکدیگر یا فضای بیرونی ماز متصل باشند، این تضمین وجود دارد که با حفظ تماس یک دست به دیواره ای که از آن شروع به حرکت می کنیم، بتوان از ماز خارج شد. ولی اگر ماز ساده نباشد، این الگوریتم به یافتن خروجی در قسمت های گسسته کمکی نمی کند.

الگوریتم دنبال کردن دیواره ها در مازهای سه بعدی نیز عملی است. مثلا در یک ماز سه بعدی مسیر های رو به بالا می توانند شمال غرب و مسیرهای رو به پایین جنوب شرق فرض شوند و با روش دنبال کردن دیواره ها به نتیجه رسید.

2- الگوریتم Pledge

ماز های گسسته را می توان به روش دنبال کردن دیواه ها حل کرد، در صورتی که ورودی و خروجی ماز روی دیواره های خارجی ماز قرار داشته باشند. چنانچه از درون ماز شروع به حرکت کنیم، ممکن است الگوریتم دنبال کردن دیواره ها در قسمت گسسته ای که شامل خروجی نیست دائما یک حلقه را طی کند. الگوریتم Pledge می تواند این گونه مسائل را حل کند.

الگوریتم Pledge برای رفع موانع، به طی یک مسیر اختیاری نیاز دارد. هنگام مواجهه با مانع،یک دست (مثلا دست راست) را در امتداد مانع نگه می داریم در حالیکه زوایای چرخش شمرده می شود. وقتی دوباره در راستای مسیر اصلی قرار گرفتیم و جمع زاویه ای چرخش ها برابر صفر شد، می توان مانع را ترک کرد و در راستای مسیر اصلی حرکت نمود. این الگوریتم به شخص اجازه ی جهت یابی را در شروع از هر نقطه برای خارج از مازهای دوبعدی، را می دهد.

3- الگوریتم جستجوی تصادفی

این الگوریتم یک روش ضعیف است که به وسیله ی ربات های غیر هوشمند یا موش قابل اجراست، اما تضمینی برای رسیدن به هدف وجود ندارد. در این الگوریتم یک مسیر مستقیم طی می شود تا به اولین مانع برسد، سپس یک مسیر تصادفی را برای ادامه انتخاب می کند. این الگوریتم در صورتی که خروجی به صورت یک سوراخ در میانه ی دیوار باشد، با شکست مواجه می شود.

4- الگوریتم Tremaux

الگوریتم Tremaux یک روش کارآمد است که در آن مسیرهای طی شده با رسم خطوط نشان دار می شوند. این الگوریتم برای همه ی مازهایی که مسیر های خوش تعریف دارند، عملی است. با رسیدن به تقاطع های بی نشان، می توان یکی از جهت های ممکن را انتخاب کرد. اگر یک تقاطع قبلا طی شده باشد می توان مسیر طی شده را باز گشت. اگر نیاز به طی مسیری باشد که نشان دار است، می توان خط دیگری رسم کرد و تقاطع بعدی ممکن است شامل مسیر غیر نشان دار باشد. در این روش نیاز به طی مسیری بیش از دو بار نمی باشد و اگر خروجی وجود نداشته باشد، این روش با نقطه ی شروع ماز بر می گردد.