الگوریتم Sollin سولین تشریح همراه با مثال
الگوریتم Boruvka (الگوریتم Sollin)
الگوریتم Sollin یا همان الگوریتم Boruvka عنوان موضوعی است که در این پست به آن پرداخته می شود. ابتدا الگوریتم سولین تشریح می شود سپس مثال عملی از این الگوریتم زده می شود. برای اطلاهات بیشتر روی مفاهیم موجود در این پست به لینک هایی که گذاشته شده حتماً مراجعه کنید.
الگوریتم بروکا Boruvka چیست؟
الگوریتم Boruvka راهی برای پیدا کردن درخت پوشای کمینه است. یک درخت پوشای مینیمم درختی است که در آن مجموع وزن لبه به حداقل برسد. این اولین الگوریتمی بود که در سال 1926 برای پیدا کردن درخت پوشای کمینه MSTs طراحی شد. آقای Otakar Boruvka از آن برای یافتن مسیریابی کارآمدترین شبکه برق استفاده کرده است. الگوریتم ها و روش های زیادی برای پیدا کردن درخت پوشای حداقل وجود دارد. الگوریتم Boruvka یک الگوریتم حریصانه است و مشابه الگوریتم Kruskal و الگوریتم Prim است. این روش اساساً حد وسط بین دو الگوریتم کروسکال و پریم است. این الگوریتم اغلب با نام الگوریتم Sollin نیز شناخته می شود. در کتاب های ساختمان داده اغلب از این روش با نام الگوریتم سولین یاد می شود.
تشریح الگوریتم Sollin
بر خلاف الگوریتم های پریم و راشال – کروسکال که در هر مرحله فقط یک یال به درخت اضافه می کردند در الگوریتم سولین چندین لبه را برای درخت اضافه می کند. در ابتدا یک مرحله لبه های انتخاب شده، همراه با تمام n راس گراف، تشکیل یک درخت پوشا را می دهند. در خلال یک مرحله یک لبه برای هر درخت انتخاب می شود که دارای حداقل هزینه بوده یعنی اینکه دقیقاً دارای یک راس در درخت می باشد. از آنجا که دو درخت در جنگل می توانند یک لبه یکسان انتخاب کنند، لذا می توان کپی تکراری لبه ها را حذف کرد. در ابتدای مرحله اول مجموعه لبه های انتخاب شده خالی است. این الگوریتم هنگامی پایان می یابد که فقط یک درخت در انتهای یک مرحله باقی و یا هیچ لبه ای برای انتخاب باقی نمانده باشد. شبه کد الگوریتم Boruvka به صورت زیر است:
1) Input is a connected, weighted and directed graph. 2) Initialize all vertices as individual components (or sets). 3) Initialize MST as empty. 4) While there are more than one components, do following for each component. a) Find the closest weight edge that connects this component to any other component. b) Add this closest edge to MST if not already added. 5) Return MST.
سورس کد تعیین درخت پوشای کمینه با الگوریتم sollin در پایتون
این سورس کد به زبان پایتون نوشته شده و درخت پوشای کمینه را با استفاده از الگوریتم سولین حل میکند. برای دانلود سورس کد بر روی لینک زیر کلیک نمایید.
مثال الگوریتم سولین (Sollin)
برای مثال گراف شکل زیر را همراه با هزینه هر لبه در نظر می گیریم.
ابتدا MST یا درخت پوشا خالی است هر رأس یک جزء یا مولفه تنها است که در زیر نمودار با رنگ آبی مشخص شده است.
برای هر جزء، ارزان ترین لبه را پیدا کنید که آن را به یک جزء دیگر متصل می کند.
Component Cheapest Edge that connects it to some other component {0} 0-1 {1} 0-1 {2} 2-8 {3} 2-3 {4} 3-4 {5} 5-6 {6} 6-7 {7} 6-7 {8} 2-8
ارزان ترین لبه با رنگ سبز مشخص شده است. اکنون MST 0-1، 2-8، 2-3، 3-4، 5-6، 6-7 می شود.
بعد از مرحله بالا اجزاء یا همان زیر دختان {{0،1}، {2،3،4،8}، {5،6،7}} می باشد. اجزاء با رنگ آبی محاصره می شوند.
در مرحله بعد دوباره گام قبلی را برای مشخص کردن ارزان ترین لبه تکرار می کنیم، به عنوان مثال، برای هر جزء، ارزان ترین لبه را پیدا می کنیم که آن را به برخی اجزای دیگر متصل می کند ( یعنی به درختان دیگر متصل کند نه اعضای جزء خودش)
Component Cheapest Edge that connects it to some other component {0,1} 1-2 (or 0-7) {2,3,4,8} 2-5 {5,6,7} 2-5
در مرحله آخر تنها یک جزء {0، 1، 2، 3، 4، 5، 6، 7، 8} وجود دارد که همه لبه ها دارد. از آنجا که تنها یک جزء وجود دارد، الگوریتم متوقف می شود و درخت ایجاد می شود. در نهایت درخت پوشا بصورت زیر خواهد بود و هزینه آن نیز برابر 37 خواهد بود.
الگوریتم سولین در سی پلاس پلاس (حل درخت پوشای کمینه با الگوریتم سولین)
سورس کد تعیین درخت پوشای کمینه با الگوریتم سولین در سی پلاس پلاس نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می باشد.
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
بالاخره اینو یاد گرفتم 😎
[…] حداقل الگوريتم کروسکال (Kruskal) و الگوريتم پريم (Prim) و الگوریتم سولین (Sollin) به روش حریصانه شروع به حل مسئله می کنند. دو الگوریتم […]
[…] این نوع دسته الگوریتم ها می توان به الگوریتم کروسکال و سولین نیز اشاره […]