الگوریتم مبتنی بر Heap با سوئیفت – از صفر تا صد

۱۹۴ بازدید
آخرین به‌روزرسانی: ۳ مهر ۱۴۰۲
زمان مطالعه: ۴ دقیقه
دانلود PDF مقاله
الگوریتم مبتنی بر Heap با سوئیفت – از صفر تا صدالگوریتم مبتنی بر Heap با سوئیفت – از صفر تا صد

در یکی از مطالب قبلی مجله فرادرس به بررسی الگوریتم «دایجسترا» (Dijkstra) برای جستجوی یک گراف پرداختیم. این الگوریتم که در سال 1959 انتشار یافته است، یک تکنیک رایج برای یافتن کوتاه‌ترین مسیر در مسائل پیچیده محسوب می‌شود. در آن مقاله به بررسی جنبه‌های گوناگون از قبیل پیمایش گراف، ساختمان‌های داده سفارشی و «رویکرد حریصانه» (greedy approach) پرداختیم. زمانی که برنامه‌ها را طراحی می‌کنیم، تماشای کار کردن آن‌ها حس خوبی ایجاد می‌کند. استفاده از الگوریتم دایجسترا به ما امکان می‌دهد که کوتاه‌ترین مسیر بین رأس مبدأ و مقصد را بیابیم. با این حال این رویکرد را می‌توان بهبود بخشید تا کارآمدتر شود. در این مقاله قصد داریم با استفاده از الگوریتم مبتنی بر Heap این بهینه‌سازی را اجرا کنیم. برای مطالعه مقاله قبلی می‌توانید روی لینک زیر کلیک کنید:

997696

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

طرز کار الگوریتم مبتنی بر Heap

ساحتمان داده Heap اساساً فقط از یک آرایه تشکیل یافته است.

با این حال برخلاف آرایه آن را به صورت درخت بصری‌سازی می‌کنیم. کلمه «بصری‌سازی» بدین معنی است که از تکنیک‌های پردازشی استفاده می‌کنیم که به طور معمول با ساختمان‌های داده بازگشتی مرتبط هستند. این تغییر در طرز تفکر، مزیت‌های زیادی دارد. به مثال زیر توجه کنید:

چنان که می‌بینید، numberList را می‌توان به سادگی به صورت یک Heap تصور کرد. با آغاز از اندیس 0، آیتم‌ها یک نقطه متناظر را به صورت گره والد یا فرزند پر می‌کنند. هر والد نیز به استثنای اندیس شماره 2 دارای دو فرزند است.

درک الگوریتم مبتنی بر Heap
مثالی از یک آرایه که به صورت یک «درخت تقریباً کامل» بصری‌سازی شده است.

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

هیپ‌های مرتب‌سازی

یکی از ویژگی‌های جالب هیپ، توانایی آن برای مرتب‌سازی است.

الگوریتم‌های زیادی برای مرتب‌سازی دنباله‌های داده‌ها طراحی شده‌اند و هنگامی که به مرتب‌سازی هیپ‌ها می‌پردازیم، گره‌ها می‌توانند طوری چیدمان یابند که هر والد مقداری کمتر از فرزندانش باشد. در علوم رایانه این کار به نام «هیپ-کمینه» (min-heap) خوانده می‌شود:

الگوریتم مبتنی بر Heap

در الگوریتم دایجسترا از مفهومی به نام frontier استفاده کردیم. Frontier به صورت یک آرایه ساده کدنویسی شده که در آن وزن کلی هر مسیر را برای یافتن کوتاه‌ترین مسیر مورد مقایسه قرار دادیم:

با این که این روش پاسخگو بود، اما در واقع ما از تکنیک brute force استفاده کردیم. به بیان دیگر ما همه مسیرهای بالقوه را برای یافتن کوتاه‌ترین مسیر مورد بررسی قرار داده‌ایم. این قطعه کد در یک زمان خطی O(n) اجرا می‌شود. اگر frontier شامل یک میلیون ردیف باشد، تأثیر آن بر عملکرد کلی الگوریتم چگونه خواهد بود؟

ساختار هیپ

در این بخش یک frontier کارآمدتر می‌سازیم. نام این ساختمان داده جدید که کارکرد یک آرایه را بسط می‌دهد PathHeap می‌گذاریم:

کلاس PathHeap شامل دو مشخصه است. هیپ برای پشتیبانی از طراحی خوب، یک مشخصه خصوصی اعلان کرده است. count برای ردگیری تعداد آیتم‌ها، به صورت یک «مشخصه محاسبه‌شده» (computed property) اعلان یافته است.

ساخت صف

برای جستجوی frontier به روشی کارآمدتر از O(n) باید طرز فکر جدیدی پیش بگیریم. می‌توانیم با استفاده از هیپ، عملکردمان را تا حد O(1) بهبود بخشیم. بدین ترتیب با بهره‌گیری از فرمول‌های heapsort، رویکرد جدید به این صورت است که مقادیر اندیس را طوری بچینیم که کوچک‌ترین آیتم در ریشه قرار گیرد:

متد enqueuer یک مسیر منفرد را به عنوان پارامتر می‌پذیرد. برخلاف دیگر الگوریتم‌های مرتب‌سازی، هدف ما این نیست که همه آیتم‌ها مرتب‌سازی شوند، بلکه می‌خواهیم کمترین مقدار را پیدا کنیم. این بدان معنی است که می‌توانیم با مقایسه مقادیر زیرمجموعه، کارایی را بهبود ببخشیم.

الگوریتم مبتنی بر Heap
پردازش enqueuer یک مقدار جدیداً اضافه شده را مقایسه می‌کند.
درک الگوریتم مبتنی بر Heap
پردازش تا زمانی که کوچک‌ترین مقدار در ریشه قرار گیرد، ادامه می‌یابد.

از آنجا که متد enqueuer مشخصه min-heap را نگهداری می‌کند، وظیفه اضافی یافتن کوتاه‌ترین مسیر را حذف می‌کنیم. در نتیجه، کارایی الگوریتم تا حد زمان ثابت O(1) افزایش می‌یابد. در اینجا یک متد ابتدایی peek برای بازیابی آیتم در سطح ریشه پیاده‌سازی می‌کنیم:

هیپ و ژنریک

استفاده از هیپ می‌تواند به بهبود پیچیدگی زمانی راه‌حل‌های مختلف کمک کند. برای این که مدل خود را برای کاربردهای عمومی بسط دهیم، می‌توانیم الگوریتم تعمیم‌یافته‌تری نیز ایجاد کنیم:

بدین ترتیب به پایان این مقاله می‌رسیم.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
swift-algorithms-data-structures
دانلود PDF مقاله
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *