الگوریتم sollin در پایتون عنوان سورس کدی است که در این پست به آن پرداخته می شود. برای تعیین درخت پوشای کمینه الگوریتم های زیادی وجود دارد یکی از این الگوریتم ها الگوریتم سولین Sollin می باشد. در ادامه به تشریح این مسئله خواهیم پرداخت.
تهیه و تنظیم: تیم طراحی و تولید پی استور
متشکل از اساتید و فارغ التحصیلان رشته های فنی - مهندسی
تیم طراحی و تولید پی استور از اولین تیم های تشکیل شده در مجموعه آموزشی پی استور می باشد. این تیم از اساتید مجرب و فارغ التحصیلان رشته های فنی و مهندسی تشکیل شده که در زمینه های مختلف تولید محتوای تخصصی فعال هستند.
الگوریتم سولین sollin
الگوریتم سولین یا Sollin راهی برای پیدا کردن درخت پوشای کمینه است. یک درخت پوشای مینیمم درختی است که در آن مجموع وزن لبه به حداقل برسد. این اولین الگوریتمی بود که در سال 1926 برای پیدا کردن درخت پوشای کمینه MSTs طراحی شد. آقای Otakar Boruvka از آن برای یافتن مسیریابی کارآمدترین شبکه برق استفاده کرده است. الگوریتم ها و روش های زیادی برای پیدا کردن درخت پوشای حداقل وجود دارد. الگوریتم Boruvka یک الگوریتم حریصانه است و مشابه الگوریتم Kruskal و الگوریتم Prim است.
این روش اساساً حد وسط بین دو الگوریتم کروسکال و پریم است. این الگوریتم اغلب با نام الگوریتم بروکا نیز شناخته می شود. در کتاب های ساختمان داده اغلب از این روش با نام الگوریتم سولین یاد می شود. برای یادگیری هر چه بهتر الگوریتم به مقاله ای تحت عنوان الگوریتم سولین در همین سایت مراجعه کنید که به طور مفصل مراحل این الگوریتم در آن توضیح داده شده است.
تشریح الگوریتم Sollin
بر خلاف الگوریتم های پریم و راشال – کروسکال که در هر مرحله فقط یک لبه به درخت اضافه می کردند در الگوریتم سولین چندین لبه را برای درخت اضافه می کند. در ابتدا یک مرحله لبه های انتخاب شده، همراه با تمام n راس گراف، تشکیل یک درخت پوشا را می دهند. در خلال یک مرحله یک لبه برای هر درخت انتخاب می شود که دارای حداقل هزینه بوده یعنی اینکه دقیقاً دارای یک راس در درخت می باشد. از آنجا که دو درخت در جنگل می توانند یک لبه یکسان انتخاب کنند، لذا می توان کپی تکراری لبه ها را حذف کرد.
در ابتدای مرحله اول مجموعه لبه های انتخاب شده خالی است. این الگوریتم هنگامی پایان می یابد که فقط یک درخت در انتهای یک مرحله باقی و یا هیچ لبه ای برای انتخاب باقی نمانده باشد. شکل زیر روند اجرای الگوریتم سولین را نشان می دهد.
الگوریتم sollin در پایتون
پیاده سازی الگوریتم سولین در Python شامل توابعی است که مراحل بالا را انجام می دهد. به دلیل محدودیت در شکل گرافیکی در Python این کار با ورود اعداد و ارقام انجام می شود. مثلاً برای کشیدن گراف بایستی تعداد گره ها و یال ها و هزینه هر یال بصورت دستی انجام می شود. قسمتی از سورس کد الگوریتم sollin در پایتون به صورت زیر است.
from collections import defaultdict #Class to represent a graph class Graph: def __init__(self,vertices): self.V= vertices #No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self,u,v,w): self.graph.append([u,v,w]) # A utility function to find set of an element i # (uses path compression technique) def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) . . . g = Graph(4) g.addEdge(0, 1, 10) g.addEdge(0, 2, 6) g.addEdge(0, 3, 5) g.addEdge(1, 3, 15) g.addEdge(2, 3, 4) g.boruvkaMST()
خروجی حاصل از اجرای این الگوریتم نیز بصورت زیر است:
Edge 0-3 included in MST Edge 0-1 included in MST Edge 2-3 included in MST Weight of MST is 19
ویدئوی معرفی محصول
درباره سورس کد الگوریتم sollin در پایتون
این محصول تحت عنوان سورس کد تعیین درخت پوشای کمینه با الگوریتم سولین sollin در پایتون Python در نرم افزار Python نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می باشد چرا که دارای کد های روان و قابل فهم و آسان برای یادگیری می باشد. خرید محصول توسط کلیه کارت های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود محصول در اختیار شما قرار خواهد گرفت. کیفیت محصول توسط کارشناسان پی استور تضمین می شود.
مباحث مرتبط با الگوریتم Solin
مباحث پیشنهادی در حوزه حل درخت پوشای مینیمم
تاریخ انتشار: | 24 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 18 شهریور 1398 |
حجم فایل: | 1.5 کیلوبایت |
فرمت فایل | py. در قالب پایتون |
نسخه: | 1.0 |
هماهنگی با: | (Spyder (Python 3.8 و بالاتر |
تاکنون 278 نفر این محصول را تهیه کرده اند و 2 نظر برای آن ثبت شده است.
نظرات و دیدگاه ها
قوانین ثبت دیدگاه
- لطفاً دیدگاه های خود را فارسی تایپ کنید.
- دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
- از درج دیدگاه های تکراری پرهیز نمایید.
- سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.
قیمت 49,000 تومان
تاریخ انتشار: | 24 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 18 شهریور 1398 |
حجم فایل: | 1.5 کیلوبایت |
فرمت فایل | py. در قالب پایتون |
نسخه: | 1.0 |
هماهنگی با: | (Spyder (Python 3.8 و بالاتر |
2 بازخورد (مشاهده نظرات)
قیمت: 49,000 تومان
آرمان
سلام. حتما باید با نرم افزار اسپایدر اجرا بشه؟
فاطمه اسماعیلی
سلام. خیر با خود IDE پایتون و همینطور VS Code هم قابل اجرا هست.
مهمان
خوب بود