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

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

کلیدواژه ها:

الگوریتم دیکسترا ، هزارتو ، برنامه نویسی پویا ، گراف