درخت پوشای کمینه: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Scholar.me (بحث | مشارکتها) جز جایگزینی با اشتباه‌یاب: ابتدایال⟸ابتدا یال، ایجادحلقه⟸ایجاد حلقه، باشدیعنی⟸باشد یعنی، درالگوریتم⟸در الگوریتم، نسبتاپرباشدویالهای⟸نسبتا پر باشد و یالهای، نیزمشابه⟸نیز مشابه، هاازکمترین⟸ها از کمترین، واگریالی⟸و اگر یالی، کندوکنارگذاشته⟸کند و کنار گذاشته، گردندسپس⟸گردند سپس، یااینکه⟸یا اینکه، یابدکه⟸یابد که |
Scholar.me (بحث | مشارکتها) جز ویرایش به‌وسیلهٔ ابرابزار: |
||
خط ۱:
'''درخت پوشای کمینه'''
فرض کنید گراف یک [[گراف همبند]] باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک [[درخت پوشا]] از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یالهای آن را دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یالهای آن، کمترین مقدار ممکن باشد. برای به دست آوردن درخت پوشای بهینه یک [[گراف جهت دار]] متصل می‌توان از الگوریتم‌های متفاوتی استفاده نمود. سه [[الگوریتم]] معروف پیدا کردن درخت پوشای کمینه عبارتند از
[[الگوریتم کروسکال]]،
[[الگوریتم پریم]]،
[[الگوریتم بروکا]] (سولین)،
[[الگوریتم حذف معکوس]]
==
تعداد حالات ممکن
خط ۱۴:
کم وزن‌ترین یال در برش گراف
ادعا: اگر گراف را به دو مجموعه V و V′ از راس‌ها افراز کنیم، کم‌وزن‌ترین یال بین یالهایی که یک طرفشان در مجموعه V و طرف دیگرشان در مجموعه V′ است باید جزء درخت پوشای کمینه باشد. (اگر چند یال با کمترین وزن وجود داشت، باید
کم‌وزن‌ترین یال گراف
خط ۲۲:
پروزن‌ترین یال هر دور
اگر یالی در یک دور از تمام یالهای موجود در آن دور وزنش بیشتر باشد، نمی‌تواند در درخت پوشای کمینه قرار بگیرد. فرض خلف: فرض کنید این یال در یک درخت پوشای کمینه وجود دارد، اگر آن را حذف کنیم درخت به دو
== کاربرد درخت پوشای کمینه ==
در مسائلی که هدف ایجاد شبکه‌ای است که برای ایجاد ارتباط بین هر دو عضو آن هزینه‌ای باید بپردازیم و می‌خواهیم در نهایت در این شبکه بین هر دو عضو ارتباط وجود داشته باشد، درخت پوشای کمینه همان کم هزینه‌ترین شبکه است. برای مثال فرض کنید در کشوری می‌خواهیم طوری جاده‌سازی کنیم که بتوان از هر شهری به هر شهر دیگری سفر کرد و هزینه ساخت جاده بین هر دو شهر را داریم (این هزینه می‌تواند تابعی بر اساس فاصله ۲ شهر، آب و هوای بین دو شهر فاصله آن‌ها از شرکت راه‌سازی و … باشد). برای پیدا کردن کم هزینه‌ترین راه، باید درخت پوشای کمینه را بیابیم.
== الگوریتم کروسکال ==
در الگوریتم کراسکال یالهای گراف را به ترتیب صعودی مرتب
این الگوریتم نیز مشابه الگوریتم پریم برای یافتن درخت پوشای کمینهٔ یک گراف به کارمی رود. دراین الگوریتم ابتدا
بیشتر زمان در الگوریتم کروسکال مربوط به
نکته
(n lg n) Ѳ =
واگرe نزدیک به کران بالا باشد یعنی گراف
(n2 lg n) Ѳ =
پس اگر گرافی یالهای کمی دارد بهتراست از روش کروسکال واگر یالهای زیادی دارد بهتراست از روش پریم استفاده کنیم.
خط ۵۵:
8 // edge u,v is the minimum weighted route from/to v
9 (u,v) ← Q.removeMin()
10 // prevent cycles in T. add u,v only if T does not already contain a path between u and v.
11 // Note that the cluster contains more than one vertex only if an edge containing a pair of
12 // the vertices has been added to the tree.
خط ۶۹:
== الگوریتم پریم ==
در این روش از یک رأس شروع
{{چپ‌چین}}
<source lang=cpp>
خط ۸۴:
{{پایان چپ‌چین}}
* ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت‌ها یکسان است.
* مرتبهٔ زمانی الگوریتم پریم برابر (o(n^2 است. (حلقهٔ while، برای n دفعه و عمل یافتن از میان لبه‌های متصل به یک مجموعه دور خاص n دفعه اتفاق
[[File:16597fe.jpg|16597fe]]|[[File:16597fe.jpg|thumb|16597fe]] نمونه مثال الگوریتم پریم
== زمان اجرای الگوریتم prim ==
به چگونگی پیاده‌سازی صف اولویت Q بستگی دارد. اگر Q به صورت min-heap دودویی پیاده‌سازی شود. می‌توانیم از روال BUILD-MIN-HEAP در خطوط
▲به چگونگی پیاده‌سازی صف اولویت Q بستگی دارد. اگر Q به صورت min-heap دودویی پیاده‌سازی شود. می‌توانیم از روال BUILD-MIN-HEAP در خطوط ۵-۱ برای [[مقدار دهی اولیه]] در زمان(O(V استفاده کنیم. بدنه حلقهwhile، |V| بار اجرا می‌شود. و چون هر عمل EXTRACT-MIN زمان(O(lgV را صرف می‌کند زمان کل برای همه فراخوانی EXTRA-MIN برابر(O(vlogV است. حلقه for در خطوط ۱۱-۸ روی هم رفته (O(E بار اجرا می‌شود چون مجموعه طول همه لیست‌های همجواری برابر ۲|E| می‌باشد. در داخل حلقه for بررسی برای عضویت در Q در خط ۹ می‌تواند در زمان ثابت با نگهداری یک بیت برای هر راس که بیان می‌کند آیا آن راس در Q قرار دارد یا خیر، پیاده‌سازی می‌شود و وقتی که راس از Q حذف شود بروز رسانی بیت انجام می‌گیرید. انتساب در خط۱۱ شامل یک عمل DECREASE- KEY ضمنی بر روی min-heap است که می‌تواند در min-heap دودویی در زمان(O(lgV پیاده‌سازی شود. بنابراین زمان کل برای الگوریتم Prim برابر(O(VlgV+ ElgV)= O(ElgV است که به‌طور مجانبی با پیاده‌سازی الگوریتم Kruskal یکسان می‌باشد.
اگر heap فیبوناچی برای پیاده‌سازی صف اولویت مینیمم Q استفاده شود. [[زمان اجرای الگوریتم]] Prim به(O(E+VlgV بهبود می‌یابد.
== الگوریتم سولین ==
در الگوریتم سولین برای هر گره یال با کمترین هزینه که از آن عبور می‌کند را رسم
== منابع ==
سطر ۱۰۰ ⟵ ۹۹:
{{چپ‌چین}}
* [//mst.sheikhoo.ir درخت پوشای کمینه]
* [[:en:Kruskal algorithm|Kruskal algorithm]]
* [[:en:Prim algorithm|Prim algorithm]]
{{پایان چپ‌چین}}
| |||