فهرست بستن

الگوریتم جستجوی اول عمق در پایتون برای حل هزار تو با توضیح سطر به سطر کدها

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

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

grid = [[1,0,1,1,1,1],
        [۱,۰,۱,۰,۱,۰],
        [۱,۰,۱,۰,۱,۱],
        [۱,۱,۱,۰,۱,۱]]
print(find_path(grid))

 

محتویات بسته:

  • فایل توضیح سطر به سطر کدها
  • فایل پایتون برای حل هزار تو و پیدا کردن طول کوتاهترین مسیر از نقطه شروع به پایان
  • فایل پایتون ویرایش شده برای داشتن طول و اندیس‌های قطعات مسیر به عنوان خروجی

امیدوارم از خرید این بسته نهایت رضایت را داشته باشید. با ما در تماس باشید:

contact [at] projelecom.ir

 

برای مشاهده حل هزار تو با الگوریتم جستجوی اول سطح به این آدرس مراجعه نمایید.