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

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

امروز در این پست برای شما کاربران عزیز وبسایت فایل سحرآمیز یک نمونه سورس و کد حل‌کننده ماز (کوتاه‌ترین مسیر یاب) در سی شارپ را آماده دانلود قرار داده ایم.

معرفی

این فایل یک تکنیک ساده برای یافتن کوتاه‌ترین مسیر بین دو نقطه در یک ماز ​​دو بعدی ارائه می‌کند. برنامه‌های مشابه در چنین شرایطی از نمودار استفاده می‌کنند، اما این مقاله نشان می‌دهد که چگونه می‌توان این کار را بدون دردسر نمودار انجام داد. از تکنیکی شبیه به جستجوی عرضی استفاده می کند. کلاس MazeSolver Maze را به عنوان یک آرایه عدد صحیح دو بعدی با مقدار '0' برای گره های باز (در دسترس) و غیر صفر برای گره های بسته (دیوار) ذخیره می کند. اگر مسیری پیدا شود، یک آرایه عدد صحیح دوبعدی جدید با مسیری PathCharacterکه مقدار پیش‌فرض آن '100' است، ردیابی می‌شود. کلاس همچنین می تواند مسیرهای مورب را در صورت اجازه انجام دهد.

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

الگوریتم جستجوی پهنا-اول

ایده کلی پشت الگوریتم جستجوی پهنا اول این است که یک گره شروع را بررسی می کنیم، مثلا A. سپس همه همسایگان A را بررسی می کنیم، سپس همه همسایگان همه همسایگان A را بررسی می کنیم، و به همین ترتیب... به گره انتهایی مورد نظر می رسیم یا تا زمانی که هیچ گره ای برای بررسی نداشته باشیم (در این صورت هیچ مسیری وجود نخواهد داشت). به طور طبیعی، ما باید تمام گره ها را ردیابی کنیم تا مطمئن شویم که هیچ گره ای بیش از یک بار پردازش نمی شود. این کار با پیوند دادن یک فیلد "وضعیت" با تمام گره ها انجام می شود. طرح کلی الگوریتم به شرح زیر است:

• راه اندازی همه گره ها در حالت آماده (Status=Ready)
• گره شروع را، مثلاً A، در صف قرار دهید و وضعیت آن را به حالت انتظار (Status=Waiting) تغییر دهید.
• مراحل a و b را تکرار کنید تا صف خالی شود:
• گره جلویی، مثلاً N، صف را بردارید. N را پردازش کرده و وضعیت N را به حالت پردازش شده تغییر دهید (Status=Processed)
• تمام همسایگان N را که در حالت آماده هستند (وضعیت = آماده) به پشت صف اضافه کنید و وضعیت آنها را به حالت انتظار (وضعیت = انتظار) تغییر دهید.
• خارج شوید

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

حداقل مسیر بین دو گره را می‌توان با استفاده از جستجوی پهنا-اول پیدا کرد، اگر منشاء هر یال (یعنی نحوه رسیدن به یک عنصر خاص در پیچ و خم) را با استفاده از یک آرایه Origin همراه با آرایه Queue پیگیری کنیم. این روش در کلاس استفاده می شود.

بدون نمودار!

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

برای شما کاربران عزیز پیشنهاد دانلود داده می شود.